Russian Qt Forum

Qt => Общие вопросы => Тема начата: Igors от Июнь 28, 2011, 15:06



Название: В каких контейнерах данные перемещаемы ?
Отправлено: Igors от Июнь 28, 2011, 15:06
Добрый день

Помещаю элемент в контейнер, могу ли я после этого использовать адрес помещенного элемента? Пример (популярная ошибка):
Код
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 приличная структура). Есть ли какой-то общий принцип/способ определить?

Спасибо   


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: Zartul от Июль 05, 2011, 13:07
Я в таких случаях использую мутируемы итераторы в стиле 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



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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: Igors от Июль 06, 2011, 19:07
Я в таких случаях использую мутируемы итераторы в стиле 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));
 
Однако не видно никаких "официальных" подтверждений/опровержений, а полагаться на "авось" не хочется


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: brankovic от Июль 06, 2011, 23:49
Можно ещё доки к STL почитать, тоже вариант такой неплохой.


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 07, 2011, 15:39
алгоритмы STL работают только через итераторы. и даже если итератор - указатель, это лишь частный случай, а вопрос треда в другом...


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: brankovic от Июль 07, 2011, 17:09
алгоритмы STL работают только через итераторы. и даже если итератор - указатель, это лишь частный случай, а вопрос треда в другом...

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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 07, 2011, 19:36
к чему это вообще было?..


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: brankovic от Июль 07, 2011, 20:48
к чему это вообще было?..

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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 07, 2011, 21:36
общий ответ именно "нет, не можешь". возьмём в качестве примера поиск значения в списке - где гарантия того, что реализация не делает никаких отложенных перемещений/копирований самих хранимых данных, тогда как итераторы остаются нетронутыми? нет такой гарантии...
равно как и в другом случае - например, при добавлении значений в список - внутренний буффер может иметь достаточно свободного пространства для добавления значений.
скажем,
Код:
QList<T>::iterator it = list.begin();
list.prepend(T);
while (it != list.end()) ;
может как изменить list.end(), так и не тронуть его - снаружи предупредить это сложно...


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: Igors от Июль 08, 2011, 13:25
Код:
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 и потом пере-присвоить? Вообще не годится т.к порядок следования может оказаться другим


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: brankovic от Июль 08, 2011, 13:51
Igors, а почему не хотите работать с итераторами вместо указателей? В стандарте даны гарантии на валидность итераторов list, set, map, multiset/map, unordered_set/map, по размеру они от указателей не отличаются, так почему не использовать их вместо указателей?

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

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


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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 08, 2011, 14:17
Если именно "список" (последовательный доступ) то совсем др. дело. Пусть у меня есть структура
Код
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 детачнется независимо от наличия/отсутствия последующих изменений...


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: Igors от Июль 08, 2011, 16:20
В стандарте даны гарантии на валидность итераторов list, set, map, multiset/map, unordered_set/map,
Если нетрудно подскажите где. Спасибо
 
Igors, а почему не хотите работать с итераторами вместо указателей?
..
по размеру они от указателей не отличаются, так почему не использовать их вместо указателей?
Толком не понимаю, в чем разница :) Напр. итератор вернул неконстантную ссылку. Что имеется ввиду под "валидный итератор"? Что после удалений/вставок он не вылетит - хотя может вернуть уже др. ссылку? Так мне такая валидность не нужна, нужен адрес/ссылка именно тех данных что были "до того" (напр чтобы к ним сделать append). А иначе получается что валидность итератора и указателя - одно и то же. 

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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: brankovic от Июль 08, 2011, 18:35
В стандарте даны гарантии на валидность итераторов 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 назад, что итераторы не инвалидируются.


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: Igors от Июль 09, 2011, 11:07
Да, действительно, все четко написано. Напр std::map
http://www.sgi.com/tech/stl/Map.html (http://www.sgi.com/tech/stl/Map.html)
Цитировать
Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.
Спасибо


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 09, 2011, 14:31
опять-таки, это не обязательно означает, что адрес элемента останется прежним


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: brankovic от Июль 09, 2011, 15:08
опять-таки, это не обязательно означает, что адрес элемента останется прежним

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

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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 10, 2011, 08:24
лядь, там про std::map, тут откуда-то std::list::erase взялся...


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: brankovic от Июль 10, 2011, 11:02
лядь, там про std::map, тут откуда-то std::list::erase взялся...

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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 10, 2011, 14:12
лядь, там про std::map, тут откуда-то std::list::erase взялся...

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

так мб перестать "втолковывать" одно и то же кругами - про валидность и невалидность итераторов? прочтите внимательно оригинальный вопрос треда - там речь об указателях на объекты, а не об итераторах. хоть в общем случае итератор - это унифицированная надстройка над указателем на ячейку, хранящую объект, и в частном случае адрес ячейки равен адресу самого объекта, но (в зависимости от типа объекта и/или типа контейнера) адрес ячейки может быть равен адресу указателя на объект...или на слайс, или ещё на что-нибудь - я и вывел "общий ответ" выше...
далее, std::list - это банальный двунаправленный список - тут и ежу понятно, что удаление произвольной ноды никоим образом не влияет на цикл жизни остальных нод того же списка - так какой интерес всюду приводить его в пример? да и какая связь с указателями, опять же? std::map уже интереснее - там сбалансированное дерево (которое я, честно говоря, уже с трудом вспоминаю) - и вот есть в документации строка
Цитировать
Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements.
, которая, опять-таки, совершенно не проливает свет на вопрос об указателях...ладно, пустое...

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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: Igors от Июль 10, 2011, 15:52
далее, std::list - это банальный двунаправленный список - тут и ежу понятно, что удаление произвольной ноды никоим образом не влияет ..
Ежу все понятно - потому у него вместо мозгов иголки :) А где гарантия что в конкретной реализации - и.т.п. как Вы недавно рассказывали? Допустим разработчик захотел распределять ноды блоками в целях оптимизации - тогда их перемещение при удалении/вставке вполне возможно.

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


Название: Re: В каких контейнерах данные перемещаемы ?
Отправлено: ритт от Июль 10, 2011, 21:05
далее, std::list - это банальный двунаправленный список - тут и ежу понятно, что удаление произвольной ноды никоим образом не влияет ..
Ежу все понятно - потому у него вместо мозгов иголки :) А где гарантия что в конкретной реализации - и.т.п. как Вы недавно рассказывали? Допустим разработчик захотел распределять ноды блоками в целях оптимизации - тогда их перемещение при удалении/вставке вполне возможно.
в двунаправленном списке сами ноды не меняются - меняются только связи между ними. если изменение нод при удалении/вставке вполне возможно, такая реализация списка некорректна.