Просто о списках, словарях и множествах или ТОП 5 структур данных
Привет. Ей! Не говорите “Да блин! Я знаю, чем отличается список от вектора, мне не нужна эта статья”. Прошу, загляните под кат и освежите свои знания. Я надеюсь, однако, что вы сможете почерпнуть из этой статьи намного больше и, некоторые, возможно, наконец-то разберутся, почему существует так много типов данных для коллекций объектов.
Введение
Так уж сложилось, что в программировании коллекции представляет много, нет ОЧЕНЬ МНОГО различных сущностей — списки, массивы, вектора, множества, стеки, очереди, ассоциативные массивы и у большинства из этих структур данных есть еще по несколько подвидов.
Должны же быть причины, чтобы для простого представления какой-либо совокупности объектов существовало настолько много различных вариаций.
Должны же быть отличия между списком и массивом? Между ассоциативным массивом и хеш-таблицей?
Коллекция
Для начала — самое скучное (да, я люблю такое). Что такое коллекция вообще?
Коллекция — структура данных (тип, класс, даже лучше сказать интерфейс), которая создана, чтобы содержать в себе некоторое количество объектов (в зависимости от языка и терминологии они должны быть одного типа или могут быть разных типов).
Различные типы коллекций могут быть статическими или динамическими, т.е. изменять свой размер или оставаться постоянными, могут быть упорядоченными (точнее учитывающими порядок элементов) и неупорядоченными (соответственно не учитывающими).
Над коллекциями предусмотрено несколько стандартных операций (сейчас мы поговорим о мутабельных, т.е. изменяемых коллекциях), таких как: получение размера, добавление элемента, удаление элемента, поиск (есть какой-либо элемент в коллекции или нет), их очень много.
Ладно, свой негласный долг я выполнил, теперь поехали!
1 Вектор (Vector, Array)
А вы чего ждали?
Вектор (он же одномерный массив) — упорядоченный набор элементов с произвольным доступом по числовому индексу. Что для нас важно в этом определении? Да ничего. Шучу, на самом деле нам важно почти каждое слово:
Доступ к элементам производится по числовому индексу (обычно начиная с 0-го индекса, хотя есть и исключения), обычно доступ к элементу коллекции по индексу записывается как myFavoriteCats[i] или blackKitties[5]. Причем для обозначения этого самого числа — индекса используют букву i.
А когда одной буквы не хватает приплетают сюда j и k.
Итак, далее мы понимаем, что доступ произвольный — значит мы можем обращаться к элементам под индексами 0, 42, 2014 и вобщем-то ожидаем, что операция будет сложности O(1), т.е. константной и независимо от того какой из элементов мы запросим он нам со скоростью света тут же вернется.
Далее — вектор — упорядоченная коллекция, что собственно понятно — у нас есть такие понятия как первый, последний элемент, для каждого конкретно взятого элемента мы также можем назвать предыдущий и следующий.
Релизация
Обычно вектор (как низкоуровневая структура) будет представлять из себя дескриптор, содержащий различную информацию, неотделимую от самой структуры (разумнее всего держать там только размер вектора) и указатель на первый элемент.
Такая реализация позволит за константное время получить доступ к произвольному элементу вектора по его индексу, а также позволит выполнять копирование, конкатенацию и другие простые операции на низком уровне.
И действительно, получить доступ к определенному элементу очень просто — прибавляем к указателю на первый элемент индекс (с некоторыми поправками на размер типа данных) и получаем указатель на нужный элемент! Осталось разыменовать и у нас в переменной нужная кошечка!
Ладно, вектор — классная структура, но и у него есть недостатки (а у кого их нет?!), например нельзя просто так взять и добавить в вектор новый элемент! Особенно втиснуть его в середину. Нельзя также сказать, что кошки с номерами 0, 1 и 4 у нас есть, а с номерами 2 и 3 — нет (раньше они были, но оказалось, что это собаки).
Можно представить себе вектор, как книжную полку с отделениями, в каждом из которых помещается ровно одна книга. Чтобы засунуть новый роман Донцовой между 10-ым и 11-ым томом Большой Совецкой Энциклопедии нужно сильно постараться и переложить все тома с 11-го по 65-ый тома (можно схитрить и поставить 11-ый том в конец, но я вам этого не говорил, да и мы в таком случае потеряем упорядоченность).
В моей памяти все именно так
Применение
В нашем случае вектор бы идеально подошел для топ-10 самых милых котят, т.к. добавлять и удалять элементы не нужно (только изменять), пропусков между 1-ым и 5-ым местом быть не должно, да и удобно обращаться по номеру.
Ладно. В любом случае вектор классный, мы просто посмотрим какие есть еще коллекции.
2 Список (List)
Первый том
Ух! Список задач на сегодня, список покупок в магазине. Список гостей на свадьбу… Так. Ближе к делу.
Мы уже знаем, что элементы вектора лежат акуратненько друг за другом, красиво и ровно. Это дает нам как преимущества так и недостатки.
Список в этом плане полностью противоположная вещь — его элементы могут быть разбросаны по памяти как угодно! Из-за этого мы теряем возможность быстро получить элемент по индексу, а также не можем быстро скопировать весь список, но получаем довольно приятную штуку — мы можем вставлять элементы за константное время в любое место! По слухам удаляются элементы из списка тоже за O(1).
Реализация
Хм. А как с формальным определением?
Список — упорядоченный набор элементов, для каждого из которых хранится указатель на следующий (или для двусвязного списка и на следующий и на предыдущий) элементы списка.
Для последнего элемента списка мы храним нулевой указатель (на диаграммах я буду использовать указатель на нулевую кошку (Null Cat), не пугайтесь).
Внимание! В каноничной реализации списка, для того, чтобы получить размер списка, необходимо обойти весь список — дойдя до нулевого указателя (линейное время — сложность O(n)) и хотя в некоторых реализациях размер кешируется в дескрипторе списка (или в первом элементе), не стоит на это полагаться.
Если бы я мог, я бы один элемент списка разместил на северном полюсе, а другой где-нибудь в окресностях Бетельгейзе
Применение
Список бы подошел для (внимание!) списка бездомных котят, отсортированных по возрасту (по возрастанию). Нам как-раз нужно часто добавлять и удалять элементы из списка (вы не подумайте ничего такого — котят забирают), да и чаще понадобятся первые элементы списка — я бы взял себе маленького пушистого котенка, а не 8-ми-летнего манула.
Ладно. Списки это вроде простая структура. Что есть еще?
3 Множество (Set)
Это Сет
Похожее понятие есть в математике, а точнее в теории множеств. Множество отличается и от вектора и от списка, хотя их реализация может быть похожа.
Множество — неупорядоченный набор элементов, без повторов. Ух. И все? Ни тебе произвольного доступа, ничего! Зачем такое нужно?
Как мы знаем в векторе можно быстро получить элемент по индексу, в списке можно быстро добавить или удалить элемент, а что с множеством?
В множестве можно быстро проверить, есть какой-либо элемент внутри, или его нет. Скажем если бы я хотел узнать, находится ли конкретная кошка в моем списке любимых, то и для списка и для вектора мне пришлось бы перебрать (в худжем случае) все элементы!
Реализация
В множестве, т.к. оно неупорядочено можно сортировать элементы при добавлении и в случае чего устроить бинарный поиск. Хм. Вот ведь парадокс, коллекция неупорядоченная, а внутри все будет по-порядку. Тут важно понять, что если вы добавите новый элемент в множество, не факт, что он пойдет в конец.
На самом деле, работая с множеством вообще нельзя полагаться на какой-либо порядок элементов, он может быть любым — именно поэтому множество и неупорядоченная коллекция.
Стоит отметить, что множество может быть реализовано множеством различных способов, например можно использовать хеширование, для еще более быстрого поиска элементов, поэтому подробно реализацию я рассматривать не буду. Скажу лишь, что можно схитрить и использовать наши знания по спискам.
Вообще есть еще упорядоченные множества, множества с повторами (мультимножество), и вероятно должно быть упорядоченное мультимножество.
Теория множеств дается проще, если брать множество котят
Применение
Множество идеально подойдет для списка любимых котят, потому что их множество. Ха! Шучу.
Но оно действительно подойдет, потому-что такую коллекцию не нужно сортировать (упорядоченность не важна) и мы легко сможем проверить, находится ли какой-нибудь конкретный кот в этом множестве (скажем у меня 100 котят и любимых я кормлю креветками).
Ну ладно. Множества тоже хороши, но неужели есть что-то еще?
4 Словарь (Associative Array, Map, Dictionary)
Признайтесь, это лучше, чем просто словарь
Словарь (он же ассоциативный массив) — это тот-же вектор, но с небольшими отличиями. В качестве индекса (который в словаре будет называться ключ) могут выступать не только числа, но и любые другие типы данных (даже другие коллекции!). Также допустимы пропуски, если мы все-таки будем использовать в качестве ключа целое число, например у нас может быть элемент связанный с ключем 5, но при этом отсутствовать элемент связанный с ключем 4.
Что все это значит на практике? Всего-лишь, то, что в квадратных скобках для ображения к элементу по “индексу” мы можем указывать произвольный тип, например allMyCats[“Murka”].
Реализация
Невооруженным видно, что можно просто завести массив (или список) пар (Ключ, Значение) и добавить специальную функцию, которая будет пробегать по этому списку и возвращать определенное значение по связанному с ним ключу.
Мы также не можем сказать какая пара первая, какая последняя и что раньше “Murka” или “Borka”, поэтому словарь считается неупорядоченной структурой.
Опять-же с каждым ключем может быть связано лишь одно значение, поэтому для приведенного примера с именами кошек словарь в чистом виде подходит слабо.
Реализация, как и в случае со множеством, может быть совершенно различной, можно упорядочить пары по ключу и использовать для получения элемента бинарный поиск (в таком случае элементы должны быть упорядочеваемыми). Опять-же можно реализовать словарь с помощью хеширования ключа, что довольно часто используется со строками.
Применение
Самый правдоподобный и грамотный способ — использовать словарь вместе со списком, где ключем словаря будет строка — имя кошки, а значением — список кошек с таким именем. Это позволит быстро найти всех кошек по имени Мурка и выбрать из них ту, которая в данный момент нужна.
Примерно так выглядит в памяти std::map<std::color, std::list<std::cat>>
И у меня для вас новость — типы коллекций закончились. Ну все. Вообще больше нет. Совсем.
5 Стек (Stack)
Еще один кот и будет Stack Overflow
Ха! Я вас обманул (всмысле пошутил)! Есть еще пара структур данных, которые представляют коллекции.
Итак стек — коллекция с необычным доступом, точнее с необычными правилами относительно того, как могут быть добавлены и удалены элементы.
Все просто — добавляемый элемент, называемый “последним”, первый выбывает из из стека.
Стек очень нужен и полезен в программировании. Например с помощью стека осуществляется вложенный вызов процедур — в стек сохраняются адрес возврата и аргументы вызванной функции.
Реализация
В высокоуровневой реализации ничего особенно интересного нет — указатель на список и элементы добавляются в начало этого списка, и удаляются с него-же.
В низкоуровневой реализации (точнее то, как он реализован в современных архитектурах) есть интересные моменты.
Стек там является небольшим зарезервированным участком памяти и совместно с ним хранится два указателя — на начало стека (где лежит первый доавленный элемент) и конец стека — где лежит последний добавленный.
Если в стек поместить слишком много данных программа завершится со всем знакомой ошибкой — Stack Overflow, это значит, что указатель на конец стека превысил верхний допустимый предел.
Также может случиться обратная ситуация (Stack Underflow), если попытаться забрать из стека больше чем в нем есть, но в высокоуровневых языках она не встречается (понятно почему — нам не дают напрямую работать со стеком).
Если кому интересно как это все работает — изучение ассемблера для какой-нибудь популярной архитектуры, вроде i386, может вам помочь.
Применение
Можно было-бы описать в этом месте стек из бедных котят высотой с гору, но на самом деле в высокоуровневых языках стек редко необходим, часто хватает рекурсии, которая использует стек неявно. Я не стал прикладывать надуманный пример (и не смог придумать нормальный, простите), поэтому переходим к следующему пункту.
Разное
На самом деле есть еще куча коллекций, таких как очередь, двусторонняя очередь (дек), двусвязанный список, кольцевое множество, очереди с приоритетом.
Есть деревья (да их целый лес!) и графы.
Есть вероятностные структуры данных, такие как вероятностное множество и список с пропусками.
Я очень хочу про все это написать, но времени и места на хабре не всегда мало.
Однако есть множество (или вектор) вещей, относящихся к теме, которые я хотел бы упомянуть хоть вскользь, да просит меня любопытный читатель и пойдет читать умную книгу.
Строки
В первую очередь то, как реализованы строки в некоторых языках может показаться странным. Самое простое и эффективное решение это наверное решение C — строка это набор символов, с нулевым символом в конце, что позволяет обходиться без дескриптора.
В C++ std::string уже больше походит на вектор.
Ну а в старом паскале дескриптор (точнее всего-лишь длина) хранится в нулевом элементе массива.
В Haskell String — это список символов ([Char]), из чего вытекает, что получение длины строки имеет сложность O(n). Зато их очень удобно оббегать рекурсивно.
В общем случае, строка — это упорядоченный набор символов и не более. Какой именно тип коллекции будет использован — не важно (ну я бы не советовал использовать множество, ха!).
Очередь (Queue)
Очередь очень похожа на стек и в тоже время является его противоположностью — первым мы получим обратно не тот элемент, что мы добавили последним, а тот, что “стоит в очереди” дольше всех. Очередь очень удобная структура, но несмотря, на то, что принцип ее работы схож со стеком, в эффективной реализации есть небольшое отличие.
Для стека мы могли схитрить и выделить приемлемый по размеру участок памяти, в случае чего его расширяя, потому-что стек то уменьшается, то увеличивается, т.к. элементы и добавляются и удаляются “с одного конца”. Если же мы представим работу очереди, то она будет “ползти в памяти” — начало будет постоянно сдвигаться вверх, поэтому трюк, который применим для стека, будет работать хуже и тут уже намного лучше будет использовать двусвязный список (и не забудьте хранить указатели на первый и последний элементы).
Еще можете попробовать реализвать очередь на двух стеках, но это тоже менее эффективно.
Также есть дек (двусторонняя очередь — deque). В ней можно добавлять элементы как в конец, так и в начало. И забирать их тоже и с конца и с начала.
Заключение
Ух. Я начинаю повторяться
Я совсем не упомянул, про комбинирование различных коллекций, благодаря которым образуются матрицы, таблицы. Также я не затронул деревья, кольцевое множество, почти ничего не написал про очереди, очень мало информации по хешированию (я таки отделался парой слов от этой темы) и другим методам оптимизации.
Однако я думаю статья исполнит свою роль — просто и понятно изложит основы структур данных для читателей разной степени подготовленности. И я буду рад продолжить и осветить множество (или очередь, ха!) других тем в таком-же ключе.
Спасибо тем, кто смог дочитать аж до этих строк (как они это выдержали?).
Класс vector
Класс вектора стандартной библиотеки C++ — это шаблон класса для контейнеров последовательностей. Вектор хранит элементы заданного типа в линейном расположении и обеспечивает быстрый случайный доступ к любому элементу. Вектор является предпочтительным контейнером для последовательности, если производительность случайного доступа находится на уровне «Премиум».
Синтаксис
Параметры
Type
Тип данных элементов, сохраняемых в векторе.
Allocator
Тип, представляющий сохраненный объект распределителя, содержащий сведения о распределении и отмене распределения памяти для вектора. Этот аргумент является необязательным, и значением по умолчанию является allocator<Type> .
Remarks
Для векторов время выполнения вставок и удалений элементов в конце последовательности является постоянной величиной. Время вставки и удаления элементов в середине вектора меняется линейно. Контейнер deque класса быстрее выполняется при вставке и удалении в начале и конце последовательности. Контейнер list класса быстрее выполняется при вставке и удалении в любом расположении в последовательности.
Расширение вектора происходит, когда функции-члену требуется увеличить последовательность в объекте вектора сверх его текущей емкости. Другие операции вставки и стирания могут изменять различные адреса хранения внутри последовательности. Во всех таких случаях итераторы или ссылки, указывающие на изменившиеся части последовательности, становятся недействительными. Если расширения не происходит, действительными остаются только итераторы и ссылки перед точкой вставки или удаления.
Класс vector<bool> является полной специализацией вектора шаблона класса для элементов типа bool . Он имеет распределитель базового типа, используемого специализацией.
Ссылочный vector<bool> класс — это вложенный класс, объекты которого могут предоставлять ссылки на элементы (отдельные биты) в объекте vector<bool> .
Члены
Конструкторы
| Имя | Описание |
|---|---|
| vector | Создает вектор определенного размера, вектор с элементами определенного значения, вектор с определенным allocator , или вектор как копию какого-либо другого вектора. |
Определения типов
| Имя | Описание |
|---|---|
| [allocator_type] (#allocator_type) | Тип, представляющий класс allocator для объекта вектора. |
| const_iterator | Тип, предоставляющий итератор произвольного доступа, который может читать элемент const в векторе. |
| const_pointer | Тип, предоставляющий указатель на элемент const в векторе. |
| const_reference | Тип, предоставляющий ссылку на const элемент, хранящийся в векторе. Он используется для чтения и выполнения const операций. |
| const_reverse_iterator | Тип, предоставляющий итератор произвольного доступа, который может читать любой элемент const в векторе. |
| difference_type | Тип, представляющий различие между адресами двух элементов в векторе. |
| iterator | Тип, предоставляющий итератор произвольного доступа, который может читать или изменять любой элемент в векторе. |
| pointer | Тип, предоставляющий указатель на элемент в векторе. |
| reference | Тип, предоставляющий ссылку на элемент, хранящийся в векторе. |
| reverse_iterator | Тип, предоставляющий итератор произвольного доступа, который может читать или изменять любой элемент в обратном векторе. |
| size_type | Тип, считающий количество элементов в векторе. |
| value_type | Тип, представляющий тип данных, хранящихся в векторе. |
Функции
| Имя | Описание |
|---|---|
| assign | Удаляет вектор и копирует указанные элементы в пустой вектор. |
| at | Возвращает ссылку на элемент в заданном положении в векторе. |
| back | Возвращает ссылку на последний элемент вектора. |
| begin | Возвращает итератор произвольного доступа, указывающий на первый элемент в векторе. |
| capacity | Возвращает число элементов, которое вектор может содержать без выделения дополнительного пространства. |
| cbegin | Возвращает постоянный итератор произвольного доступа, указывающий на первый элемент в векторе. |
| cend | Возвращает константный итератор произвольного доступа, указывающий на позицию, следующую за концом вектора. |
| crbegin | Возвращает константный итератор, который указывает на первый элемент в обратном векторе. |
| crend | Возвращает константный итератор, который указывает на последний элемент в обратном векторе. |
| clear | Очищает элементы вектора. |
| data | Возвращает указатель на первый элемент в векторе. |
| emplace | Вставляет элемент, созданный на месте, в указанное положение в векторе. |
| emplace_back | Добавляет элемент, созданный на месте, в конец вектора. |
| empty | Проверяет, пуст ли контейнер вектора. |
| end | Возвращает итератор произвольного доступа, который указывает на конец вектора. |
| erase | Удаляет элемент или диапазон элементов в векторе из заданных позиций. |
| front | Возвращает ссылку на первый элемент в векторе. |
| get_allocator | Возвращает объект классу allocator , используемому вектором. |
| insert | Вставляет элемент или несколько элементов в вектор по заданной позиции. |
| max_size | Возвращает максимальную длину вектора. |
| pop_back | Удаляет элемент в конце вектора. |
| push_back | Добавляет элемент в конец вектора. |
| rbegin | Возвращает итератор, указывающий на первый элемент в обратном векторе. |
| rend | Возвращает итератор, который указывает на последний элемент в обратном векторе. |
| reserve | Резервирует минимальную длину хранилища для объекта вектора. |
| resize | Определяет новый размер вектора. |
| shrink_to_fit | Удаляет лишнюю емкость. |
| size | Возвращает количество элементов в векторе. |
| swap | Меняет местами элементы двух векторов. |
Операторы
| Имя | Описание |
|---|---|
| operator[] | Возвращает ссылку на элемент вектора в указанной позиции. |
| operator= | Заменяет элементы вектора копией другого вектора. |
allocator_type
Тип, представляющий класс распределителя для объекта вектора.
Remarks
allocator_type является синонимом для параметра-шаблона Allocator .
Пример
Пример использования allocator_type см. в разделе get_allocator.
assign
Удаляет вектор и копирует указанные элементы в пустой вектор.
Параметры
first
Положение первого элемента в диапазоне копируемых элементов.
last
Положение первого элемента за пределами диапазона копируемых элементов.
count
Количество копий элемента, вставляемых в вектор.
value
Значение элемента, вставляемого в вектор.
init_list
Объект initializer_list, содержащий вставляемые элементы.
Remarks
Во-первых, assign удаляет все существующие элементы в векторе. assign Затем либо вставляет указанный диапазон элементов из исходного вектора в вектор, либо вставляет копии нового указанного элемента значения в вектор.
Пример
Возвращает ссылку на элемент в заданном положении в векторе.
Параметры
position
Номер нижнего индекса или позиции элемента, на который включается ссылка в векторе.
Возвращаемое значение
Ссылка на элемент, индекс которого указан в аргументе. Если position размер вектора больше, at вызывает исключение.
Remarks
Если возвращаемое значение at присваивается объекту const_reference , объект вектора нельзя изменить. Если возвращаемое значение at присвоено reference , то объект вектора можно изменить.
Пример
Возвращает ссылку на последний элемент вектора.
Возвращаемое значение
Последний элемент вектора. Если вектор пуст, возвращаемое значение не определено.
Remarks
Если возвращаемое значение back присваивается объекту const_reference , объект вектора нельзя изменить. Если возвращаемое значение back присвоено reference , то объект вектора можно изменить.
При компиляции с использованием _ITERATOR_DEBUG_LEVEL 1 или 2 возникает ошибка среды выполнения при попытке доступа к элементу в пустом векторе. Дополнительные сведения см. в разделе «Проверенные итераторы».
Пример
begin
Возвращает итератор произвольного доступа, указывающий на первый элемент в векторе.
Возвращаемое значение
Итератор произвольного доступа, который указывает на первый элемент в vector или на элемент, следующий за пустым vector . Всегда сравнивайте возвращаемое значение, vector::end чтобы убедиться, что оно допустимо.
Remarks
Если возвращаемое значение назначено begin объекту vector::const_iterator , vector объект нельзя изменить. Если возвращаемое значение begin присваивается объекту vector::iterator , vector его можно изменить.
Пример
capacity
Возвращает число элементов, которое вектор может содержать без выделения дополнительного пространства.
Возвращаемое значение
Текущая длина хранилища, выделенного вектору.
Remarks
Функция-член resize будет более эффективной, если выделено достаточно памяти для ее размещения. Используйте функцию-член reserve , чтобы указать объем выделенной памяти.
Пример
cbegin
Возвращает итератор const , направленный на первый элемент в диапазоне.
Возвращаемое значение
Итератор случайного доступа const , который указывает на первый элемент диапазона или расположение прямо за концом пустого диапазона ( cbegin() == cend() для пустого диапазона).
Remarks
Возвращаемое значение cbegin , элементы в диапазоне не могут быть изменены.
Эту функцию-член можно использовать вместо функции-члена begin() , чтобы гарантировать, что возвращаемое значение будет const_iterator . Как правило, он используется с ключевым словом вычета auto типов, как показано в следующем примере. В этом примере предположим, что Container является изменяемым контейнером (не const ) любого типа, который поддерживает begin() и cbegin() .
const Возвращает итератор, указывающий на элемент после последнего элемента вектора.
Возвращаемое значение
Итератор const последнего итератора для вектора. Он указывает на элемент после последнего элемента вектора. Этот элемент является заполнителем и не должен быть разыменован. Используйте его только для сравнения. Если вектор пуст, то vector::cend() == vector::cbegin() .
Remarks
cend используется для проверки того, прошел ли итератор конец диапазона.
Эту функцию-член можно использовать вместо функции-члена end() , чтобы гарантировать, что возвращаемое значение будет const_iterator . Как правило, он используется с ключевым словом вычета auto типов, как показано в следующем примере. В этом примере предположим, что Container является изменяемым контейнером (не const ) любого типа, который поддерживает end() и cend() .
Возвращаемое cend значение не должно быть разыменовывано. Используйте его только для сравнения.
clear
Очищает элементы вектора.
Пример
const_iterator
Тип, предоставляющий итератор произвольного доступа, который может читать элемент const в векторе.
Remarks
Тип const_iterator нельзя использовать для изменения значения элемента.
Пример
Пример использования back см. в разделе const_iterator .
const_pointer
Тип, предоставляющий указатель на элемент const в векторе.
Remarks
Тип const_pointer нельзя использовать для изменения значения элемента.
Для доступа к элементу вектора обычно используется iterator.
const_reference
Тип, предоставляющий ссылку на const элемент, хранящийся в векторе. Он используется для чтения и выполнения const операций.
Remarks
Тип const_reference нельзя использовать для изменения значения элемента.
Пример
const_reverse_iterator
Тип, предоставляющий итератор произвольного доступа, который может читать любой элемент const в векторе.
Remarks
Тип const_reverse_iterator не может изменять значение элемента и используется для итерации по вектору в обратном направлении.
Пример
См rbegin . пример объявления и использования итератора.
crbegin
Возвращает константный итератор, который указывает на первый элемент в обратном векторе.
Возвращаемое значение
Константный обратный итератор произвольного доступа, адресующий первый элемент в обратном vector или адресующий то, что было последним элементом в неразрешимом vector виде.
Remarks
Возвращаемое значение crbegin vector объекта невозможно изменить.
Пример
crend
Возвращает обратный const итератор, указывающий на элемент после последнего элемента обратного вектора.
Возвращаемое значение
Обратный const итератор в прошлом для обратного вектора. Он указывает на элемент, следующий за последним элементом обратного вектора, который совпадает с элементом перед первым элементом невернутого вектора. Этот элемент является заполнителем и не должен быть разыменован. Используйте его только для сравнения.
Remarks
crend используется с обратным vector так же, как vector::cend и с vector .
Возвращаемое значение crend (подходящее уменьшение) vector не может быть изменено.
crend используется, чтобы проверить, достиг ли итератор конца vector .
Возвращаемое crend значение не должно быть разыменовывано. Используйте его только для сравнения.
Пример
Возвращает указатель на первый элемент в векторе.
Возвращаемое значение
Указатель на первый элемент в vector расположении или в расположении, который завершается пустым vector .
Пример
difference_type
Тип, предоставляющий разницу между двумя итераторами, ссылающимися на элементы в одном и том же векторе.
Remarks
difference_type также можно описать как число элементов между двумя указателями, так как указатель на элемент содержит его адрес.
Для доступа к элементу вектора обычно используется iterator.
Пример
emplace
Вставляет элемент, созданный на месте, в указанное положение в векторе.
Параметры
position
Позиция в vector месте вставки первого элемента.
args
Аргументы конструктора. Функция определяет перегрузку конструктора, которую нужно вызвать, на основе переданных аргументов.
Возвращаемое значение
Функция возвращают итератор, указывающий на положение вставки нового элемента в vector .
Remarks
Любая операция вставки может быть дорогостоящей, ознакомьтесь vector с классом для обсуждения vector производительности.
Пример
emplace_back
Добавляет элемент, созданный на месте, в конец вектора.
Параметры
args
Аргументы конструктора. Функция определяет перегрузку конструктора, которую нужно вызвать, на основе переданных аргументов.
Пример
empty
Проверяет, пуст ли вектор.
Возвращаемое значение
true if the vector is empty; false if the vector isn’t empty.
Пример
Возвращает итератор, указывающий на элемент после последнего элемента вектора.
Возвращаемое значение
Итератор последнего итератора для вектора. Он указывает на элемент после последнего элемента вектора. Этот элемент является заполнителем и не должен быть разыменован. Используйте его только для сравнения. Если вектор пуст, то vector::end() == vector::begin() .
Remarks
Если возвращаемое значение end присваивается переменной типа const_iterator , объект vector нельзя изменить. Если возвращаемое значение end присваивается переменной типа iterator , объект vector можно изменить.
Пример
erase
Удаляет элемент или диапазон элементов в векторе из заданных позиций.
Параметры
position
Положение элемента, удаляемого из вектора.
first
Положение первого элемента, удаляемого из вектора.
last
Положение после последнего элемента, удаляемого из вектора.
Возвращаемое значение
Итератор, указывающий на первый элемент, оставшийся после удаленных элементов, или на указатель конца вектора, если такого элемента не существует.
Пример
front
Возвращает ссылку на первый элемент в векторе.
Возвращаемое значение
Ссылка на первый элемент в объекте вектора. Если вектор пуст, возвращаемое значение не определено.
Remarks
Если возвращаемое значение назначено front объекту const_reference , объект вектора не может быть изменен. Если возвращаемое значение front присвоено reference , то объект вектора можно изменить.
При компиляции с использованием _ITERATOR_DEBUG_LEVEL 1 или 2 возникает ошибка среды выполнения при попытке доступа к элементу в пустом векторе. Дополнительные сведения см. в разделе «Проверенные итераторы».
Пример
get_allocator
Возвращает копию объекта allocator, используемого для создания вектора.
Возвращаемое значение
Распределитель, используемый вектором.
Remarks
Распределители для класса вектора определяют, как этот класс управляет хранилищем. Распределителей по умолчанию в классах контейнеров стандартной библиотеки C++ достаточно для большинства задач программирования. Написание и использование собственного класса распределителя — это расширенная функция C++.
Пример
insert
Вставляет элемент, множество элементов или диапазон элементов в вектор по заданной позиции.
Параметры
position
Позиция в векторе, куда вставляется первый элемент.
value
Значение элемента, вставляемого в вектор.
count
Количество элементов, вставляемых в вектор.
first
Положение первого элемента в диапазоне копируемых элементов.
last
Положение первого элемента после диапазона копируемых элементов.
Возвращаемое значение
Две первые функции insert возвращают итератор, указывающий на положение вставки нового элемента в вектор.
Remarks
Используемые в качестве предусловия first и last не должны быть итераторами в векторе, в противном случае поведение будет неопределенным. Любая операция вставки может быть дорогостоящей, ознакомьтесь vector с классом для обсуждения vector производительности.
Пример
iterator
Тип, предоставляющий итератор произвольного доступа, который может читать или изменять любой элемент в векторе.
Remarks
Тип iterator можно использовать для изменения значения элемента.
Пример
max_size
Возвращает максимальную длину вектора.
Возвращаемое значение
Максимально возможная длина вектора.
Пример
operator[]
Возвращает ссылку на элемент вектора в указанной позиции.
Параметры
position
Позиция элемента вектора.
Возвращаемое значение
Если заданная позиция больше или равна размеру контейнера, результат не определен.
Remarks
Если возвращаемое значение назначено operator[] объекту const_reference , объект вектора не может быть изменен. Если возвращаемое значение operator[] присвоено ссылке, то объект вектора можно изменить.
При компиляции с использованием _ITERATOR_DEBUG_LEVEL 1 или 2 возникает ошибка среды выполнения при попытке доступа к элементу за пределами вектора. Дополнительные сведения см. в разделе «Проверенные итераторы».
Пример
operator=
Заменяет элементы вектора копией другого вектора.
Параметры
right
Копируемый vector в . vector
Remarks
После удаления всех существующих элементов в объекте vector operator= копирует или перемещает содержимое right в объект vector .
Пример
pointer
Тип, предоставляющий указатель на элемент в векторе.
Remarks
Тип pointer можно использовать для изменения значения элемента.
Пример
pop_back
Удаляет элемент в конце вектора.
Remarks
Пример кода см. в разделе vector::push_back().
push_back
Добавляет элемент в конец вектора.
Параметры
value
Значение, назначаемое элементу, который добавляется в конец вектора.
Пример
rbegin
Возвращает итератор, указывающий на первый элемент в обратном векторе.
Возвращаемое значение
Обратный итератор произвольного доступа, указывающий на первый элемент в обратном векторе или на последний элемент в исходном векторе.
Remarks
Если возвращаемое значение назначено rbegin объекту const_reverse_iterator , объект вектора не может быть изменен. Если возвращаемое значение rbegin присвоено reverse_iterator , то объект вектора можно изменить.
Пример
reference
Тип, предоставляющий ссылку на элемент, хранящийся в векторе.
Пример
См at . пример использования reference в классе векторов.
Возвращает обратный итератор, указывающий на элемент после последнего элемента обратного вектора.
Возвращаемое значение
Обратный итератор последнего итератора для обратного вектора. Он указывает на элемент после последнего элемента обратного вектора, который совпадает с элементом перед первым элементом невернутого вектора. Этот элемент является заполнителем и не должен быть разыменован. Используйте его только для сравнения.
Remarks
rend используется с обратным вектором так же, как end и с вектором.
Если возвращаемое значение rend присваивается объекту const_reverse_iterator , объект вектора не может быть изменен. Если возвращаемое значение rend присвоено reverse_iterator , то объект вектора можно изменить.
rend используется, чтобы проверить, достиг ли обратный итератор конца вектора.
Возвращаемое rend значение не должно быть разыменовывано. Используйте его только для сравнения.
Пример
reserve
Резервирует минимальную длину хранилища для объекта вектора, при необходимости выделяя пространство.
Параметры
count
Минимальная длина хранилища, выделяемого для вектора.
Пример
resize
Определяет новый размер вектора.
Параметры
new_size
Новый размер вектора.
value
Значение инициализации новых элементов, добавленных в вектор, если новый размер больше исходного. Если значение опущено, новые объекты используют конструктор по умолчанию.
Remarks
Если размер контейнера меньше запрошенного размера, new_size resize добавляет элементы в вектор, пока не достигнет запрошенного размера. Если размер контейнера больше запрошенного размера, удаляет элементы, ближайшие к концу контейнера, resize пока он не достигнет размера new_size . Действие не выполняется, если размер контейнера совпадает с запрошенным размером.
size отражает текущий размер вектора.
Пример
reverse_iterator
Тип, предоставляющий итератор произвольного доступа, который может читать или изменять любой элемент в обратном векторе.
Remarks
Тип reverse_iterator используется для последовательного прохождения через вектор в обратную сторону.
Пример
shrink_to_fit
Удаляет лишнюю емкость.
Пример
Возвращает количество элементов в векторе.
Возвращаемое значение
Текущая длина вектора.
Пример
size_type
Тип, считающий количество элементов в векторе.
Пример
Меняет местами элементы двух векторов.
Параметры
right
Вектор, предоставляющий элементы для замены. Или вектор, элементы которого необходимо обменять с элементами в векторе left .
left
Вектор, элементы которого необходимо обменять с элементами в векторе right .
Пример
value_type
Тип, представляющий тип данных, хранящихся в векторе.
Remarks
value_type является синонимом для параметра-шаблона Type .
Пример
vector
Создает вектор. Перегрузки создают вектор определенного размера или элементы определенного значения. Или как копия всего или части другого вектора. Некоторые перегрузки также позволяют указать используемый распределитель.
Параметры
allocator
Класс распределителя для использования с данным объектом. get_allocator возвращает класс распределителя для объекта.
count
Количество элементов в создаваемом векторе.
value
Значение элементов в создаваемом векторе.
source
Вектор, для которого создаваемый вектор станет копией.
first
Положение первого элемента в диапазоне копируемых элементов.
last
Положение первого элемента за пределами диапазона копируемых элементов.
init_list
Содержащий initializer_list элементы для копирования.
Remarks
Все конструкторы хранят объект распределителя ( allocator ) и инициализировать вектор.
Первые два конструктора определяют пустой исходный вектор. Второй конструктор явно указывает используемый тип распределителя ( allocator ).
Третий конструктор задает повторение указанного числа ( count ) элементов со значением по умолчанию для класса Type .
Четвертый и пятый конструкторы указывают повторение ( count ) элементов значения value .
Шестой конструктор задает копию вектора source .
Седьмой конструктор перемещает вектор source .
Восьмой конструктор использует initializer_list, чтобы указать элементы.
Девятый и десятый конструкторы копируют диапазон [ first , last ) вектора.
В чем разница между вектором и массивом в C++?
Программирование и разработка
В C ++ существует много различий между вектором и массивом. Однако главное сходство очень важно. Основное сходство заключается в том, что оба они представляют собой список, и каждый из них может содержать последовательность данных одного и того же типа. Основные отличия заключаются в следующем: размер (длина) вектора может быть увеличен естественным образом, но размер массива является фиксированным и не может быть увеличен. Элементы могут быть вставлены в вектор, но не могут быть вставлены в массив. Элементы могут быть добавлены в конце вектора, но не могут быть добавлены в конце массива. Вектор — это класс, из которого создаются экземпляры других векторных объектов, но массив является постоянным указателем на последовательность данных того же типа. У вектора есть методы (функции-члены), но у массива их нет, поэтому вектор называется структурой данных. Хотя указатель можно использовать с массивом, итераторы используются с вектором. Итератор — это разработанный указатель.
Перед массивом нельзя включать ни один элемент. В C ++ 17 и выше элемент может быть включен перед вектором с помощью функции-члена emplace ().
В оставшейся части этой статьи проиллюстрированы различия между вектором и массивом. Для каждой точки упоминается недееспособность массива или дается его грубый или громоздкий способ достижения той же цели.
Создание вектора или массива
Вектор можно создать несколькими способами. Основной способ выглядит следующим образом: