Какова временная сложность получения максимального ключа std :: map в C ++?

Question

Я пытаюсь найти наибольшее значение в std::map, которое будет последним узлом в дереве (поскольку ключи std::map отсортированы).

Cppref говорит, что std::map.end() - это постоянное время. Но чтобы получить самый большой ключ, я должен получить предыдущее значение этого итератора, то есть *std::prev(std::map.end()).

Какова временная сложность этой операции?

Я понимаю, что это должно быть эквивалентно --std::map.end(), но я также не знаю стоимость этой операции.

Answer 1

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

std::prev равно , а не эквивалентно --std::map.end(), хотя последний не гарантирует ничего полезного. См. std::prev документы.

Answer 2

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

Какова временная сложность этой операции?

Все std::map.end, std::prev(a_std_map_iterator) и std::map::iterator::operator* являются постоянными операциями. Следовательно, это выражение является константой в целом.

Обратите внимание, что сложность std::prev гарантированно будет максимально линейной с точки зрения второго аргумента n, который по умолчанию равен 1. Когда n является постоянным, std::prev в целом является постоянным.

Answer 3

Используйте взамен std::map::rbegin(), что:

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

и

Сложность

Constant.

где последнее слово должно звучать как музыка в ваших ушах.

---

std::prev(std::map.end()) - константа в сложности.

---

Более того, ваше понимание эквивалентности неверно.

С std::prev примечания:

Хотя выражение --c.end() часто компилируется, оно не гарантированно сделает это: c.end() является выражением rvalue, и есть нет требования к итератору, которое указывает, что уменьшение значения гарантированно работать. В частности, когда итераторы реализованы как указатели, --c.end() не не компилируются, а std::prev(c.end()) делает.