Как упорядоченные контейнеры STL узнают свой конец?

Я знаю, что стандарт не определяет способ реализации контейнеров STL, а устанавливает набор требований для каждого из них.

Однако широко известно, что упорядоченные контейнеры STL обычно реализуются в виде красно-черных деревьев< /а>.

Вы можете перебирать элементы std::set или std::map, используя соответствующие итераторы, или, начиная с C++11, используя циклы с ранжированием.

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

Я знаю, что стандарт диктует §23.2.1/c Общие требования к контейнерам (Выделение мое):

begin() возвращает итератор, ссылающийся на первый элемент в контейнере. end() возвращает итератор, который представляет собой последнее значение для контейнера. Если контейнер пуст, то begin() == end();

Хорошо, для смежных контейнеров это легко сделать, но как материализовать это «за концом» для деревьев?


c++ c++11 stl stdmap stdset
person 101010    schedule 11.11.2015    source источник
comment
Поймите, что прошлое-конец — это логическое понятие, а не физическое. Это буквально означает итератор, который вы получаете, когда проходите мимо последней допустимой записи, но внутреннее содержимое этого итератора может быть любым.   -  person Mark Ransom    schedule 11.11.2015
comment
Существует естественное понятие next() и end() из завершающих обходов дерева, таких как обход в ширину и в глубину, поэтому в соответствующих итераторах нет ничего концептуально особенного.   -  person decltype_auto    schedule 11.11.2015
comment
@MarkRansom Честно говоря, это логичная концепция. Но как реализовать такую ​​логическую концепцию? Я имею в виду в коде.   -  person 101010    schedule 12.11.2015
comment
Я предполагаю, что моя точка зрения заключалась в том, что это совершенно произвольно. В зависимости от точной реализации дерева может быть естественный и очевидный способ сделать это, но я подозреваю, что вы найдете столько разных способов сделать это, сколько существует реализаций стандартной библиотеки.   -  person Mark Ransom    schedule 12.11.2015

Ответы (2)


arrow_upward
9
arrow_downward

Я только что проверил реализацию контейнера map в Visual Studio 2013 STL, и вот как реализован end. Когда создается map, выделяется головной элемент дерева RB, и этот элемент объявляется концом контейнера.

Когда вы проходите контейнер через допустимый итератор, operator++ и operator-- просто пропускают элемент head. И когда вы достигаете последнего элемента дерева и увеличиваете итератор, он карабкается вверх (ища правильное поддерево) и в конечном итоге достигает головы дерева, которая равна end.

person AlexStepanov    schedule 11.11.2015

arrow_upward
3
arrow_downward

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

person Billy ONeal    schedule 11.11.2015
comment
Я не могу найти место в стандарте, которое подразумевает, что std::map::end() или std::set::end() должны возвращать уменьшаемый итератор. То, что вы говорите, верно для basic_string, array, deque, list и vector, но ОП спрашивал о set и map. - person Андрей Беньковский; 11.11.2015
comment
@АндрейБеньковский: N4527 23.2.1 [container.requirements.general]/12: Если не указано иное, [...]вызов функции-члена контейнера [...] не должен делать недействительными итераторы или изменять значения объектов внутри этого контейнер. -- и map::insert явно не указывает обратное. 23.2.4 [associative.reqmts]/9: Члены вставки и размещения не должны влиять на действительность итераторов и ссылок на контейнер, а члены стирания должны делать недействительными только итераторы и ссылки на стертые элементы. - person Billy ONeal; 11.11.2015
comment
@АндрейБеньковский: В частности, это НЕ верно для basic_string, deque или vector - в тех случаях, если перераспределение запускается итераторами вставки, а ссылки становятся недействительными. И вы не можете вставить в array, так что это не очень важно здесь. - person Billy ONeal; 11.11.2015