Перемещение объектов из неупорядоченного ассоциативного контейнера

ProgramBox

Перемещение объектов из неупорядоченного ассоциативного контейнера

Post author:admin
Запись опубликована:20 апреля, 2023
Post category:Вопросы по программированию

#c #c 11

Вопрос:

Есть ли в c 0x какой-либо способ перемещения объектов из неупорядоченных ассоциативных контейнеров? Мне нужно объединить два отдельных неупорядоченных набора, и я хотел бы, в случае, если задействованы rvalues, «переработать» элементы в наборах, которые вскоре перестанут существовать.

Дело в том, что итераторы unordered_set предоставляют только постоянные ссылки на сохраненные элементы. Изначально я думал использовать const_cast, чтобы отбросить постоянство, но при дальнейшем чтении кажется, что это приводит к неопределенному поведению. Есть предложения?

Редактировать

Возьмем этот простой пример:

 #include <string>
#include <unordered_set>

using namespace std;

void merge_sets(unordered_set<string> amp;s1, unordered_set<string> amp;amp;s2)
{
   // Something like this, which (of course) does not work.
   for (auto it = s2.begin(); it != s2.end();   it) {
     s1.insert(std::move(*it));
   }
}

int main()
{
   unordered_set<string> s1, s2;
   // Fill first set:
   s1.insert("hello");
   s1.insert("world");
   // Fill second set.
   s2.insert("foo");
   merge_sets(s1,std::move(s2));
   // After this operation, s2 is empty and s1 contains "hello", "world" and "foo".
}

Другими словами, я хотел бы иметь возможность перемещать элементы из s2 вместо того, чтобы копировать их. Должен быть способ «извлечь» элементы из набора таким образом, чтобы элемент копировался / перемещался, а затем удалялся из текущего набора.

Ответ №1:

В текущей спецификации такой функциональности нет. Но вы не одиноки в запросе на это. Возможно, мы получим эту функциональность в будущем, но только если такие люди, как вы, поднимут много шума по поводу необходимости этого.

В выпуске 839 LWG есть комментарий с пометкой «[ 2009-09-19 Говард добавляет: ]», в котором описывается API для объединения узлов из одного контейнера на основе узла в другой. Используя ваш код, это будет выглядеть:

 void merge_sets(unordered_set<string> amp;s1, unordered_set<string> amp;amp;s2)
{
   // Something like this, which (of course) does not work.
   for (auto it = s2.begin(); it != s2.end();) {
     s1.insert(s2.remove(it  ));
   }
}

Это не потребовало бы какого-либо выделения или освобождения памяти. Это даже не потребовало бы перемещения или копирования из вашего элемента. Он буквально передает узел из одного unordered_set<string> в другой.

Сообщите представителю вашего национального органа, что вам нужна эта функциональность. Скажите comp.std.c , что вам нужна эта функциональность. Если вы не уверены, что этот API соответствует вашим потребностям, спросите меня, либо в частном порядке, либо здесь, и я уточню, если смогу.

1. Приятно слышать от кого-то, кто так вовлечен в процесс, но я думаю, что это должно быть сделано более обобщенно, чем просто «сращивание» в другой контейнер. Должен быть способ получить значение xvalue при удалении отдельного элемента из любого из контейнеров. Возможно, remove_swap функция для контейнеров, которые не позволяют изменять элементы, пока они содержатся.

2. Есть маркер «Изменить значение в std::set без затрат на перераспределение узла». Это та функциональность, которую вы хотите?

3. @Howard: Я почти уверен, что это было бы полезно само по себе, но этот вопрос, похоже, касается возможности требовать ресурсы из элемента, который уничтожается в силу удаления из набора. Я думаю, что это сделало бы его значением xvalue. Похоже, было бы полезно иметь swap_element , который удаляет ключ из хэшированной структуры поиска, меняет значение местами и повторно вставляет ключ, а также remove_swap который удаляет ключ, меняет значение местами, а затем уничтожает элемент. В любом случае ресурсы, принадлежащие элементу, будут переданы внешнему объекту.

4. auto p = m.remove(i); Key new_key = ...; swap(new_key, p->first); m.insert(std::move(p)); В вашем последнем примере просто не выполняйте вставку. p деструктор очистит ресурсы.

5. @Howard: Я полагаю, вы имели в виду erase , что нет unordered_set::remove . Но итератор, возвращаемый erase имеет const члены и не может использоваться с swap . [unord.set] указывает, что «Типы iterator и const_iterator оба являются типами постоянного итератора».

Ответ №2:

Почему бы не объединить два набора, используя один из них в качестве целевого, а не объединять их в третий, отдельный набор? Это, по крайней мере, позволило бы вам избежать копирования элементов из одного из исходных наборов (предположительно, вы бы выбрали больший).

Или, если элементы большие, вы должны хранить их косвенно, используя интеллектуальные указатели (например, boost::shared_ptr<> ), в этом случае будет легко скопировать указатели из двух источников в целевой и никогда не копировать фактический объект.

1. Я обновил исходный вопрос примером. Что касается shared_ptr<> , это, безусловно, правильное решение, но в моем случае объекты легковесны, хотя они все еще требуют выделения кучи памяти. Я хотел бы избежать дополнительных выделений, когда я мог бы перемещать объекты.

2. То, что вы ищете, существует для std::list<> (оно называется splice ), но не для других типов контейнеров. Если вы хотите избежать дополнительных выделений для самих интеллектуальных указателей, вы можете использовать Boost Intrusive для устранения этих накладных расходов.

3. Спасибо за указатель для «сращивания». Я еще раз рассмотрю Boost.intrusive, но в любом случае на данный момент я рассматриваю возможность написания собственной минимальной реализации unordered_set . Приветствия!

4. @blue: Это действительно стоит затраченных усилий? Вы измерили это и обнаружили, что это самая низкоэффективная часть вашего кода?

5. @GMan: нет, я еще этого не делал, и вы, безусловно, правы в этом. Я полагаю, что разумный путь здесь — использовать unordered_set, profile, а затем, возможно, повторно реализовать. Меня просто немного раздражает, что, похоже, в таком случае нет способа использовать семантику перемещения.

Ответ №3:

Вы не можете изменить элемент в наборе (упорядоченный или нет), потому что это нарушает гарантию уникальности.

1. Это не совсем правильно. Вы не можете изменить элемент в наборе таким образом, который изменил бы его порядок в наборе (как определено средством сравнения, используемым этим набором). Например, можно иметь mutable поля в value_type вашего набора, и тогда можно изменять эти поля в элементах внутри набора, если эти поля не используются в функции сравнения.

2. Перемещение из элемента с высокой вероятностью изменит порядок, если вы не будете предельно осторожны при определении типа элемента.