Есть ли причина, по которой STL не предоставляет функции для возврата итератора через индекс?

Есть ли причина, по которой STL не предоставляет функции для возврата итератора в контейнер через индекс?

Например, предположим, что я хотел вставить элемент в std::list, но в n-й позиции. Похоже, мне нужно получить итератор с помощью чего-то вроде begin() и добавить n к этому итератору. Я думаю, было бы проще, если бы я мог просто получить итератор в n-й позиции с чем-то вроде std::list::get_nth_iterator(n).

Я подозреваю, что неправильно понял принципы STL. Кто-нибудь может помочь объяснить?

Спасибо БиБэнд


c++ iterator stl
person BeeBand    schedule 14.01.2010    source источник
comment
Всем спасибо. Понятно, что я должен использовать std::vector.   -  person BeeBand    schedule 15.01.2010
comment
Использование vector<>, если у вас есть возможность и важен произвольный доступ, определенно стоит сделать. Но если произвольный доступ не более важен, чем вставка с постоянным временем (например) или если вы пишете общий код (шаблон) и не хотите заставлять пользователей использовать контейнер с итераторами произвольного доступа, std::advance() поможет.   -  person Michael Burr    schedule 15.01.2010

Ответы (4)


arrow_upward
12
arrow_downward

Вы можете использовать advance() из заголовка <iterator>:

<забастовка> list<foo>::iterator iter = advance(someFooList.begin(), n); 

list<foo>::iterator iter = someFooList.begin();

std::advance( iter, n);

Если итератор поддерживает произвольный доступ (например, vector), он будет работать достаточно эффективно, если он поддерживает только увеличение (или уменьшение) итератора, например list, он будет работать, но только настолько, насколько это возможно.

person Michael Burr    schedule 14.01.2010
comment
Приведенный выше код генерирует синтаксическую ошибку, поскольку std::advance() возвращает void. Код должен выглядеть так: iter = someFooList.begin(); advance(iter, n); - person BeeBand; 15.01.2010
comment
Извините, я написал в спешке прямо перед встречей, и, как и почти весь код, который я на самом деле не компилирую, это было неправильно. Я исправил это. std::advance() принимает ссылку на итератор, который обновляется, а не возвращает новый итератор. Вероятно, это указано для разумной поддержки таких вещей, как итераторы только для ввода (поскольку в этом случае, если advance() принимает параметр значения, а не ссылку, итератор, переданный в advance(), вернет другой элемент при разыменовании после возврата advance(). Интерфейс advance() использования делает это немного более очевидным). - person Michael Burr; 15.01.2010

arrow_upward
5
arrow_downward

std::list — это связанный список. Так что он не поддерживает произвольный доступ. Чтобы добраться до n-й позиции в списке, вы должны начать с самого начала и пройти через все узлы, пока не дойдете до n. Это довольно дорого (O(n)), и поэтому плохо иметь метод, который не предполагает таких затрат. get_nth_iterator(n) подразумевает, что итератор, указывающий на n-й узел, стоит дешево.

std::vector конечно же поддерживает это напрямую с оператором [], потому что структура данных поддерживает произвольный доступ и поэтому для него это очень недорого.

person Matt Greer    schedule 14.01.2010
comment
На самом деле, если бы get_nth_iterator() была бесплатной функцией, то это могло бы быть неэффективно. Рассмотрим std::vector<int> n; ... n.erase(std::remove(n.begin(), n.end(), 12), n.end()); - person D.Shawley; 15.01.2010
comment
Ой... извините... не понял, что get_nth_iterator() был предложенным методом std::list. - person D.Shawley; 15.01.2010

arrow_upward
2
arrow_downward

std::list не является контейнером с произвольным доступом, поэтому нет необходимости обращаться к n-му элементу. если вам это нужно, рассмотрите возможность использования вместо этого std::vector.

person nothrow    schedule 14.01.2010
comment
К сожалению, иногда есть веские причины для доступа к n-му элементу списка. Векторы и списки эффективны для разных целей, и иногда вам приходится делать разные вещи с одной и той же структурой данных. - person David Thornley; 15.01.2010

arrow_upward
1
arrow_downward

Как правило, все, что может быть дорогостоящим, делается немного неуклюжим, поэтому вы не сделаете это случайно. Используя ваш пример, с контейнером, который предоставляет итераторы произвольного доступа, это будет просто container.begin()+n, но для std::list (который предоставляет прямой итератор) вам нужно будет использовать list.begin(), а затем advance().

Если вы хотите получить Nй итератор, скорее всего, вам вообще не следует использовать std::list. Опять же, если вы начнете это предложение со слова «шансы», оно останется почти истинным...

person Jerry Coffin    schedule 14.01.2010