_DEN_ Но по Стандарту не обязан. container.end() возвращает обычный итератор. Разве что не разыменовываемый на момент получения. Его "конечность" определяется результатом сравнения с текущим значением container.end() и ничем другим. А end() не обязан возвращать всегда один и тот же итератор.
green Тогда это противоречит утверждению о том, что последовательные итераторы остаются живыми после операции вставки/удаления
_DEN_ Впрочем, для вектора можно сделать реализацию итератора, при которой end() всегда будет возвращать один и тот же итератор. Например: class vector::iterator { vector *pMyVector_; size_t elementIndex_; // -1 для end-итератора // ... };
green Нельзя Точнее - поломается куча оптимизаций и вектор по многим параметрам скатится до листа. Придется ставить костыли в операторе сравнения итераторов, std::distanse и std::vector::at получат линейную сложность вместо константной, и еще много всего неприятного.
_DEN_ Вот-вот. Нельзя требовать от всех контейнеров абсолютно одинакового поведения - каждый заточен под что-то своё.
green: Для листа гарантируется сохранение валидности всех итераторов при push_back. green: Дело в том, нет никакого специального end-итератора, который обязательно сохраняет свой end-status независимо от состояния контейнера. Вот в этом противоречие. green Так я и не требую Мой изначальный вопрос, который кстати так и остался открытым - чем диктуется поведение сохраненного end-а после операции вставки, при условии что итератор остался валиден? ))) Мы тут уже обсудили все, кроме самого вопроса)))
_DEN_ Противоречия нет. Для list::push_back (и, с оговорками, vector::push_back) гарантируется сохранение валидности. Т.е. если итератор до push_back был валидным до push_back, то таковым и останется. А сохранение невалидности (т.е. что невалидный итератор таковым и останется) не гарантируется, конечно. Или я не понял? Т.е. почему (с точки зрения Стандарта) у вектора после вставки end_before_insert != vector.end(), а у листа == ? Из-за того, что Стандарт не требует равенства vector.end() до и после вставки, реализация вектора в целях эффективности сделана с изменяемым end(). Возможны стандарт-совместимые реализации вектора с неизменным end(), но менее эффективные. Чем не ответ?
_DEN_ По-моему ты слишком многого хочешь от С++. У меня тоже нет полноценного стандарта, только какой-то ошлёпок который вряд ли на него может претендовать, но там нет ни слова о том о чём ты пишешь. По-моему стандарт определяет только внешний интерфейс поведения. Например те же требования к итераторам. По-моему элементы вектора не обязательно должны располагать в памяти последовательно, а списка нет. Если их внешний интерфейс удовлетворяет требованиям, то почему бы и нет. А всё то, что опирается на конкретную реализацию, по-определению не корректно. Другой вопрос, что часто конкретная реализация выглядит почти как стандартная(например не POD структуры которые выглядят как POD). Думаю этот случай примерно из той же самой оперы.
green Просто в данной реализации так вышло, что end() указатель на следующий за валидным элементом массива, что является разумным и эффективным. Но никто не запрещает сделать иначе.
green end-итератор не является невалидным итератором end-итератор можно использовать в диапазонных алгоритмах, но нельзя разыменовывать. Невалидный итератор нельзя разыменовывать и нельзя использовать в алгоритмах. У end-итератора особый статус. Ну вот об этом-то и речь. Можешь ткнуть в стандарте где именно сказано, что "вот тут равенство требуется, а вот тут - не требуется"? Booster На счет C++98 не уверен, но начиная с C++2003 точно стандарт требует непрерывности буффера вектора. Стандарт - это 1000 страниц текста мелким шрифтом. Он определяет очень многие вещи в самых мельчайших подробностях.
_DEN_ У меня около 800 не очень мелкого, и по-моему стандарт многие вещи даже в новых версиях оставляет на усмотрение. Если так то звиняйте, у меня кусок от 98. ^) Интересно с чего это вдруг решили залезть внутрь реализации? И он требует, чтобы итераторы располагались строго последовательно тоже?
Booster Ну если стандарт говорит о какой-то конкретной модели памяти (или семействе моделей), то требование в общем-то вполне себе ничего. Кстати та же самая непрерывность гарантируется у std::basic_string::c_str(), std::basic_string::data и, если не ошибаюсь, у любого &*std::basic_string:const_)iterator. Не совсем понял, что значит "итераторы располагаются последовательно"?. std::vector:const_)iterator имеет оператор "меньше". Между элементами дырок (выравнивания) нет.
_DEN_ Да, согласен, не стоит причислять его к невалидным. Но сохранение end-status тоже не гарантируется. Для операции вставки Стандартом явно гарантируется только сохранение валидности прежде валидных итераторов. Сюда вполне вписывается и end-iterator, который, кроме сохранения валидности, после вставки может приобрести ещё разыменовываемость. AFAIK, Стандарт не накладывает никаких ограничений на значение end() кроме вот этого: Значит реализации позволяется делать end() изменяемым.
_DEN_ Этому могу дать объяснение, только желанием работать с вектором как и с обычным массивом. Но тогда это накладывает ограничение и на сам этот массив, необходимо чтобы он точно соответствовал своей обычной реализации. Но всё-таки не понятно зачем это было сделано, вектор нисколько не уступает по эффективности обычному массиву. Не корректно выразился. Имел ввиду последовательность соответствующих элементов данных.
Booster Ты про это? ЗЫ: _DEN_ - приношу извинения, что тоже влез с обсуждением реализации, а не стандарта, но очень любопытно узнать на чём основано такое интересное замечание Booster.
Y_Mur Вектор действительно нисколько не уступает по эффективности обычному массиву. Единственное что я не понял - это к чему это было сказано
Booster Полагаю, для того, чтобы позволить делать нечто вроде: Код (Text): memcpy(pRawBuffer, &v[0], v.size() * sizeof(vector::value_type));
_DEN_ Код (Text): int testArray[100]; for (int i = 0; i<100; i++) testArray[i] = i; vector <int> v1( 100 ); for (int i = 0; i<100; i++) v1[i] = i; компилится MSVC 9 /RELEASE /O2 в: Код (Text): testArray[i] = i; 00401021 mov dword ptr [esp+eax*4+28h],eax ... v1[i] = i; 00401060 mov edx,dword ptr [esp+1Ch] 00401064 sub edx,dword ptr [esp+18h] 00401068 sar edx,2 0040106B cmp esi,edx 0040106D jb wWinMain+71h (401071h) 0040106F call edi 00401071 mov eax,dword ptr [esp+18h] 00401075 mov dword ptr [eax+esi*4],esi Конечно соглашусь, что накладных расходов относительно немного, но до "не уступает по эффективности" несколько не дотягивает, тем более что практическая ситуация когда дополнительная проверка каждого элемента точно не нужна, а скорость критична не такая уж и редкость.
