Как получить итератор на элемент vector
Перейти к содержимому

Как получить итератор на элемент vector

  • автор:

Операции с векторами в STL

Размер вектора можно узнать при помощи универсального метода size() , возвращающего для всех контейнеров в STL их размер. Также есть метод empty() , возвращающий логическое значение ( true , если вектор пустой).

Размер вектора можно изменить в любой момент, при помощи метода resize . У этого метода может быть один или два параметра. Вызов метода resize(n) изменяет размер вектора до n элементов (длина вектора может как уменьшится, так и увеличиться). Вызов метода resize(n, val) изменяет размер вектора до n элементов, и если при этом размер вектора увеличивается, то новые элементы получают значение, равное val.

Очень часто бывает полезно добавлять элементы в конец вектора по одному и удалять элементы из конца вектора по одному. Для добавления нового элемента, равного val в конец вектора используется метод push_back(val) . Для удаления последнего элемента вектора используется метод pop_back() — он не возвращает значения.

Добавление элемента в конец вектора осуществляется в среднем за O(1). Это реализовано за счет того, что память для хранения элементов вектора выделяется “с запасом”, то есть можно будет добавлять элементы по одному, пока не кончится запас памяти. Если запас памяти исчерпан, выделяется новая память, при этом «запас» размера вектора удваивается.

Очистить вектор можно при помощи метода clear() .

Вставка и удаление элементов в середину вектора

Для удаления и вставки элементов в середину вектора используются методы erase и insert . В качестве параметра им нужно передавать итератор, поэтому просто покажем на примере, как их использовать.

Итератор — специальный объект, указывающий на элемент вектора (или другой структуры данных). Итератор на элемент с индексом i можно получить при помощи выражения a.begin() + i . Кроме того, можно при помощи итератора a.end() “отсчитывать” элементы, начиная с конца. При этом a.end() будет итератором на элемент, следующий за последним, a.end() будет итератором на последний элемент, то есть то же самое, что a.begin() + a.size() — 1 , a.end() — 2 — второй элемент с конца и т.д.

Удаление элементов: метод erase

Метод erase позволяет удалять из середины вектора один или несколько элементов. Если вызвать метод erase с одним параметром–итератором, то будет удален соответствующий элемент из вектора, то есть для удаления элемента с индексом i из вектора a нужно вызвать метод следующим образом:

a.erase(a.begin() + i);

Методу erase передать два итератора на начало и конец удаляемого фрагмента, например:

a.erase(a.begin() + i, a.begin() + j);

В этом случае будут удалены элементы с индексами от i (включительно) до j не включительно, то есть элементы a[i] , a[i + 1] , . a[j — 1] . Всего будет удалено j — i элементов.

Методу erase можно передавать и итераторы, полученные относительно итератора end . Например, удалить из вектора три последних элемента можно так:

a.erase(a.end() - 3, a.end());

Подробней про его использование можно прочитать в документации.

Вставка элементов: метод insert

Метод insert позволяет вставлять в середину вектора новый элемент, или несколько равных элементов, или другой вектор, или фрагмент другого вектора. Этот метод также работает с итераторами и про его использование можно прочитать в документации.

Примеры использования метода insert :

Вставка одного элемента со значением val в позицию с индексом i :

a.insert(a.begin() + i, val);

Вставка нескольких равных (количеством count ) элементов со значением val в позицию с индексом i :

a.insert(a.begin() + i, count, val);

Вставка в вектор a в позицию с индексом i фрагмент вектора b с индексами от start включительно до finish не включительно:

a.insert(a.begin() + i, b.begin() + start, b.begin() + finish);

В качестве параметром могут использоваться произвольные итераторы. Рассмотрим несколько примеров:

Весь вектор b добавить в конец вектора a :

a.insert(a.end(), b.begin(), b.end());

Последние 5 элементов вектора b вставить в начало вектора a :

a.insert(a.begin(), b.end() - 5, b.end());

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

Присваивание и сравнение векторов

Содержимое одного вектора можно целиком скопировать в другой вектор при помощи операции присваивания. При этом размер вектора A автоматически изменится и будет равен размеру вектора B . A = B .

Также векторы можно сравнивать на равенство и неравенство ( A == B , A != B ), и сравнивать их содержимое в лексикографическом порядке ( A < B , A B , A >= B ).

Как получить итератор элемента std::vector?

есть функция добавления Item* в item_list, которая должна возвращать
итератор только-что вставленного элемента:

vector::iterator AddItem(Item* pItem)
<
item_list.push_back(pItem);
vector::iterator i = item_list.end(); i—;
return i;
>

Дальше делаю следующим образом:

Item item1, item2, item3;
vector::iterator i1 = AddItem(&item1);
vector::iterator i2 = AddItem(&item2);
vector::iterator i3 = AddItem(&item3);

В результате получаю, что итераторы i1 и i2 невалидны. С третьим все в порядке.
Я знаю что, делаю что-то неправильно, но не могу понять что. На первый взгляд все выглядит
безобидно, но и нихрена неработает.
Вообще по задумке итератор мне нужен для того, чтобы потом удалить элемент из вектора.

Помогите плиз правильно реализовать функцию AddItem! Проект стоит.
И еще вопрос: после сортировки вектора, эти итераторы, полученные с помощью ф-ии AddItem
будут вылидны?

Спасибо за внимание.

#1
14:03, 6 авг 2005

plastik
>И еще вопрос: после сортировки вектора, эти итераторы, полученные с помощью ф-ии AddItem
будут вылидны?
Нет, конечно.

Перепиши свою логику работы с вектором. Вектор — это просто массив. Если хочешь запомнить позицию элемента, сохрани индекс.

И ещё, не самый хороший и безопасный стиль — хранить в векторе глупые указатели.

#2
14:08, 6 авг 2005

plastik
RTFM
После вставки элемента в вектор итераторы становятся невалидными.
Если планируется удаление элементов из середины контейнера, вектор не годится. Используй std::deque или std::list.

#3
14:24, 6 авг 2005

_loki_
Если планируется удаление элементов из середины контейнера, вектор не годится. Используй std::deque или std::list.
Я изначально и планировал использовать list. Но необходимо будет сортировать этот список указателей.
И здесь я зашел в тупик с критерием сортировки.
В книге я нашел std::list::sort(Cmp). Как ей пользоваться?

#4
14:26, 6 авг 2005

cppguru
Если хочешь запомнить позицию элемента, сохрани индекс.

Как я догадываюсь, после сортировки этот индекс тоже будет невалидным?

#5
14:34, 6 авг 2005

_loki_
>Используй std::deque
deque не гарантирует валидность указателей при добавлении элементов в него.

plastik
>В книге я нашел std::list::sort(Cmp). Как ей пользоваться?
так же как и обычной сортировкой. например используя функторы. ну или boost::lambda

cppguru
>И ещё, не самый хороший и безопастный стиль — хранить в векторе глупые указатели.
ну смотря для каких целей и когда. в некоторых ситуациях оверхед от хранения умных указателей бывает слишком большим. например, если идет активная сортировка большого массива указателей каждый кадр, при этом все происходит в многопоточной среде. те же boost::shared_ptr приводят к сильным тормозам.

#6
14:37, 6 авг 2005

plastik
>Как я догадываюсь, после сортировки этот индекс тоже будет невалидным?
гы. вполне валидным )
количество элементов же в векторе не изменется и наверняка этот индекс будет в пределеах [0; vec.size)
а вообще как ты представляешь что бы переменная типа int сама менялась во время сортировки какого-то там контейнера? :)))

#7
14:39, 6 авг 2005

plastik
>Я изначально и планировал использовать list. Но необходимо будет сортировать этот список указателей
std::multiset ?

#8
14:40, 6 авг 2005

CyberZX
так же как и обычной сортировкой. например используя функторы

Ну функторы для std::sort я писал. Только такие функторы не подходят для std::list::sort.
она требует greater. вообщем я в STL пока полный бум-бум 😉
Напиши пжалста коротенький примерчик функтора для std::list::sort если не жалко?

#9
14:46, 6 авг 2005

CyberZX
гы. вполне валидным )
количество элементов же в векторе не изменется и наверняка этот индекс будет в пределеах [0; vec.size)

только он будет указывать уже не на тот элемент, который нужен

а вообще как ты представляешь что бы переменная типа int сама менялась во время сортировки какого-то там контейнера? :)))

#10
14:47, 6 авг 2005

plastik
>Ну функторы для std::sort я писал. Только такие функторы не подходят для std::list::sort. она требует greater
Бред, все функторы используются совершенно единообразно. Используешь либо стандартные (less, greater, . либо пишешь свой).

CyberZX
>ну смотря для каких целей и когда.
Конечно, всё в жизни бывает, но до тех пор, пока профайле не подтвердил, что это существенно влияет на скорость работы программы, имхо нет повода портить ОО-дизайн ;).

#11
14:49, 6 авг 2005

plastik
>Ну функторы для std::sort я писал. Только такие функторы не подходят для std::list::sort. она требует greater
ИМХО тебе следует почитать литературу по STL. хотя бы того же Страуструпа

>Напиши пжалста коротенький примерчик функтора для std::list::sort если не жалко?

struct my_sort_predicate : std::binary_functionconst Item*, const Item*, bool> < bool operator( )( const Item* lhs, const Item* rhs) const < return lhs->some_value  rhs->some_value; // сортирует по значению Item::some_value > > . std::listItem*> list; // наполняем список list.sort( my_sort_predicate( ));

#12
14:52, 6 авг 2005

Ф-я vector::end() возвращает не последний элемент, а элемент следующий за последним. Используй vector::back(), тогда заработает может быть.

#13
15:01, 6 авг 2005

vectorItem*>::iterator AddItem( Item* pItem) < return item_list.insert( item_list.end( ),pItem); >

P.S. Писалось на вскидку 😉

#14
15:05, 6 авг 2005

neib
>Ф-я vector::end() возвращает не последний элемент, а элемент следующий за
>последним. Используй vector::back(), тогда заработает может быть.

back() вернет сылку на последний елемент но никак не итератор..

хотя если воспользоваться Хаком.. и посмотреть что в Векторе Итератор это всего навсего T* то можно прикастить указатель елемента к итератору

в принцыпе я раньше считал что rbegin().base() должен вернуть итератор на последний.. но это тожа не так..

Итераторы

Итератор — это объект, указывающий на элемент какого-то контейнера.

Итератор является абстракцией над концепцией указателей. Если указатели работают только с последовательными данными (массивами), то итераторы работают с любыми контейнерами — например со связными списками или деревьями поиска — причём в единообразном синтаксисе, что сильно помогает разработчикам библиотек избегать дублирования кода.

#Синтаксис

Чтобы получить элемент, на который указывает итератор it , необходимо воспользоваться оператором разыменования: *it . Если нужно перейти к следующему элементу надо использовать инкремент: ++it (постфиксного инкремента у итераторов нет).

У всех контейнеров есть какой-то первый и последний элемент. Итератор на первый элемент можно получить через a.begin() , а через a.end() можно получить итератор на некий фиктивный элемент, следующий последним. Таким образом, если проходить от a.begin() до a.end() не включительно, ты мы пройдём по всем элементам контейнера.

::iterator»

#Категории итераторов

Итераторы — очень важная часть интерфейса контейнера. Итераторы можно передавать в различные алгоритмы стандартной библиотеки, которым не обязательно знать про внутреннее устройство контейнера, но нужно знать про то, какие паттерны доступа к данным возможны.

Поэтому в зависимости от внутренней структуры, итераторы контейнера могут отвечать к одному из нескольких абстрактных классов с разными уровнями гарантий:

  • input_iterator , поддерживающий только операции разыменования и инкремента — причём даже без гарантии, что после того, как был произведён инкремент, его предыдущие значения остались валидными. Как можно догадаться из названия, используется для потокового ввода.
  • forward_iterator , помимо предыдущего гарантирующий что итераторы на какой-то конкретный элемент можно инкрементировать сколько угодно раз не опасаясь, что они исчезнут (что позволяет их использовать в алгоритмах, проходящих по данным несколько раз).
  • bidirectional_iterator , помимо предыдущего поддерживающий возможность декремента ( it— ) — то есть перехода к предыдущему элементу.
  • random_access_iterator , помимо предыдущего поддерживающий возможность переходить к элементу, который находится на каком-то расстоянии $k$ — it + k , it — k , it += k , it -= k — и находить расстояние между позициями, на которые указывают два итератора: например, выражение a — b вернет целое число — расстояние между двумя элементами коллекции, соответствующим итераторам a и b .

#Алгоритмы из STL

Например, итераторы std::vector относятся к random_access_iterator , и если вызвать функцию lower_bound из стандартной библиотеки, то она произведет бинарный поиск по элементам (предполагая, что они отсортированы в порядке неубывания):

 Функция lower_bound возвращает итератор на первый элемент, не меньший заданного. Также есть upper_bound , возвращающий первый элемент, строго больший (в случае с int это то же самое, что найти lower_bound от x + 1 ).

Зная, что итераторы вектора поддерживают произвольный доступ, бинарный поиск будет работать за $O(n \log n)$, но для других структур это, возможно, будет не так.

Также по этой причине часто имеет смысл вместо сишных массивов использовать std::array , который является точно таким же массивом фиксированной длины, но поддерживает итераторы и вместе с ними все алгоритмы STL:

stl: добавить в вектор элемент и получить его итератор

Подскажите, можно ли добавить в вектор элемент и получить итератор одной функцией или все таки придется делать так:

data.push_back(object); auto it = data.begin() + (data.size() - 1); 

Отслеживать
13.8k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 16 янв 2019 в 10:28
37.5k 4 4 золотых знака 28 28 серебряных знаков 76 76 бронзовых знаков

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

auto it; 

Отслеживать
ответ дан 16 янв 2019 в 11:07
user7860670 user7860670
29.8k 3 3 золотых знака 17 17 серебряных знаков 36 36 бронзовых знаков

Вопрос был о добавлении существующего объекта object , функция emplace тут подходит слабо так как требует лишнего копирования объекта.

16 янв 2019 в 12:07

@freim Что значит «не подходит»? Это рабочий код. Никакого лишнего копирования или создания ненужных промежуточных объектов тут не происходит (в отличие от функции insert ).

16 янв 2019 в 12:13
а чем emplace от Insert в конец отличается?
16 янв 2019 в 12:24

В данном случае emplace будет полностью эквивалентно insert — и там, и там будет вызываться конструктор копии. Работать, конечно, будет, но это нецелевое и вводящее в заблуждение использование функции. К тому же в случае insert можно использовать и перемещение — в отличие от emplace .

16 янв 2019 в 12:56

@freim: Что за ерунда? Функции emplace почти полностью замещают функции push и insert . В современнои коде надо стараться пользоваться именно emplace . Ничего нецелевого здесь нет — наоборот, именно так и надо. И emplace по определению полностью поддерживает перемещение. О каком «в отличие» вы ведете речь?

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *