STL итератор перед std :: map :: begin ()

Question

STL итератор перед std :: map :: begin ()

В C ++ 11 std::mapесть ли действительный итератор Икс такой что ++Икс гарантировано равно map::begin()? Я хотел бы обнаружить, если функция, которую я только что вызвал (моя), вывела итератор из передней части функции. Функция переместит итератор ровно на одну позицию назад.

Ответ остался для остальной части библиотеки?

5

c++c++11 iterator reverse-iterator stl

Решение

Другие решения

Очень важно понимать, что контейнеры стандартной библиотеки являются полуоткрытыми [begin, end)то есть вы можете повторять один за другим. Для двунаправленных (и случайных) итераторов вы также можете сделать --end() и вернись с края. Разыменование один за другим *end() является неопределенным поведением и поэтому уменьшает начальный итератор на --begin() или же begin() - 1, Есть только одно исключение: std::forward_list который имеет неотменяемый итератор before_begin() это удовлетворяет ++before_begin() == begin() (но учтите, что для forward_list Вы не можете уменьшить begin() или).

Эта фундаментальная асимметрия для двунаправленных итераторов означает, что обратные итераторы являются тонкими обертками вокруг обычных итераторов. В большинстве реализаций стандартной библиотеки они просто содержат копию base_ итератора нижележащего. Увеличение std::reverse_iterator называет что-то вроде --base_; return *this;и разыменование
оно делает auto old = base_; return *--old;, Ни при каких условиях базовый итератор не уменьшается до begin()и без разыменования end() сделано так.

Ниже приведены четыре способа перебора контейнера, поддерживающего двунаправленные или случайные итераторы, и отношения между различными итераторами (.base() преобразует std::reverse_iterator вернуться к своему базовому итератору)

#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <string>

int main()
{
auto c = std::map<int, std::string>{ {1, "hello"}, {2, "world"} };

{   // 1) forward iteratation
auto it = begin(c);
for (; it != end(c); ++it){}
std::cout << std::boolalpha << (it == c.rbegin().base()) << "\n";
}

{   // 2) meh, backward iteration
auto it = end(c);
for (; it != begin(c); --it){}
std::cout << std::boolalpha << (it == c.rend().base()) << "\n";
}

{   // 2') better: reverse iteration
auto it = c.rbegin();
for (; it != c.rend(); ++it){}
std::cout << std::boolalpha << (it.base() == begin(c)) << "\n";
}

{   // 1') backward reverse, better avoid this
auto it = c.rend();
for (; it != c.rbegin(); --it){}
std::cout << std::boolalpha << (it.base() == end(c)) << "\n";
}
}

Живой пример

Если у вас есть структура данных, которая должна поддерживать двунаправленную итерацию, но нет итераторов-членов .rbegin() или же rend()Вы можете легко определить их самостоятельно std::reverse_iterator(end()) а также std::reverse_iterator(begin())соответственно (это также способ, которым стандартная библиотека обычно реализует их).

3

Под «иди итератором вперед» я предполагаю, что вы уменьшаете прямой итератор примерно так:

// don't do this:
for(it = mymap.end(); --it >= mymap.begin(); ) { ... }

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

// this is better:
for(it = mymap.rbegin(); it != mymap.rend(); ++it) { ... }

-Джесси

1

Источник

Accepted Answer

Нет, итераторы перед началом в std все контейнеры UB (кроме обратных итераторов, которые, вероятно, не решат вашу проблему).

Возможно, вам нужно исправить данную функцию. В противном случае оберните его и поймайте плохое поведение, прежде чем вызывать его. В противном случае вы можете вставить отрицательный элемент бесконечности в map Порядок ввода типа ключа и добавление часового значения. В противном случае вы могли бы написать адаптеры итератора, которые обернут map итераторы с теми, которые могут идти один перед началом без UB.

Они заказаны в моем порядке рекомендации, примерно. У каждого есть способы, которыми он может потерпеть неудачу, и они становятся более подверженными ошибкам и опасными, поскольку моя рекомендация становится более отдаленной.

4