Каким требованиям должен отвечать end-итератор? Код (Text): 1. std::vector<char> v; v.end() - 1 == v.rbegin().base(); ??? --------------------------------------------------------------------- 2. std::vector<char> v; v.push_back(0); std::vector<char>::const_iterator i = v.end(); v.push_back(1); *i == 1; ??? --------------------------------------------------------------------- 3. std::vector<char> v; v.push_back(0); v.push_back(1); std::vector<char>::const_iterator i = v.rbegin().base(); v.pop_back(); i == v.end(); ??? Плюс те же вопросы для последовательных контейнеров.
1. Ошибка номер один: вектор пока пустой, и выражение v.end()-1 вызывает ошибку, потому что итератору некуда "двигаться". Ошибка номер два: v.end() == v.rbegin().base() является правильным выражением, и вычитать ничего не нужно. Плюс ещё замечание: операция вычитания числа из итератора (вот здесь: v.end() - 1) определена только для vector. Для остальных контейнеров (а лучше всегда) следует писать так: --v.end(). 2. Может работать, может и не работать - в зависимости от реализации STL. Например, в MS VS 2005 в Debug-версии вылетает assert. Ошибка - в том, что после второго push_back'а все итераторы становятся недействительны, поскольку возможно произошло перераспределение памяти, и сохранённые итераторы указывают в "никуда". 3. i сначала указывает на последний элемент (на 1), потом этот элемент удаляется, а итератор по-прежнему указывает на ту же память. В Debug-версии вылетает с ошибкой, а в Release спокойно "проглатывает". Теперь по поводу rbegin(). Вот такой код будет правильным: Код (Text): std::vector<char>::const_iterator i = v.rbegin().base(); assert (i == v.end()); Вот когда сохраняется, а когда нет действительность итераторов: Если произошла вставка элемента в контейнер, то - в vector: если произошло перераспределение памяти, то все итераторы недействительны; если перераспределения не было, то действительны итераторы, указывающие на элементы, стоящие до вставляемого - в list: все сохранённые итераторы действительны - в deque: все сохраненные итераторы становятся недействительными - в set, map: все сохраненные итераторы сохраняют свою действительность Если произошло удаление элемента, то сохраненные итераторы: - в vector: недействительны только те итераторы, которые указывали на элементы, стоящие после удаляемого - в list: становятся недействительными только те итераторы, которые указывали на удалённые элементы - в deque: все становятся недействительными - в set, map: недействительны только те итераторы, которые указывали на удалённые элементы Эти требования вполне естественны, если представлять, что эти контейнеры представляют из себя внутри. Если итератор стал недействителен, то нужно снова получить его значение из контейнера. В случае применения insert/erase, они сами возвращают новое значение итератора. Если используется push_back/pop_back, то нужно вызвать end(). Теперь по поводу reverse_iterator'ов. reverse_iterator хранит внутри себя обычный итератор. Однако операция * всегда возвращает элемент, который стоит перед элементом, на который указывает (внутренне) этот итератор. Поэтому эти два выражения эквивалентны: reverse_iterator(v.end()) и v.rbegin(). Функция base() возвращает тот самый скрытый итератор. Поэтому, хотя rbegin() указывает на последний элемент, rbegin().base() указывает на элемент за последним, т.е. равен end(). Такая странная, на первый взгляд, работа обратных итераторов легко объяснима: если end() легко положить указывающим на NULL, то для rend() подходящего значения уже не находится, и приходится считать, что внутренне rend() == begin(), а rbegin() == NULL. А вот при вызове любой функции, кроме base(), это состояние скрывается.
maxdiver Стоп, стоп, стоп... .rbegin().base() инератор на последний элемент, а .end() это итератор на ПОСЛЕ последнего. .rbegin().base() == --.end(); <- Вот ЭТО правильно! --------------------------------------------- [EDIT] ...уяссе.... Во я слажал-то. Действительно, rbegin() это end().
Так это как-то тупо получается... Получается что реверсная переборка - не симметричная?! Тогда ведь алгоритмы работать не должны.... Я требую ясности!! ) [EDIT] Разобрался. Мда..... Все это очень непонятно. Зачем сделали так что реверс и реверс.base() указывает на разные элементы. Какой в этом смысл?
Ну вот подробное объяснение (кто дочитает до конца - тот герой Смотри: begin() указывает на первый элемент, end() - за последним, а внутренне - на NULL. Теперь представим, что мы хотим реализовать reverse_iterator'ы. Но при этом мы хотим сделать их совместимыми с обычными итераторами. Более того, мы обязаны базироваться на обычных итераторах, чтобы сохранить внутренние возможности обычных итераторов (в первую очередь, отладку). Как же мы можем это сделать? Создаём член, например, current типа iterator, а вокруг него делаем некоторую обертку, которая ++ преобразует в --, и наоборот. Теперь поступим "по логике": rbegin() указывает на последний, а rend() - перед первым, т.е. на NULL. Соответствующие значения и занесём в current. Но как мы теперь объясним current'у в операции ++, что если в нём лежит NULL, то он должен перейти к первому элементу контейнера, а если он указывает на последний, то и вовсе сгенерировать исключение? Ведь это абсолютно несвойственное для iterator'а поведение (он работает как раз наоборот)! У нас остаётся два выхода: 1) copy-paste'ить весь код из итератора (очень плохо); 2) придумать более хорошее взаимодействие с iterator'ом. Мы, разумеется, выберем второй путь, тем более что ничего сложного тут нет. Пусть в current'е лежит итератор, указывающий после текущего элемента. Тогда rbegin() внутренне будет указывать на NULL, а rend() - на первый элемент. Теперь мы можем спокойно применять обычные итераторы. Разница только в том, что когда мы будем реализовывать операторы * и ->, будем возвращать значение не текущего, а предыдущего элемента. Так что всё вполне логично Разработчики STL пошли по пути наименьшего сопротивления и наибольшего соответствия принципам ООП. P.S. Зачем тебе понадобилась функция base()? Её стоит использовать только в особых случаях, когда нужно преобразовать reverse_iterator в обычный iterator. В обычном коде ты должен использовать reverse_iterator в том виде, в каком он есть. Иначе зачем создавать обратный итератор и преобразовывать его в обычный?
_DEN_ рекомендую в первую очередь обратить внимание на замечания maxdiver'а об аллокейторах. ИМХО это даже важнее чем техника обратных итераторов. Или посмотрите какую-нибудь реализацию вектора и для сравнения - красно-черного контейнера, каковы отличия при выделении памяти, где ее можно резервировать а где - нет. Нет ничего лучше чем один раз увидеть самому - и тогда ну очень многие вопросы отпадут. STL, поверьте, внутри не так страшен, как кажется с первого взгляда. Про base() - тоже неспроста замечание. Если клиент получает итераторы только через begin(), end() то ему не следует трогать base() - правда это уже философия
Если действительно захотелось изучить работу vector'а, могу предложить собственную разработку - аналог vector'а, только полностью комментированный (на уровне почти каждой строки) и немного улучшенный. Просто ИМХО изучать контейнеры по хидерам (особенно мелкософтским ) - ужасно неудобно. Ну а по остальным контейнерам - чтобы лезть в их исходники, нужно сначала представлять себе, что такое двусвязные списки и деревья. Иначе - пустая трата времени.
