Russian Qt Forum

Добрый день

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

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 приличная структура). Есть ли какой-то общий принцип/способ определить?

Спасибо   

Я в таких случаях использую мутируемы итераторы в стиле 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 - где гарантия, что поведение в будущем останется индентичным? такой гарантии нет...
в качестве дополнения к общему ответу - "если нужен указатель, храни указатели"

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

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));
 

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

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

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

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

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

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

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

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

edit:

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

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

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

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

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

в 23.2.2.3 list modifiers

видим про erase:

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

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

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


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


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

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

Да, действительно, все четко написано. Напр std::map
http://www.sgi.com/tech/stl/Map.html (http://www.sgi.com/tech/stl/Map.html)
Спасибо

опять-таки, это не обязательно означает, что адрес элемента останется прежним

Там много текста было, трудно воспринимается. Ещё раз подчеркну главное. Итак, цитирую стандарт C++ о std::list::erase:

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

лядь, там про std::map, тут откуда-то std::list::erase взялся...

уж и не знаю как вам втолковать. Наверное лучше прямо стандарт почитать. Там главка есть про каждый контейнер. Если почувствуете что теряетесь, то поищите поиском слово invalidate.

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

вкратце: допустим, Igors'у изначально ну позарез нужно было хранить указатель на объект (скажем, в некотором другом контейнере), Вы ему предлагаете забыть про указатели и хранить вместо них итераторы? хорошо, общий ответ: для ряда случаев и контейнеров итераторы - то, что вам нужно; для другого ряда - не совсем то; указатели - чаще совсем не то.
консенсус? тему можно закрывать?

Ежу все понятно - потому у него вместо мозгов иголки :) А где гарантия что в конкретной реализации - и.т.п. как Вы недавно рассказывали? Допустим разработчик захотел распределять ноды блоками в целях оптимизации - тогда их перемещение при удалении/вставке вполне возможно.

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

в двунаправленном списке сами ноды не меняются - меняются только связи между ними. если изменение нод при удалении/вставке вполне возможно, такая реализация списка некорректна.