Почему итератор в наборе (C++) не работает должным образом?

Question

Это код, который я написал:

multiset<int>S; 
for(int i = 0;i<20;i++) 
S.insert(i); 
for(auto it = S.end();it!=S.begin();--it) 
cout<<*it<<" "; 
cout<<endl; 

Выход:

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 

Answer 1

Ваш код содержит некоторое неопределенное поведение. Как вы уже указали, S будет содержать все значения от 0 до 20 (эксклюзивные), хотя как-то печать дает 1 до 20 (включительно).

Ваш код:

for(auto it = S.end();it!=S.begin();--it) 
    cout<<*it<<" "; 

Проблема здесь состоит в том, что диапазон [begin, end) имеет end ссылаясь на то, что не является частью набора. Разыменование итератора, полученного от end(), может привести к сбою вашей программы или дать произвольное случайное значение. В этом случае, я думаю, вы получаете значение 20 из-за оптимизации компилятора. (Некоторая оптимизация черного ящика)

В C++ (и других языках) понятие итераторов сопровождается концепцией reverse iterators. (Если вы по ссылке, есть хорошая картина объяснения итераторы.)

В основном, при помощи обратного итераторы позволит вам петлю от задней части к началу, как если бы вы были зацикливание с нормальными итераторов:

for (auto it = S.crbegin(); it != S.crend(); ++it) 
    cout << *it << " "; 

Обратите внимание, что функции rbegin() и crbegin() не имеют недостатков в сложности кода. (если вы не хотите снова преобразовать их в передний итератор)

Бонус: По умолчанию, не используйте оператор -оператор на итераторах, он дает головные боли при попытке отладки.

Answer 2

Лучше использовать:

for(auto it = S.rbegin(); it != S.rend(); ++it) 

обновление в соответствии с комментариями.

Answer 3

Петля с итератором неверна и имеет неопределенное поведение, потому что итератор, возвращаемый функцией-членом end(), разыменован в цикле.

Действующая программа может выглядеть

#include <iostream> 
#include <set> 

int main() 
{ 
    std::multiset<int> s; 

    for (int i = 0; i < 20; i++) s.insert(i); 

    for (auto it = s.end(); it != s.begin();) std::cout << *--it << " "; 
    std::cout << std::endl; 

    return 0; 
} 

Его выход

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

Конечно, вы можете использовать обратный итератор класса, возвращаемого функцией rbegin(). Например,

#include <iostream> 
#include <set> 

int main() 
{ 
    std::multiset<int> s; 

    for (int i = 0; i < 20; i++) s.insert(i); 

    for (auto it = s.rbegin(); it != s.rend(); ++it) std::cout << *it << " "; 
    std::cout << std::endl; 

    return 0; 
} 

В этом случае петля выглядит проще.