В каких контейнерах данные перемещаемы ?

[Igors]

Добрый день

Помещаю элемент в контейнер, могу ли я после этого использовать адрес помещенного элемента? Пример (популярная ошибка):

Код

C++ (Qt)
QVector <int> vec;
vec.push_back(123);
int * myPtr = &vec.back();
 

myPtr будет валиден до следующего добавления/удаления в/из вектора, потом может быть валиден или нет и когда - зависит от реализации. То есть для std::vector (QVector) общий ответ "нет, не могу".  Для std::list ответ "могу". Для QList "могу если sizeof(T) > sizeof(void *)". Но я затрудняюcь ответить для std::set, std::map, QMap и многих других. Конечно я всегда могу хранить указатели в value - но это лишние движения. Да и расходы на перемещение могут быть значительны (если value приличная структура). Есть ли какой-то общий принцип/способ определить?

Спасибо   

[Zartul]

Я в таких случаях использую мутируемы итераторы в стиле java

Код

C++ (Qt)
QMutableListIterator< T >
QMutableLinkedListIterator< T >
QMutableVectorIterator< T >
QMutableSetIterator< T >
QMutableMapIterator< Key, T >
QMutableHashIterator< Key,  T>

если при помощи такого итератора сослаться на элемент контейнера, то при добавлении/удалении данных из контейнера
итератор будет валиден, главное перед использованием итератора проверить есть ли еще данные на которые он ссылается.
Это делается ф-ями (см. ассистент):

Код

C++ (Qt)
bool hasNext () const
bool hasPrevious () const

[ритт]

общий ответ: "нет, не можешь".
в том же QList есть ряд исключений, когда объект приходится пересоздавать. а если исходить из позиции "я смотрел исходники - однозначно могу", то это - стрелять себе в ногу...я вот сейчас как-раз колдую над рядом оптимизаций для QList в 5.0 - где гарантия, что поведение в будущем останется индентичным? такой гарантии нет...
в качестве дополнения к общему ответу - "если нужен указатель, храни указатели"

[Igors]

Я в таких случаях использую мутируемы итераторы в стиле java

Ну валидны ли остаются итераторы - это уже все-таки другой вопрос. Меня интересует незатейливый указатель/ссылка, напр.

Код

C++ (Qt)
iterator it = theMap.find("First");
if (it != theMap.end()) {
 MyValue * val = &it->second;  // ну или ссылка
 ...
 // здесь мне надо что-то удалить (или добавить) в theMap
 // конечно с ключом  отличным от "First"
 ... 
 // так что, здесь я опять обязан сделать find чтобы обновить val ?
 it = theMap.find("First");
 // и.т.д
 // неприятно т.к. find - операция не бесплатная, да и забыть легко
}
 

Вроде получается что если в контейнер можно добавлять "парой" то данные не перемещаются при
удалении/вставке, напр

Код

C++ (Qt)
theMap.insert(std::make_pair(key, val));
 

Однако не видно никаких "официальных" подтверждений/опровержений, а полагаться на "авось" не хочется

[brankovic]

Можно ещё доки к STL почитать, тоже вариант такой неплохой.

[ритт]

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

[brankovic]

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

Если написано в доке, что итератор не инвалидируется, то и указатель стало быть тоже, в чём разница-то принципиальная?

[ритт]

к чему это вообще было?..

[brankovic]

к чему это вообще было?..

к тому, что общий ответ не "нет, не можешь", а "можешь, если и только если не ивалидируется итератор"

[ритт]

общий ответ именно "нет, не можешь". возьмём в качестве примера поиск значения в списке - где гарантия того, что реализация не делает никаких отложенных перемещений/копирований самих хранимых данных, тогда как итераторы остаются нетронутыми? нет такой гарантии...
равно как и в другом случае - например, при добавлении значений в список - внутренний буффер может иметь достаточно свободного пространства для добавления значений.
скажем,

Код:

QList<T>::iterator it = list.begin();
list.prepend(T);
while (it != list.end()) ;

может как изменить list.end(), так и не тронуть его - снаружи предупредить это сложно...

[Igors]

Код:

QList<T>::iterator it = list.begin();
list.prepend(T);
while (it != list.end()) ;

может как изменить list.end(), так и не тронуть его - снаружи предупредить это сложно...

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

возьмём в качестве примера поиск значения в списке - где гарантия того, что реализация не делает никаких отложенных перемещений/копирований самих хранимых данных, тогда как итераторы остаются нетронутыми? нет такой гарантии...

Если именно "список" (последовательный доступ) то совсем др. дело. Пусть у меня есть структура

Код

C++ (Qt)
struct CTest {
 float mSquare;
 int mNomer;
 ...
};
 
std::list <CTest> theList;
 

Надо пройтись по theList и сделать так:

- если mSquare > 100 - разбить на 2 (которые поместить в хвост а сам элемент удалить)
- если mSquare < 1 - "слить" элемент с предыдущим пока общая mSquare не превысит напр 4

Что я должен делать если "нет, не можешь"? Определить std::list <CTest *>? Так это заботы с созданием/удалением. Копировать в новый list и потом пере-присвоить? Вообще не годится т.к порядок следования может оказаться другим

[brankovic]

Igors, а почему не хотите работать с итераторами вместо указателей? В стандарте даны гарантии на валидность итераторов list, set, map, multiset/map, unordered_set/map, по размеру они от указателей не отличаются, так почему не использовать их вместо указателей?

edit:

Надо пройтись по theList и сделать так:

- если mSquare > 100 - разбить на 2 (которые поместить в хвост а сам элемент удалить)
- если mSquare < 1 - "слить" элемент с предыдущим пока общая mSquare не превысит напр 4

С такой задачей std::list справится на ура, какая проблема? Вообще если рассматривается вариант "скопировать в другой контейнер, поколбасить и вернуть", то зачем тогда вообще обсуждать общий случай, ведь можно воспользоваться хорошим (частным) контейнером, подходящим под задачу.

[ритт]

Если именно "список" (последовательный доступ) то совсем др. дело. Пусть у меня есть структура

Код

C++ (Qt)
struct CTest {
 float mSquare;
 int mNomer;
 ...
};
 
std::list <CTest> theList;
 

Надо пройтись по theList и сделать так:

- если mSquare > 100 - разбить на 2 (которые поместить в хвост а сам элемент удалить)
- если mSquare < 1 - "слить" элемент с предыдущим пока общая mSquare не превысит напр 4

Что я должен делать если "нет, не можешь"? Определить std::list <CTest *>? Так это заботы с созданием/удалением. Копировать в новый list и потом пере-присвоить? Вообще не годится т.к порядок следования может оказаться другим

в данном примере можно как-раз таки итераторами (хоть std::list<CTest>, хоть QList<CTest>). не помню как там в std::list, а в QList итератор - это указатель на позицию в массиве => std::swap() или QList::swap() на двух итераторах обменяют значения сразу в векторе. один минус с итераторами - QList детачнется независимо от наличия/отсутствия последующих изменений...

[Igors]

В стандарте даны гарантии на валидность итераторов list, set, map, multiset/map, unordered_set/map,

Если нетрудно подскажите где. Спасибо
 

Igors, а почему не хотите работать с итераторами вместо указателей?
..
по размеру они от указателей не отличаются, так почему не использовать их вместо указателей?

Толком не понимаю, в чем разница Напр. итератор вернул неконстантную ссылку. Что имеется ввиду под "валидный итератор"? Что после удалений/вставок он не вылетит - хотя может вернуть уже др. ссылку? Так мне такая валидность не нужна, нужен адрес/ссылка именно тех данных что были "до того" (напр чтобы к ним сделать append). А иначе получается что валидность итератора и указателя - одно и то же. 

С такой задачей std::list справится на ура, какая проблема? Вообще если рассматривается вариант "скопировать в другой контейнер, поколбасить и вернуть", то зачем тогда вообще обсуждать общий случай, ведь можно воспользоваться хорошим (частным) контейнером, подходящим под задачу.

Знаю что std::list справится А напр std::map? A QHash? Почему? Откуда это видно? Общий ответ "нельзя потому что не гарантируется, подробности реализации.." конечно правилен, но как с (тем или иным) конкретным контейнером (не каждый же раз колбасить дубликаты).

[brankovic]

В стандарте даны гарантии на валидность итераторов list, set, map, multiset/map, unordered_set/map,

Если нетрудно подскажите где. Спасибо

В стандарте есть описание каждого метода каждого контейнера. Например

в 23.2.2.3 list modifiers

видим про erase:

Effects: Invalidates only the iterators and references to the erased elements.

Заметьте и про ссылки упомянуто. И так про каждый метод можно найти. Мнемонически запоминается так -- все контейнеры на нодах (list, set, map) -- итераторы/ссылки/указатели инвалидируются только при удалении элементов на которые они указывают. В deque только при вставках/удалениях в/из середины. В векторе при любой вставке, но не при удалении из конца.
 

Что имеется ввиду под "валидный итератор"?

валидный, это тот, который не претерпел инвалидации согласно правилам стандарта, т.е. не невалидный итератор. Как следствие его поведение определено. Но на самом деле эта формалистика затуманивает суть. Стандарт это лишь систематическое описание 'разумной реализации' простейшего контейнера с данными O по каждой операции.

Так мне такая валидность не нужна, нужен адрес/ссылка именно тех данных что были "до того" (напр чтобы к ним сделать append). А иначе получается что валидность итератора и указателя - одно и то же.

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

Знаю что std::list справится А напр std::map? A QHash? Почему? Откуда это видно? Общий ответ "нельзя потому что не гарантируется, подробности реализации.."

Это вас Константин запугал просто. На самом деле stl очень хорошо определена, и ей действительно можно пользоваться не боясь значительных подводных камней. Вот QHash я бы побоялся, но опять же, в доке к нему должен быть освещён этот вопрос.

Кстати, в стандарте это прочёл только сегодня. Всегда по stl пользовался online докой по запросу sgi stl в гугле. Там очень кратко и чётко, я там и прочитал лет 5 назад, что итераторы не инвалидируются.