Почему push_back в std:: list меняет обратный итератор, инициализированный rbegin?

В соответствии с некоторыми документами STL, которые я нашел, вставка или удаление элементов в std:: list не делает недействительными итераторы. Это означает, что разрешено перебирать список (от begin() до end()), а затем добавлять элементы с помощью push_front.

Например, в следующем коде я инициализирую список с элементами a, b и c, затем перебираю его и выполняю push_front элементов. Результатом должен быть cbaabc, и именно это я получаю:

std::list<std::string> testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

for (std::list<std::string>::iterator itList = testList.begin(); itList != testList.end(); ++itList)
   testList.push_front(*itList);

for (std::list<std::string>::const_iterator itList = testList.begin(); itList != testList.end(); ++itList)
   std::cout << *itList << std::endl;

Когда я использую обратные итераторы (цикл от rbegin() до rend()) и используйте push_back, я бы ожидал подобного поведения, то есть результата abccba. Однако я получаю другой результат:

std::list<std::string> testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

for (std::list<std::string>::reverse_iterator itList = testList.rbegin(); itList != testList.rend(); ++itList)
   testList.push_back(*itList);

for (std::list<std::string>::const_iterator itList = testList.begin(); itList != testList.end(); ++itList)
   std::cout << *itList << std::endl;

Результат не abccba, а abcccba. В этом случае добавляется еще один c.

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

Я тестировал это как с Visual Studio 2010, так и с GCC, и оба возвращали тот же результат.

Это ошибка? Или какое-то странное поведение обратных итераторов, о которых я не знаю?

Ответ 1

В стандарте говорится, что итераторы и ссылки остаются действительными во время вставки. Он ничего не говорит об обратных итераторах.: -)

reverse_iterator, возвращаемый rbegin(), внутренне содержит значение end(). После push_back() это значение, очевидно, будет не таким, как было раньше. Я не думаю, что стандарт говорит, что это должно быть. Очевидные альтернативы включают предыдущий последний элемент списка или его конец, если это фиксированное значение (например, часовое устройство node).

Технические данные: значение, возвращаемое rend(), не может указывать перед begin(), потому что это неверно. Поэтому было решено, что rend() должно содержать значение begin(), а все остальные обратные итераторы будут сдвинуты на одну позицию дальше. operator* компенсирует это и в любом случае получает доступ к правильному элементу.

Первый абзац 24.5.1. Итераторы обратного хода говорят:

Шаблон класса reverse_iterator - это адаптер итератора, который выполняет итерацию с конца определенной последовательности его базовым итератором до начала этой последовательности. Фундаментальное соотношение между обратным итератора и его соответствующего итератора я устанавливается тождеством: &*(reverse_iterator(i)) == &*(i - 1).

Ответ 2

Я думаю, чтобы понять это, лучше всего начать с повторения цикла for как цикл while:

typedef std::list<std::string> container;

container testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

container::reverse_iterator itList = testList.rbegin(); 
while (itList != testList.rend()) {
    testList.push_back(*itList);
     ++itList;
}

Кроме того, мы должны понимать, как работает reverse_iterator вообще. В частности, reverse_iterator действительно указывает на элемент после того, который вы получите, когда вы разыщите его. end() дает итератор сразу после конца контейнера, но для таких вещей, как массивы, нет определенного способа указать непосредственно перед началом контейнера. Вместо этого у С++ начинается запуск итератора сразу после завершения и прогресс до начала, но когда вы разыгрываете его, вы получаете элемент непосредственно перед тем, где он на самом деле указывает.

Это означает, что ваш код действительно работает следующим образом:

После этого вы получаете почти то, что ожидаете, отбрасывая B, а затем A, чтобы вы попали в ABCCCBA.

Ответ 3

Попробуйте использовать итератор для обоих. Попробуйте:

std::list<std::string>::iterator i = testList.end();

и обратный через --i