ходьба на Сете (из STL)
Мне было интересно, стоит ли ходить на Сете (из STL) очень дорого? Мне нужен отсортированный массив, и это единственная причина, по которой я использовал Set. Должен ли я создать свой собственный отсортированный список или прогуляться по Сету — это нормально?
Решение
Нет, это не дорого (асимптотически). Согласно стандарту C ++ это выполняется за линейное время, потому что каждый шаг занимает постоянное время (амортизируется).
Хотя ходить по фактическому отсортированному массиву (например, std::vector или простой массив C) может быть немного быстрее из-за более низкой константы.
Другие решения
Других решений пока нет …