Vector в c: Аналог std::vector из C++11 на чистом C89 и как я его писал / Хабр

Аналог std::vector из C++11 на чистом C89 и как я его писал / Хабр

Жилой массив людей. Нет, серьёзно.

Холивары между ценителями Си и приверженцами его ублюдка сына в лице C++ начались ещё до моего рождения и прекратятся разве что после смерти обоих этих языков и меня заодно.

Адепты великого творения Кернигана-Ритчи до последней секунды рабочего дня готовы доказывать приспешникам Страуструпа аксиомы про вечность Си и его невероятную гибкость.

Те в ответ по-свойски советуют им лучше порадоваться рабочему дню, ведь он вот-вот окажется последним – двадцать первому веку кроссплатформенный ассемблер не нужен.

Распаляясь, сторонники Си приводят миллионы давно прошедших через голову навылет тезисов «почему Си лучше C++», при этом каждый раз подчёркивая, что второй все достоинства первого растерял ещё будучи в отцовской утробе, попутно утратив лик человеческий.

Обвиняемая сторона в обиде не остаётся и…

а хотя постойте, о чём это я.

Я люблю Си, уважаю C++ и не переношу холивары (честно). При этом я осознаю, что в Си действительно не хватает многого, и яркий тому пример – отсутствие удобной работы с данными. В C++ эту проблему во многом решает STL и свойства самого языка. На мой студенческий взгляд, здесь особо отличается всем знакомый std::vector. Если стало интересно, как я реализовал его аналог средствами C89 – прошу под кат.

Вообще, с вышеописанной проблемой наверняка сталкивается каждый, кто переходит на Си с языка чуть более высокого уровня (в моём случае это были FreeBASIC и Free Pascal). Проблема отсутствия давно полюбившихся Redim и SetLength() вначале решается «в лоб кувалдой» при помощи realloc(). Потом приходят знания в обнимку с опытом, и вместо этого уже используется простенький самописный динамический массив.

Однако необходимость дублировать его код для каждого отдельно взятого типа данных с каждым разом всё сильнее вызывает раздражение. Туда же альтернативный вариант – использование указателей, требующее разыменований и приведений типов. А затем человеку попадает в руки C++ (или его аналог) и человек видит STL (или его аналог). Дальше можно прочитать в любом бульварном романе.

Тем не менее, влюбляются в тело, но любят душу. Если человек долгое время был в счастливых отношениях с Си, если в них уже появились проекты, то человеку вполне естественно хотеть сделать объект своей любви лучше – к обоюдной пользе. А человек в совершенствовании всегда на что-то ориентируется.

Короче говоря, это история о том, как любовь к Си заставила меня привнести в неё (него?) пресловутый std::vector – то, что мне нравилось в C++, которым (которой?) я в одно время увлёкся.

Уже было отмечено, что проблема отсутствия в Си встроенного динамического массива для произвольных типов не нова и по-разному решалась немало раз.

Вот те варианты реализации вектора, которые я нашёл буквально за пять минут в Google:

https://github. com/rxi/vec
https://github.com/eteran/c-vector
https://github.com/jibsen/scv
https://github.com/graphitemaster/cvec
https://github.com/robertkety/dataStructures (Ctrl+F «dynamicArray»)
http://troydhanson.github.io/uthash/utarray.html
https://github.com/dude719/Dynamic-Array-Kernel
https://developer.gnome.org/glib/stable/glib-Arrays.html
https://www.happybearsoftware.com/implementing-a-dynamic-array
https://github.com/nothings/stb/blob/master/stretchy_buffer.h (добавлено по наводке Xop)

Все эти решения имеют как минимум один из следующих фатальных недостатков:

1. Реализация макросами конкретных функций управления.
   
   Использовать макросы в качестве inline-функций – затея плохая. Об этом говорилось много раз, но разве мы устанем повторять?
   Во-первых, при использовании макросов-функций тяжелее отслеживать и отлаживать ошибки, возникающие из-за неправильных типов аргументов.
   Во-вторых, макросы-функции не умеют ничего возвращать, если не брать во внимание извращения с comma-оператором или отдельным аргументом под имя переменной для хранения результата.
   В-третьих, из-за постоянных подстановок кода из макросов-функций, которые и на inline-то мало похожи, разбухает размер единицы трансляции. Отсюда следует увеличение размера выходного исполняемого файла и прочие радости жизни.
   В-четвёртых, на макрос-функцию нельзя взять указатель.

2. Дублирование общих для любых векторов функций.
   
   Например, разные функции освобождения для вектора int‘ов и вектора char‘ов. Под капотом они будут представлять собой всего-навсего вызов функции free(), глубоко безразличной к тому, что хранится в уничтожаемом буфере, равно как и к типу указателя на него.
   
   Это опять же провоцирует увеличение объёма единиц трансляции, дублирование кода, а заодно и замусоривание пространства имён.

3. Работа со значениями через нетипизированные указатели.
   
   Это обязывает всегда брать указатель на значение для добавления его даже в простой вектор примитивных типов (например int‘ов). А также не забываем о приведении типов и разыменованиях. Ну и о том, что в такой вектор можно потенциально засунуть значения разных типов, и никто нас об этом не предупредит.

4. Обозначение типа вектора как структуры.
   
   Самый большой недостаток, при наличии одного которого даже полное отсутствие других уже не играет роли.
   Во-первых, обращение к элементам вектора происходит через поле структуры. Для одномерного вектора это уже неудобно – стоит ли говорить о многомерных.
   Во-вторых, все поля структуры, даже технические, свободно доступны пользователю.
   Во-третьих, практически полная несовместимость между векторами разных типов.
   В-четвёртых, для создания и удаления вектора требуется 2 вызова malloc() / free() соответственно – один на структуру и один на сам буфер вектора. Как нетрудно догадаться, для вектора размерности вызовов будет уже .
   В-пятых, передать такой вектор в свою функцию можно только по указателю на структуру, поэтому синтаксис обращения к нему в функции будет слегка другим (-> вместо . и всё такое прочее).

Таким образом, вырисовывается задача создания вектора, специализируемого для любых типов данных Си и обладающего следующими возможностями:

1. Доступ к элементам вектора как к элементам обычного массива, вне зависимости от его размерности: vec[k], vec[i][j] и т.д.
2. Управление вектором с помощью обычных функций, обладающих типизированными аргументами и возвращаемым значением, в отличие от макросов.
3. Отсутствие дублирующегося кода благодаря специализации только тех функций, которые принимают и/или возвращают значения пользовательского типа.
4. Отсутствие у пользователя прямого доступа к технической информации вектора.
5. Совместимость между векторами разных типов на уровне присваивания одного другому.
6. Возможность пользователю при специализации вектора указать способ передачи и возврата значений: по значению или по ссылке (через указатель).
7. Максимальная схожесть интерфейса вектора с таковым у std::vector из C++11.

Заранее отвечу на вопрос, почему C89, а не хотя бы C99. Во-первых, это даёт поддержку компилятора из Visual Studio (хоть он мне и не нравится). Во-вторых, я сам очень люблю C99, но в данном случае почувствовал, что поставленную задачу можно решить и в более жёстких условиях. Как-никак, публикацию в «ненормальном программировании» надо оправдывать.

Когда я только начинал изучать Си, написание удобного вектора казалось мне сугубо невозможным – оператор индексации в голове ассоциировался строго с массивом, массив ассоциировался строго с типизированным указателем, а вектор при этом ассоциировался с необходимостью хранить техническую информацию в структуре. Я никак не мог уйти от мысли, что доступ к элементам вектора возможно реализовать только через поле этой самой структуры, а использование этого подхода подавляющим большинством реализаций вектора только укрепляло уверенность в этом.

Однако потом мне на глаза попалась библиотека динамических строк для Си под названием Simple Dynamic Strings, написанная в своё время для Redis. Она использует другой подход: техническая информация о векторе хранится не в структуре вместе с указателем на него, а в виде заголовка прямо перед самим буфером вектора в памяти. Это позволяет оперировать вектором напрямую через типизированный указатель, при этом размещение технической информации всегда достоверно известно.

Напомню, что типизированный указатель даёт возможность обращаться к элементам вектора через оператор индексации, как в обычном массиве. А расположение технической информации прямо перед самим вектором лишает пользователя прямого доступа к ней – для этого ему придётся манипулировать указателями. В случае же структуры как указатель на вектор, так и техническая информация являются её полями, доступ к которым одинаков.

Таким образом мы реализовали возможности (1) и (4). Идём дальше.

Так как теперь вектор – это просто типизированный указатель, то мы, казалось бы, уже можем обобщить для разных типов векторов такие функции как, например, функцию освобождения, просто обозначив аргумент «указатель на освобождаемый вектор» как void*. Общеизвестно, что в void* можно неявно преобразовать любой другой указатель, равно как и наоборот.

Однако можем ли мы это проделать для других функций? Как ни странно, но да. У нас нет функций, оперирующих непосредственно с самими хранимыми значениями – их изначально предполагалось специализировать отдельно для каждого типа вектора. По сути мы оперируем лишь местами хранения значений, но не самими значениями. Следовательно, нам достаточно знать только размер одного элемента, который можно хранить в технической информации вектора и заполнять в функции его создания путём передачи соответствующего аргумента. Такой трюк позволяет нам обобщить для разных типов векторов вообще все функции, а специализировать на их основе только те, которые принимают и/или возвращают значения пользовательского типа.

Пункты (2) и (3) реализованы. А так как в Си нет объектов и любое значение может быть переприсвоено другой переменной буквально копированием памяти, то реализован и пункт (5). Продолжаем в том же духе.

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

• присвоение указанным элементам вектора переданного значения;
• возврат значения указанного элемента.

Известно, что значение может передаваться в функцию или возвращаться из неё либо по значению (пардон за каламбур), либо по ссылке. Для примитивных типов предпочтительнее первый вариант, тогда как для сложных структур – второй.

Ссылок а-ля C++ в Си конечно же нет, но их заменят нам указатели.

Устали от текста? вопрос риторический.

Тогда приведу для наглядности определения вариантов одних и тех же функций, принимающих/возвращающих переменные по значению и по ссылке соответственно.

gvec_error_e gvec_NAME_push( gvec_NAME_t* phandle, const TYPE value )
gvec_error_e gvec_NAME_push( gvec_NAME_t* phandle, const TYPE* value )

TYPE gvec_NAME_front( gvec_NAME_t handle )
TYPE* gvec_NAME_front( gvec_NAME_t handle )

Видно, что в обоих случаях отличие лишь в одном символе.

Уже в C89 оператор присваивания доступен для всех типов, а не только для примитивных. Это позволяет передачу и возврат по ссылке или по значению в специализируемых функциях указывать аргументами макроса-специализатора. Правда возникает резонный вопрос: а почему не указывать это одним аргументом сразу для передачи и возврата одновременно? А очень просто: возврат по значению удобнее и быстрее в случае примитивных типов, но значение может быть не определено в случае отсутствия в векторе запрошенного элемента. При возврате по ссылке в таком случае мы можем просто вернуть NULL. Короче говоря, это оставлено на усмотрение самого программиста.

В итоге реализован пункт (6). Пункт (7) можно также считать реализованным по совокупности всех предыдущих.

Итоговая реализация библиотеки вектора на C89, готовая к практическому применению, находится здесь:

https://github.com/cher-nov/genvector (MIT License теперь WTFPL)

Простейший пример использования приведён в ReadMe.

Конечно, статья не освещает некоторые другие, менее сложные но не менее интересные аспекты реализации, на описание которых у меня не хватило лаконичности и красноречия. Также опущены разглагольствования по поводу решений, оказавшихся в итоге неудачными, и их переосмысления. Но я уверен, что ответы по первому можно получить из кода и ReadMe в репозитории, а по второму – из истории коммитов.

Это первая моя статья на Хабре, поэтому прошу судить как можно строже. За косноязычие – особенно.

Надеюсь, это всё окажется кому-то да полезным.

C++: шаблон класса std::vector | pc

Векторы (vector) это последовательность контейнеров, представляющих массивы, размер которых можно изменять во время работы программы (runtime). Точно так же, как и массивы, векторы используют непрерывное хранилище в памяти для своих элементов (элементы следуют друг за другом без пропусков). Это означает, что элементы векторов могут быть доступны не только через итератор, но и с помощью смещения (использования обычных указателей), как это эффективно реализуется с массивами. Однако в отличие от массивов, размер векторов можно менять динамически, причем обслуживание хранилища осуществляется автоматически контейнером. Внутри себя векторы для хранения своих элементов используют динамически выделенный массив. В процессе роста этот массив требует своего повторного выделения. Это происходит каждый раз, когда добавляются новые элементы, при этом все элементы перемещаются в заново выделенный массив. Эта задача довольно затратная с точки зрения процессорного времени, поэтому иногда используется упреждающее выделение памяти для вектора, когда переразмещение массива его хранилища делается не каждый раз при добавлении нового элемента в контейнер. По этой причине реальный размер контейнера может быть больше, чем требуется для хранения элементов вектора. Библиотеки могут реализовывать разные стратегии для роста контейнера для обеспечения баланса между использованием памяти и повторными выделениями. Однако в любом случае повторные выделения должны происходить с логарифмически растущими интервалами размера, так чтобы вставка отдельных элементов в конец вектора можно было предоставить амортизируемую постоянную сложность вычислений в контексте затрат процессорного времени (см. push_back). Таким образом, в сравнении с массивами векторы потребляют больше памяти с целью повысить эффективность работы по обслуживанию хранилища в случаях, когда растет количество элементов. Если сравнивать с другими динамическими хранилищами последовательности — двусторонними очередями (deque) и списками (list, forward_list), векторы обеспечивают очень эффективный доступ к своим элементам (такой же эффективный, как у массивов), и относительно эффективное добавление или удаление элементов в своем конце. Для операций, которые вовлекают вставку или удаление элементов в позиции, не совпадающие с концом, векторы работают хуже других, и имеют менее целостные итераторы и ссылки, чем списки list и forward_list. [Основные свойства контейнера] Последовательность. Элементы в контейнере vector всегда имеют строго упорядоченную, линейную последовательность. К отдельным элементам можно получить доступ по номеру их позиции в последовательности (т. е. по индексу, как в массиве). Динамический массив. Позволяет осуществить доступ к любому элементу последовательности даже через арифметику указателей, и предоставляет относительно быстрое добавление/удаление элементов в конце последовательности. Проблемы выделения памяти. Контейнер использует объект выделения памяти (allocator object) для динамического обслуживания своего хранилища по мере необходимости. [Параметры шаблона] T Тип элементов. Только с теми типами, которые не выбрасывают исключение при физическом перемещении по памяти [2], гарантируется оптимизация, которая применяет перемещение данных элементов вместо их копирования (при переразмещении хранилища). Псевдоним для доступа как члену класса vector::value_type. Alloc Тип объекта allocator используется для определения модели выделения памяти для хранилища. По умолчанию используется шаблон класса allocator [3], который определяет простейший принцип выделения памяти, независимый от значения. Псевдоним для доступа как члену класса vector::allocator_type. [Поля] C++98 Поле Определение Примечание value_type Первый параметр шаблона (T)   allocator_type Второй параметр шаблона (Alloc) По умолчанию: allocator< value_type> reference allocator_type::reference Для allocator по умолчанию: value_type& const_reference allocator_type::const_reference Для allocator по умолчанию: const value_type& pointer allocator_type::pointer Для allocator по умолчанию: value_type* const_pointer allocator_type::const_pointer Для allocator по умолчанию: const value_type* iterator Итератор произвольного доступа к элементам вектора типа value_type Может быть преобразован к const_iterator const_iterator Итератор произвольного доступа к элементам вектора типа const value_type   reverse_iterator reverse_iterator< iterator>   const_reverse_iterator reverse_iterator< const_iterator>   difference_type Целочисленный тип со знаком, идентичный: iterator_traits< iterator>::difference_type Обычно то же самое, что и ptrdiff_t size_type Целочисленный тип без знака, который может представить любое неотрицательное значение difference_type Обычно то же самое, что и size_t C++11 Поле Определение Примечание value_type Первый параметр шаблона (T)   allocator_type Второй параметр шаблона (Alloc) По умолчанию: allocator< value_type> reference value_type&   const_reference const value_type&   pointer allocator_traits< allocator_type>::pointer Для allocator по умолчанию: value_type* const_pointer allocator_traits< allocator_type>::const_pointer Для allocator по умолчанию: const value_type* iterator Итератор произвольного доступа к элементам вектора типа value_type Может быть преобразован к const_iterator const_iterator Итератор произвольного доступа к элементам вектора типа const value_type   reverse_iterator reverse_iterator< iterator>   const_reverse_iterator reverse_iterator< const_iterator>   difference_type Целочисленный тип со знаком, идентичный: iterator_traits< iterator>::difference_type Обычно то же самое, что и ptrdiff_t size_type Целочисленный тип без знака, который может представить любое неотрицательное значение difference_type Обычно то же самое, что и size_t [Функции] Функция Описание Конструктор Создает экземпляр шаблона vector. Деструктор Уничтожает экземпляр шаблона vector. operator= Присваивает содержимое. Итераторы: begin Возвращает позицию итератора в начало. end Переводит позицию итератора в конец. rbegin Возвращает позицию обратного итератора к обратному началу. rend Переводит позицию обратного итератора к обратному концу. cbegin Возвращает позицию const-итератора в начало (только для C++11). cend Переводит позицию const-итератора в конец (только для C++11). crbegin Возвращает позицию обратного const-итератора к обратному началу (только для C++11). crend Переводит позицию обратного const-итератора к обратному концу (только для C++11). Работа с емкостью хранилища: size Возвратит размер. max_size Возвратит максимальный размер. resize Изменяет размер. capacity Вернет размер выделенного хранилища. empty Проверит vector на пустоту. reserve Запрос на изменение емкости хранилища. shrink_to_fit Обрезка хранилища по полезному содержимому (только для C++11). Доступ к элементам: operator[] Доступ к произвольному элементу. at front Доступ к первому элементу. back Доступ к последнему элементу. data Доступ к данным (только для C++11). Модификаторы: assign Присвоение содержимого vector. push_back Добавление элемента в конец. pop_back Удаление последнего элемента. insert Вставка элементов. erase Стирание элементов. swap Перестановка содержимого. clear Очистка содержимого. emplace Конструирование и вставка элемента. emplace_back Конструирование и вставка элемента в конец. Allocator: get_allocator Получение объекта для выделения памяти. [Перегрузки функций, не относящихся к экземпляру] Функция Описание relational-операторы Операторы отношения для vector (функция шаблона). swap Обмен содержимого vector-ов (функция шаблона). [Специализации шаблона] Функция Описание vector< bool> Вектор значений bool (специализация шаблона класса). [Ссылки] 1. std::vector site:cplusplus.com. 2. std::is_nothrow_move_constructible site:cplusplus.com. 3. std::allocator site:cplusplus.com.

Vector (C++) — это… Что такое Vector (C++)?

vector — это шаблон из стандартной библиотеки C++, реализующий динамический массив произвольного доступа. Это одна из структур данных, именуемых контейнерами (например, list, deque и т. д.)

Устройство

Шаблон vector расположен в заголовочном файле <vector>. Как и все стандартные компоненты, он расположен в пространстве имен std. Данный интерфейс эмулирует работу стандартного массива C (например, быстрый произвольный доступ к элементам), а также некоторые дополнительные возможности, вроде автоматического изменения размера вектора при вставке или удалении элементов.

Все элементы вектора должны принадлежать одному типу. Например, нельзя совместно хранить данные типов char и int в одном экземпляре вектора. Класс vector обладает стандартным набором методов для доступа к элементам, добавления и удаления элементов, а также получения количества хранимых элементов.

Инициализация

Вектор может быть инициализирован любым типом, имеющим конструктор копии и определенный operator= и удовлетворяющим следующим условиям^[1]:

Выражение	Возвращаемый тип	Условие
t = u	T&	t эквивалентен u
T(t)		t эквивалентен T(t)
T(u)		u эквивалентен T(u)
&u	const T*	показывает адрес u
t. ~T()

Здесь T — тип, которым инициализирован vector, t — переменная типа T, u — переменная типа (возможно const) T.

Например:

vector<int> myVector;      // Пустой вектор из элементов типа int
vector<float> myVector(10) // Вектор из 10-и элементов типа float
vector<char> myVector(5, ' ') // Вектор, состоящий из 5-и пробелов
 
class T {
 ...
};
n = 10;
vector<T> myVector(n); // Вектор из 10-и элементов пользовательского типа T

Доступ к элементам

Доступ к отдельному элементу вектора можно получить, используя операции, описанные в таблице ниже. По соглашению C и C++, первый элемент имеет индекс 0, последний — size() - 1^[2].

Выражение	Возвращаемый тип	Проверка границы?
v.at(i)	T& или const T& для элемента i	Возможен выброс исключения out_of_range
v[i]	T& или const T& для элемента i	Неопределенное поведение при i >= v. size()
v.front()	T& или const T& для первого элемента	Неопределенное поведение при v.empty() == true
v.back()	T& или const T& для последнего элемента	Неопределенное поведение при v.empty() == true

Где v — это объект типа (м.б const) vector<T>, а i — индекс необходимого элемента вектора.

Некоторые методы

Класс vector — это контейнер. Согласно стандарту C++, любой контейнер должен содержать методы begin(), end(), size(), max_size(), empty(), и swap().

Ниже приведен краткий перечень доступных методов с описанием и указанием сложности

	Метод	Описание	Сложность
Конструкторы	vector::vector	Конструктор по умолчанию. Не принимает аргументов, создает новый экземпляр вектора	O(1) (выполняется за константное время)
	vector::vector(const vector& c)	Конструктор копии по умолчанию. Создает копию вектора c	O(n) (выполняется за линейное время, пропорциональное размеру вектора c)
	vector::vector(size_type n, const T& val = T())	Создает вектор с n объектами. Если val объявлена, то каждый из этих объектов будет инициализирован ее значением; в противном случае объекты получат значение конструктора по умолчанию типа T.	O(n)
	vector::vector(input_iterator start, input_iterator end)	Cоздает вектор из элементов, лежащих между start и end	O(n)
Деструктор	vector::~vector	Уничтожает вектор и его элементы
Операторы	vector::operator=	Копирует значение одного вектора в другой.	O(n)
	vector::operator==	Сравнение двух векторов	O(n)
Доступ к элементам	vector::at	Доступ к элементу с проверкой выхода за границу	O(1)
	vector::operator[]	Доступ к определенному элементу	O(1)
	vector::front	Доступ к первому элементу	O(1)
	vector::back	Доступ к последнему элементу	O(1)
Итераторы	vector::begin	Возвращает итератор на первый элемент вектора	O(1)
	vector::end	Возвращает итератор на место после последнего элемента вектора	O(1)
	vector::rbegin	Возвращает reverse_iterator на конец текущего вектора.	O(1)
	vector::rend	Возвращает reverse_iterator на начало вектора.	O(1)
Работа с размером вектора	vector::empty	Возвращает true, если вектор пуст	O(1)
	vector::size	Возвращает количество элементов в вектора	O(1)
	vector::max_size	Возвращает максимально возможное количество элементов в векторе	O(1)
	vector::reserve	Устанавливает минимально возможное количество элементов в векторе	O(n)
	vector::capacity	Возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места.	O(1)
	vector::shrink_to_fit	Уменьшает количество используемой памяти за счет освобождения неиспользованной (C++11)	O(1)
Модификаторы	vector::clear	Удаляет все элементы вектора	O(n)
	vector::insert	Вставка элементов в вектор	Вставка в конец, при условии, что память не будет перераспределяться — O(1), в произвольное место — O(n)
	vector::erase	Удаляем указанные элементы вектора (один или несколько)	O(n)
	vector::push_back	Вставка элемента в конец вектора	O(1)
	vector::pop_back	Удалить последний элемент вектора	O(1)
	vector::resize	Изменяет размер вектора на заданную величину	O(n)
	vector::swap	Обменять содержимое двух векторов	O(1)
Другие методы	vector::assign	Ассоциирует с вектором поданные значения	O(n), если установлен нужный размер вектора, O(n*log(n)) при перераспределении памяти
	vector::get_allocator	Возвращает аллокатор, используемый для выделения памяти	O(1)

Итераторы

В дополнение к функциям прямого доступа к элементам, описанными выше, элементы вектора можно получить посредством итераторов.

Итераторы обычно используются парами, один из которых используется для указания текущей итерации, а второй служит для обозначения конца контейнера. Итераторы создаются при помощи таких стандартных методов как begin() и end(). Функция begin() возвращает указатель на первый элемент, а end() — на воображаемый несуществующий элемент, следующий за последним.

Вектор использует наиболее функционально богатый тип итераторов — RandomAccessIterator (итератор произвольного доступа), который позволяет обходить контейнер в любом порядке, а также изменять содержимое вектора в процессе обхода. Однако, при изменении вектора итератор может стать недействительным.

Пример подсчета суммы элементов вектора при помощи итераторов:

    vector<int> the_vector;
    vector<int>::iterator the_iterator;
 
    for (int i=0; i < 10; i++) {
        the_vector.push_back(i);
    }
    int total = 0;
    the_iterator = the_vector. begin();
    while (the_iterator != the_vector.end()) {
      total += *the_iterator; /* Обратите внимание, что доступ к элементу можно получить посредством разыменования итератора */
      ++the_iterator;
    }
    cout << "Итого=" << total << endl;

Результат:
Итого=45

Объем вектора и изменение размера

Типичная реализация вектора — это указатель на динамический массив. Размер вектора — это фактическое число элементов, а объём — количество используемой им памяти.

Если при вставке в вектор новых элементов, его размер становится больше его объёма, происходит перераспределение памяти. Как правило, это приводит к тому, что вектор выделяет новую область хранения, перемещая элементы и свободные старые области в новый участок памяти.

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

#include <vector>
int main() {
  std::vector<int> v(1); // Создаем вектор, состоящий из одного элемента типа int, значение которого равно 0
 
  int& first = *v.begin(); // Создаем ссылку на первый элемент
 
  v.insert(v.end(), v.capacity(), 0); // Добавляем новые элементы
 
  int i = first; // Неопределенное поведение. Ссылка может быть недействительной
}

Метод reserve() используется для предотвращения ненужного перераспределения памяти. После вызова reserve(n), объем вектора гарантированно будет не меньше n. Пример:

#include <vector>
int main() {
  std::vector<int> v(1); // Создаем вектор, состоящий из одного элемента типа int, значение которого равно 0
 
  v.reserve(10); // Резервируем место
 
  int& first = *v.begin(); // Создаем ссылку на первый элемент
 
  v.insert(v.end(), 5, 0); // Добавляем элементы в вектор
 
  int i = first; // OK, т.к не было перераспределения памяти
}

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

#include <vector>
int main() {
  std::vector<int> v(2); // Создаем вектор, состоящий из двух элементов типа Int
 
  // Создаем ссылки на оба элемента
  int& first = v.front(); 
  int& last = v.back();
 
  v.insert(v.begin() + 1, 1, 1); // Добавляем новые элементы в середину вектора
 
  int i = first; // Неопределенное поведение, если вставка вызвала перераспределение памяти
  int j = last; // Неопределенное поведение, согласно стандарту C++, §23.2.4.3/1
}

Специализация vector<bool>

Стандартная библиотека C++ определяет специализацию шаблона вектора для типа bool. Согласно специализации, вектор должен упаковать элементы так, чтобы каждый элемент типа bооl использовал только один бит памяти^[3]. Это многие называют ошибкой^[4][5], так как vector<bool> не соответствует требованиям контейнера стандартной библиотеки C++. Например, контейнер <T>::reference должен быть верным lvalue типа T. Это не выполняется в случае с vector<bool>::reference, которая является объектом-заместителем, конвертируемым в bool^[6]. Кроме того, vector<bool>::iterator не дает bool& при разыменовании. Существует соглашение между комитетом по стандартизации C++ и группой разработчиков библиотеки, что vector<bool> должен быть исключен, а затем удален из стандартной библиотеки, а функциональность будет восстановлена, но под другим именем.^[7]

Использование

Программы на C++, которые используют вектор, должны содержать в себе заголовочный файл <vector>:

#include <vector>
// После этого, можно проинициализировать переменную
std::vector<T> myVector;

или можно подключить заголовочный файл vector.h, где пространство имён std уже подключено

#include <vector. h>
// После этого, можно проинициализировать переменную
vector<T> myVector;

Здесь T — тип данных, которые будут храниться в контейнере, а myVector — переменная, которая будет использоваться. T может быть любым типом данных, включая тип данных, определенный пользователем.

Замена массиву

В C и C++, массив — это данные в смежных блоках памяти. Каждому блоку затем присваивается индекс, и узнать содержание каждого блока можно зная его индекс. Все элементы массива должны быть одного типа.

Вектор похож на динамический массив, но вектор может изменять размер самостоятельно. Также, нет необходимости ручного освобождения памяти.

Поскольку элементы вектора хранятся непрерывно, адрес первого элемента вектора может быть передан функции в качестве массива (указатель на первый элемент). Следующий пример иллюстрирует, как вектор может использоваться с функциями стандартной библиотеки С memcpy и printf:

#include <cstring> // memcpy
#include <vector> 
#include <cstdio> // printf
int main() {
  using namespace std;
  const char arr[] = "1234567890";
  // Создадим вектор с 11-ю '\0'
  vector<char> vec(sizeof arr);  
  // Скопируем 11 элементов типа 'char' в вектор
  memcpy(&vec[0], arr, sizeof arr); 
  // Напечатает "1234567890"
  printf("%s", &vec[0]); 
}

Обратите внимание, что использование memcpy и printf не приветствуется, в пользу более безопасных альтернатив из стандартной библиотеки C++

Пример использования

Следующий пример демонстрирует различные техники с участием вектора и алгоритмов стандартной библиотеки C++, в частности, перемешивание, сортировка, нахождение наибольшего элемента, а также удаление из вектора с использованием идиомы erase-remove.

#include <iostream>
#include <vector>
#include <algorithm>  // sort, max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater, bind2nd
 
// Используется для удобства. В реальных программах используйте с осторожностью
using namespace std;
 
int main() {
  int arr[4] = {1, 2, 3, 4};
  // Инициализирование вектора с использованием массива
  vector<int> numbers(arr, arr+4);
  // Добавляем числа в вектор
  numbers.push_back(5);
  numbers.push_back(6);
  numbers.push_back(7);
  numbers.push_back(8);
  // Теперь вектор выглядит так: {1, 2, 3, 4, 5, 6, 7, 8}
 
  // Произвольно перемешиваем элементы
  random_shuffle(numbers.begin(), numbers.end());
 
  // Получаем максимальный элемент, сложность O(n)
  vector<int>::const_iterator largest = max_element( numbers.begin(), numbers.end() );
 
  cout << "Наибольший элемент " << *largest << endl;
  cout << "Индекс этого элемента " << largest - numbers. begin() << endl;
 
  // Сортируем элементы, сложность O(n log n)
  sort(numbers.begin(), numbers.end());
 
  // Находим позицию цифры 5 в векторе, сложность O(log n)  
  vector<int>::const_iterator five = lower_bound(numbers.begin(), numbers.end(), 5);  
 
  cout << "Цифра 5 расположена под индексом " << five - numbers.begin() << endl;
 
  // Удаляем все элементы больше 4-х 
  numbers.erase(remove_if(numbers.begin(), numbers.end(), 
    bind2nd(greater<int>(), 4)), numbers.end() );
 
  // Печатаем оставшиеся
  for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << ' ';
  }
 
  return 0;
}

Вывод будет содержать:

Наибольший элемент 8

Индекс этого элемента 6 (зависит от реализации)

Цифра 5 расположена под индексом 4

1 2 3 4

Пример 2-мерного динамического вектора, а также пример доступа к нему и его модификации

typedef std::vector< std::vector<int> > pxMP;
 
void function() {
    int sizeX, sizeY; // указываем размер "на лету". 
    pxMP pxMap(sizeX, std::vector<int>(sizeY)); // массив размера X/Y пикселей 0,1.
    pxMap[0][5] = 1;  /* доступ */
 
        // удаляем левый и правый столбец
        pxMap.pop_back();
        pxMap.erase(pxMap.begin());
 
        // удаляем верхнюю и нижнюю строки из всех столбцов, для начала создаем некоторые инструменты для этого:
        std::vector< std::vector<int> >::iterator iterlvl2; // итератор для второго измерения.
        std::vector< int >::iterator iterlvl1; // итератор для первого измерения
 
        // Уходим вглубь
        for (iterlvl2=pxMap.begin();iterlvl2 != pxMap.end();iterlvl2++) {
            iterlvl1 = (*iterlvl2).begin(); // Только для демонстрации
            (*iterlvl2).pop_back();
            (*iterlvl2).erase((*iterlvl2).begin()); // где мы?
 
            sizeY = (*iterlvl2).size(); // Устанавливаем sizeY пока мы на этом уровне. Потом мы не сможем этого сделать
        }
}

Пример одномерного динамического вектора, сортировка и удаление дубликатов:

#include <vector>
#include <string>
#include <algorithm> // для использования алгоритмов: sort / unique / erase
 
void main() {
 
    vector<string> v_str;    // пустой вектор v_str
    v_str. push_back("zz");   // {"zz"}
    v_str.push_back("aa");   // {"zz", "aa")
    v_str.push_back("bb");   // {"zz", "aa", "bb")
    v_str.push_back("aa");   // {"zz", "aa", "bb", "aa")
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx")
    v_str.push_back("dd");   // {"zz", "aa", "bb", "aa", "xx", "dd")
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx", "dd", "xx")
 
    // сортируем все элементы вектора
    sort(v_str.begin(), v_str.end());    
    // Результат сортировки вектора: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"}
 
    // Удаляем дубликаты
    v_str.erase( unique(v_str.begin(), v_str.end() ), v_str.end() );   
    // Результат сортировки и удаления дубликатов: {"aa","bb","dd","xx","zz"}
 
    return void;
}

Доводы за и против

• Как и все реализации динамического массива, вектор не использует дополнительных структур данных, данные расположены в памяти рядом, за счет чего они хорошо кешируются.
• Вектор может быстро выделять память, необходимую для хранения конкретных данных. Это особенно полезно для хранения данных в списках, длина которых может быть не известна до создания списка, а удаление (за исключением, быть может, в конце) необходимо редко.
• Как и другие контейнеры STL, может содержать примитивные типы данных, сложные или определенные пользователем.
• В отличие от других контейнеров STL, таких как std::deque и std::list, вектор позволяет пользователю определить начальную длину
• Вектор разрешает произвольный доступ; то есть на элемент вектора можно ссылаться так же, как на элемент массив (по индексу). Связанные списки и множества, напротив, не поддерживают произвольный доступ и арифметические операции над указателями.
• Удаление элемента из вектора или даже очистка вектора совершенно не обязательно освободит память, связанную с этим элементом. Это потому, что максимальный размер вектора с момента его создания является хорошей оценкой размера для нового вектора.
• Векторы являются неэффективными для вставки элементов в любые места, кроме конца. Такая операция имеет О(n) (см. O-нотация) сложность по сравнению с O(1) для связанных списков. Это компенсируется скоростью доступа и скоростью удаления. Доступ к произвольному элементу вектора имеет сложность O(1) по сравнению с О(n) для связанного списка и O(log n) для дерева. Удаление имеет сложность O(2) (перестановка и удаление).

См. также

Источники

Ссылки

std :: vector — cppreference.com

1) std :: vector — это контейнер последовательности, который инкапсулирует массивы динамического размера.

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

Хранение вектора обрабатывается автоматически, при необходимости расширяясь и сокращаясь.Векторы обычно занимают больше места, чем статические массивы, потому что больше памяти выделяется для обработки будущего роста. Таким образом, вектор не нужно перераспределять каждый раз при вставке элемента, а только тогда, когда дополнительная память исчерпана. Общий объем выделенной памяти можно запросить с помощью функции capacity (). Дополнительную память можно вернуть в систему с помощью вызова shrink_to_fit (). (начиная с C ++ 11)

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

Сложность (эффективность) обычных операций над векторами следующая:

• Произвольный доступ — постоянный 𝓞 (1)
• Вставка или удаление элементов в конце — амортизированная постоянная 𝓞 (1)
• Вставка или удаление элементов — линейно по расстоянию до конца вектора 𝓞 (n)

std :: vector (для T кроме bool ) соответствует требованиям Container, AllocatorAwareContainer, SequenceContainer, ContiguousContainer (начиная с C ++ 17) и ReversibleContainer.

[править] Параметры шаблона

т	—	Тип элементов. T должен соответствовать требованиям CopyAssignable и CopyConstructible. (до C ++ 11) Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых с контейнером. Как правило, требуется, чтобы тип элемента был законченным и соответствовал требованиям Erasable, но многие функции-члены предъявляют более строгие требования. (начиная с C ++ 11) (до C ++ 17) Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых с контейнером. Обычно требуется, чтобы тип элемента соответствовал требованиям Erasable, но многие функции-члены предъявляют более строгие требования. Этот контейнер (но не его члены) можно создать с неполным типом элемента, если распределитель удовлетворяет требованиям полноты распределителя. (начиная с C ++ 17) [править]
Распределитель	—	Распределитель, который используется для получения / освобождения памяти и для создания / уничтожения элементов в этой памяти.Тип должен соответствовать требованиям Allocator. Поведение не определено (до C ++ 20). Программа плохо сформирована (начиная с C ++ 20), если Allocator :: value_type не совпадает с T. [править]

[править] Специализации

Стандартная библиотека предоставляет специализацию std :: vector для типа bool, которая может быть оптимизирована для экономии места.

[править] Недействительность итератора

Операции	признано недействительным
Все операции только для чтения	Никогда
своп, std :: swap	конец ()
очистить, оператор =, назначить	Всегда
резерв, shrink_to_fit	Если вектор изменил емкость, то все. Если нет, то нет.
стереть	Удаленные элементы и все элементы после них (включая end ())
push_back, emplace_back	Если вектор изменил емкость, то все. Если нет, только end ().
вставка, место	Если вектор изменил емкость, то все. В противном случае только те, которые находятся в точке вставки или после нее (включая end ()).
изменить размер	Если вектор изменил емкость, то все.Если нет, то удаляются только end () и все элементы.
pop_back	Элемент удален и завершен ().

[править] Типы элементов

[править] Функции-члены

	создает вектор (общедоступная функция-член) [править]
	разрушает вектор (общедоступная функция-член) [править]
	присваивает значения контейнеру (общедоступная функция-член) [править]
	присваивает значения контейнеру (общедоступная функция-член) [править]
	возвращает связанный распределитель (общедоступная функция-член) [править]
Доступ к элементу
	доступ к указанному элементу с проверкой границ (общедоступная функция-член) [править]
	доступ к указанному элементу (общедоступная функция-член) [править]
	доступ к первому элементу (общедоступная функция-член) [править]
	доступ к последнему элементу (общедоступная функция-член) [править]
	прямой доступ к базовому массиву (общедоступная функция-член) [править]
Итераторы
	возвращает итератор в начало (общедоступная функция-член) [править]
	возвращает итератор до конца (общедоступная функция-член) [править]
	возвращает обратный итератор к началу (общедоступная функция-член) [править]
	возвращает обратный итератор до конца (общедоступная функция-член) [править]
Вместимость
	проверяет, пуст ли контейнер. (общедоступная функция-член) [править]
	возвращает количество элементов (общедоступная функция-член) [править]
	возвращает максимально возможное количество элементов (общедоступная функция-член) [править]
	резервирует хранилище (общедоступная функция-член) [править]
	возвращает количество элементов, которые могут храниться в выделенной в данный момент памяти. (общедоступная функция-член) [править]
	уменьшает использование памяти за счет освобождения неиспользуемой памяти (общедоступная функция-член) [править]
Модификаторы
	очищает содержимое (общедоступная функция-член) [править]
	вставляет элементы (общедоступная функция-член) [править]
	создает элемент на месте (общедоступная функция-член) [править]
	стирает элементы (общедоступная функция-член) [править]
	добавляет элемент в конец (общедоступная функция-член) [править]
	создает элемент на месте в конце (общедоступная функция-член) [править]
	удаляет последний элемент (общедоступная функция-член) [править]
	изменяет количество хранимых элементов. (общедоступная функция-член) [править]
	меняет местами содержимое (общедоступная функция-член) [править]

[править] Функции, не являющиеся членами

[править] Руководства по выводам (начиная с C ++ 17)

[править] Пример

 #include 
#include <вектор>

int main ()
{
    // Создаем вектор, содержащий целые числа
    std :: vector  v = {7, 5, 16, 8};

    // Добавляем в вектор еще два целых числа
    v.push_back (25);
    v.push_back (13);

    // Распечатать вектор
    std :: cout << "v = {";
    for (int n: v) {
        std :: cout << n << ",";
    }
    std :: cout << "}; \ n";
} 

Выход:

 v = {7, 5, 16, 8, 25, 13,}; 

[править] Отчеты о дефектах

Следующие ниже отчеты о дефектах, изменяющих поведение, были применены задним числом к ​​ранее опубликованным стандартам C ++.

std :: vector - cppreference.

com

1) std :: vector - это контейнер последовательности, который инкапсулирует массивы динамического размера.

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

Хранение вектора обрабатывается автоматически, при необходимости расширяясь и сокращаясь.Векторы обычно занимают больше места, чем статические массивы, потому что больше памяти выделяется для обработки будущего роста. Таким образом, вектор не нужно перераспределять каждый раз при вставке элемента, а только тогда, когда дополнительная память исчерпана. Общий объем выделенной памяти можно запросить с помощью функции capacity (). Дополнительную память можно вернуть в систему с помощью вызова shrink_to_fit (). (начиная с C ++ 11)

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

Сложность (эффективность) обычных операций над векторами следующая:

• Произвольный доступ - постоянный 𝓞 (1)
• Вставка или удаление элементов в конце - амортизированная постоянная 𝓞 (1)
• Вставка или удаление элементов - линейно по расстоянию до конца вектора 𝓞 (n)

std :: vector (для T кроме bool ) соответствует требованиям Container, AllocatorAwareContainer, SequenceContainer, ContiguousContainer (начиная с C ++ 17) и ReversibleContainer.

[править] Параметры шаблона

т	-	Тип элементов. T должен соответствовать требованиям CopyAssignable и CopyConstructible. (до C ++ 11) Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых с контейнером. Как правило, требуется, чтобы тип элемента был законченным и соответствовал требованиям Erasable, но многие функции-члены предъявляют более строгие требования. (начиная с C ++ 11) (до C ++ 17) Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых с контейнером.Обычно требуется, чтобы тип элемента соответствовал требованиям Erasable, но многие функции-члены предъявляют более строгие требования. Этот контейнер (но не его члены) можно создать с неполным типом элемента, если распределитель удовлетворяет требованиям полноты распределителя. (начиная с C ++ 17) [править]
Распределитель	-	Распределитель, который используется для получения / освобождения памяти и для создания / уничтожения элементов в этой памяти.Тип должен соответствовать требованиям Allocator. Поведение не определено (до C ++ 20). Программа плохо сформирована (начиная с C ++ 20), если Allocator :: value_type не совпадает с T. [править]

[править] Специализации

Стандартная библиотека предоставляет специализацию std :: vector для типа bool, которая может быть оптимизирована для экономии места.

[править] Недействительность итератора

Операции	признано недействительным
Все операции только для чтения	Никогда
своп, std :: swap	конец ()
очистить, оператор =, назначить	Всегда
резерв, shrink_to_fit	Если вектор изменил емкость, то все. Если нет, то нет.
стереть	Удаленные элементы и все элементы после них (включая end ())
push_back, emplace_back	Если вектор изменил емкость, то все. Если нет, только end ().
вставка, место	Если вектор изменил емкость, то все. В противном случае только те, которые находятся в точке вставки или после нее (включая end ()).
изменить размер	Если вектор изменил емкость, то все.Если нет, то удаляются только end () и все элементы.
pop_back	Элемент удален и завершен ().

[править] Типы элементов

[править] Функции-члены

	создает вектор (общедоступная функция-член) [править]
	разрушает вектор (общедоступная функция-член) [править]
	присваивает значения контейнеру (общедоступная функция-член) [править]
	присваивает значения контейнеру (общедоступная функция-член) [править]
	возвращает связанный распределитель (общедоступная функция-член) [править]
Доступ к элементу
	доступ к указанному элементу с проверкой границ (общедоступная функция-член) [править]
	доступ к указанному элементу (общедоступная функция-член) [править]
	доступ к первому элементу (общедоступная функция-член) [править]
	доступ к последнему элементу (общедоступная функция-член) [править]
	прямой доступ к базовому массиву (общедоступная функция-член) [править]
Итераторы
	возвращает итератор в начало (общедоступная функция-член) [править]
	возвращает итератор до конца (общедоступная функция-член) [править]
	возвращает обратный итератор к началу (общедоступная функция-член) [править]
	возвращает обратный итератор до конца (общедоступная функция-член) [править]
Вместимость
	проверяет, пуст ли контейнер. (общедоступная функция-член) [править]
	возвращает количество элементов (общедоступная функция-член) [править]
	возвращает максимально возможное количество элементов (общедоступная функция-член) [править]
	резервирует хранилище (общедоступная функция-член) [править]
	возвращает количество элементов, которые могут храниться в выделенной в данный момент памяти. (общедоступная функция-член) [править]
	уменьшает использование памяти за счет освобождения неиспользуемой памяти (общедоступная функция-член) [править]
Модификаторы
	очищает содержимое (общедоступная функция-член) [править]
	вставляет элементы (общедоступная функция-член) [править]
	создает элемент на месте (общедоступная функция-член) [править]
	стирает элементы (общедоступная функция-член) [править]
	добавляет элемент в конец (общедоступная функция-член) [править]
	создает элемент на месте в конце (общедоступная функция-член) [править]
	удаляет последний элемент (общедоступная функция-член) [править]
	изменяет количество хранимых элементов. (общедоступная функция-член) [править]
	меняет местами содержимое (общедоступная функция-член) [править]

[править] Функции, не являющиеся членами

[править] Руководства по выводам (начиная с C ++ 17)

[править] Пример

 #include 
#include <вектор>

int main ()
{
    // Создаем вектор, содержащий целые числа
    std :: vector  v = {7, 5, 16, 8};

    // Добавляем в вектор еще два целых числа
    v.push_back (25);
    v.push_back (13);

    // Распечатать вектор
    std :: cout << "v = {";
    for (int n: v) {
        std :: cout << n << ",";
    }
    std :: cout << "}; \ n";
} 

Выход:

 v = {7, 5, 16, 8, 25, 13,}; 

[править] Отчеты о дефектах

Следующие ниже отчеты о дефектах, изменяющих поведение, были применены задним числом к ​​ранее опубликованным стандартам C ++.

std :: vector - cppreference.

com

1) std :: vector - это контейнер последовательности, который инкапсулирует массивы динамического размера.

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

Хранение вектора обрабатывается автоматически, при необходимости расширяясь и сокращаясь.Векторы обычно занимают больше места, чем статические массивы, потому что больше памяти выделяется для обработки будущего роста. Таким образом, вектор не нужно перераспределять каждый раз при вставке элемента, а только тогда, когда дополнительная память исчерпана. Общий объем выделенной памяти можно запросить с помощью функции capacity (). Дополнительную память можно вернуть в систему с помощью вызова shrink_to_fit (). (начиная с C ++ 11)

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

Сложность (эффективность) обычных операций над векторами следующая:

• Произвольный доступ - постоянный 𝓞 (1)
• Вставка или удаление элементов в конце - амортизированная постоянная 𝓞 (1)
• Вставка или удаление элементов - линейно по расстоянию до конца вектора 𝓞 (n)

std :: vector (для T кроме bool ) соответствует требованиям Container, AllocatorAwareContainer, SequenceContainer, ContiguousContainer (начиная с C ++ 17) и ReversibleContainer.

[править] Параметры шаблона

т	-	Тип элементов. T должен соответствовать требованиям CopyAssignable и CopyConstructible. (до C ++ 11) Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых с контейнером. Как правило, требуется, чтобы тип элемента был законченным и соответствовал требованиям Erasable, но многие функции-члены предъявляют более строгие требования. (начиная с C ++ 11) (до C ++ 17) Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых с контейнером.Обычно требуется, чтобы тип элемента соответствовал требованиям Erasable, но многие функции-члены предъявляют более строгие требования. Этот контейнер (но не его члены) можно создать с неполным типом элемента, если распределитель удовлетворяет требованиям полноты распределителя. (начиная с C ++ 17) [править]
Распределитель	-	Распределитель, который используется для получения / освобождения памяти и для создания / уничтожения элементов в этой памяти.Тип должен соответствовать требованиям Allocator. Поведение не определено (до C ++ 20). Программа плохо сформирована (начиная с C ++ 20), если Allocator :: value_type не совпадает с T. [править]

[править] Специализации

Стандартная библиотека предоставляет специализацию std :: vector для типа bool, которая может быть оптимизирована для экономии места.

[править] Недействительность итератора

Операции	признано недействительным
Все операции только для чтения	Никогда
своп, std :: swap	конец ()
очистить, оператор =, назначить	Всегда
резерв, shrink_to_fit	Если вектор изменил емкость, то все. Если нет, то нет.
стереть	Удаленные элементы и все элементы после них (включая end ())
push_back, emplace_back	Если вектор изменил емкость, то все. Если нет, только end ().
вставка, место	Если вектор изменил емкость, то все. В противном случае только те, которые находятся в точке вставки или после нее (включая end ()).
изменить размер	Если вектор изменил емкость, то все.Если нет, то удаляются только end () и все элементы.
pop_back	Элемент удален и завершен ().

[править] Типы элементов

[править] Функции-члены

	создает вектор (общедоступная функция-член) [править]
	разрушает вектор (общедоступная функция-член) [править]
	присваивает значения контейнеру (общедоступная функция-член) [править]
	присваивает значения контейнеру (общедоступная функция-член) [править]
	возвращает связанный распределитель (общедоступная функция-член) [править]
Доступ к элементу
	доступ к указанному элементу с проверкой границ (общедоступная функция-член) [править]
	доступ к указанному элементу (общедоступная функция-член) [править]
	доступ к первому элементу (общедоступная функция-член) [править]
	доступ к последнему элементу (общедоступная функция-член) [править]
	прямой доступ к базовому массиву (общедоступная функция-член) [править]
Итераторы
	возвращает итератор в начало (общедоступная функция-член) [править]
	возвращает итератор до конца (общедоступная функция-член) [править]
	возвращает обратный итератор к началу (общедоступная функция-член) [править]
	возвращает обратный итератор до конца (общедоступная функция-член) [править]
Вместимость
	проверяет, пуст ли контейнер. (общедоступная функция-член) [править]
	возвращает количество элементов (общедоступная функция-член) [править]
	возвращает максимально возможное количество элементов (общедоступная функция-член) [править]
	резервирует хранилище (общедоступная функция-член) [править]
	возвращает количество элементов, которые могут храниться в выделенной в данный момент памяти. (общедоступная функция-член) [править]
	уменьшает использование памяти за счет освобождения неиспользуемой памяти (общедоступная функция-член) [править]
Модификаторы
	очищает содержимое (общедоступная функция-член) [править]
	вставляет элементы (общедоступная функция-член) [править]
	создает элемент на месте (общедоступная функция-член) [править]
	стирает элементы (общедоступная функция-член) [править]
	добавляет элемент в конец (общедоступная функция-член) [править]
	создает элемент на месте в конце (общедоступная функция-член) [править]
	удаляет последний элемент (общедоступная функция-член) [править]
	изменяет количество хранимых элементов. (общедоступная функция-член) [править]
	меняет местами содержимое (общедоступная функция-член) [править]

[править] Функции, не являющиеся членами

[править] Руководства по выводам (начиная с C ++ 17)

[править] Пример

 #include 
#include <вектор>

int main ()
{
    // Создаем вектор, содержащий целые числа
    std :: vector  v = {7, 5, 16, 8};

    // Добавляем в вектор еще два целых числа
    v.push_back (25);
    v.push_back (13);

    // Распечатать вектор
    std :: cout << "v = {";
    for (int n: v) {
        std :: cout << n << ",";
    }
    std :: cout << "}; \ n";
} 

Выход:

 v = {7, 5, 16, 8, 25, 13,}; 

[править] Отчеты о дефектах

Следующие ниже отчеты о дефектах, изменяющих поведение, были применены задним числом к ​​ранее опубликованным стандартам C ++.

вектор - Ссылка C ++

Векторы - это контейнеры последовательностей, представляющие массивы, размер которых может изменяться.

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

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

Вместо этого векторные контейнеры могут выделять некоторую дополнительную память, чтобы приспособиться к возможному росту, и, таким образом, контейнер может иметь фактическую емкость больше, чем хранилище, строго необходимое для хранения его элементов (т. Е. Его размер). Библиотеки могут реализовывать различные стратегии роста, чтобы сбалансировать использование памяти и перераспределение, но в любом случае перераспределение должно происходить только с логарифмически растущими интервалами размера, так что вставка отдельных элементов в конце вектора может быть обеспечена с амортизированной константой время сложность (см. push_back).

Таким образом, по сравнению с массивами, векторы потребляют больше памяти в обмен на возможность управлять хранилищем и эффективно динамически расти.

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

векторов на C: Краткое руководство по созданию ваших собственных векторов на C

C в той или иной степени повлиял на большинство популярных современных языков программирования, таких как Perl, Java, Python и C ++. Из-за этого многие программисты считают, что знание кода C значительно упрощает изучение новых языков. Однако C сам по себе является законченным языком, и он до сих пор используется повсеместно, даже спустя более четырех десятилетий после его создания. У C есть некоторые преимущества перед его преемниками.Это язык низкого уровня, что означает, что он работает близко к языкам машинного уровня. Это ускоряет компиляцию и запуск, чем C ++ или другие языки. Компиляторы C также широко доступны и могут использоваться практически на любой машине.

Кроме того, C может делать почти все, что могут другие современные языки, хотя для этого может потребоваться время. Векторы - это современная концепция программирования, которая, к сожалению, не встроена в стандартную библиотеку C. Они находятся в C ++, который является расширением C для объектно-ориентированного программирования.По сути, векторы заменяют массивы в C ++. В этом руководстве мы дадим вам обзор того, как можно реплицировать векторы на языке C. Это учебное пособие среднего уровня. Вы должны хорошо разбираться в основах C, чтобы понять это руководство. Если вы новичок в программировании на C, мы рекомендуем сначала пройти этот курс для начинающих, чтобы изучить основы.

Массивы и векторы

Прежде чем мы начнем с того, как мы можем реплицировать векторы на C, давайте посмотрим на основные различия между массивами и векторами, а также на то, почему именно вам могут понадобиться векторы на C.Массивы - это особый тип переменных, которые могут хранить несколько значений данных одного и того же типа. В C вы должны объявить массив с определенным размером, прежде чем вы сможете его использовать. После этого массив сможет хранить данные в соответствии с его размером. Вы не можете хранить больше данных, чем указанный вами исходный размер массива. Это означает, что ваши массивы должны быть идеального размера - вы не сможете увеличить размер позже, если вам нужно. Вам нужно будет провести свое исследование прямо перед тем, как вы создадите массив для большой сложной программы.Кроме того, массивы могут хранить только примитивные типы данных, такие как int или float.

Вектор - это тип массива, который вы найдете в объектно-ориентированных языках, таких как C ++. Как и массивы, они могут хранить несколько значений данных. Однако, в отличие от массивов, они не могут хранить примитивные типы данных. Они хранят только ссылки на объекты - они указывают на объекты, содержащие данные, а не хранят сами объекты. Кроме того, необязательно объявлять размер вектора. Он будет увеличиваться или уменьшаться по мере того, как вы заполняете его ссылками на объекты или удаляете их.У векторов также есть несколько функций безопасности, которые делают их проще в использовании, чем массивы, и вероятность сбоя вашей программы намного меньше. Чтобы узнать больше о векторах и массивах, вы можете взглянуть на наши руководства по этой теме. Вы также можете записаться на этот курс C - в нем мы более подробно рассмотрим основы структуры данных. Вы можете понять, почему векторы кажутся более полезными, чем массивы, и почему они могут быть полезны в C. Однако C не является объектно-ориентированным языком, поэтому создание истинного вектора практически невозможно.Однако мы можем создать псевдовектор в C двумя разными способами.

Репликация вектора в C

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

 typedef struct dynamic_vector
{
int * данные;
size_t limit; // Общий размер вектора
size_t текущий; // Количество векторов в нем на данный момент
} vectorv; 

Здесь мы создали нашу собственную структуру, которая имитирует вектор.Ключевое слово typedef позволяет вам определять тип данных с другим именем. В этом случае мы использовали имя vector для структуры dynamic_vector. Структура - это тип данных в C, который содержит элементы с разными значениями. Он также может без проблем хранить различные типы данных, такие как int, char и float. Вы можете понять, почему это было бы идеально для нас. Ключевое слово «struct» инициализирует структуру и сообщает C, что она имеет три значения: указатель, предел (или общий размер) вектора и текущее значение (общее количество элементов, присутствующих в векторе в данный момент).

После того, как вы объявили структуру, вы захотите написать функции, которые помогут структуре имитировать способ работы вектора. Чтобы действительно знать, как работает вектор, вам нужно изучить различные методы C ++, которые работают с векторами. Вы можете пройти этот курс по C ++, чтобы узнать о них больше. Одна из функций, которые нам нужно написать, например, - сделать структуру способной динамически увеличивать или уменьшать свой «предел», чтобы при добавлении к ней элементов она расширялась автоматически.Для этого нам потребуются функции перераспределения. Что именно делает функция перераспределения? Он изменяет размер блока памяти, который ранее использовался функцией malloc. Итак, теоретически теперь нам понадобится больший размер. Синтаксис функции перераспределения следующий:

 void * realloc (void * current_ptr, size_t new_size) 

Здесь current_ptr будет текущим размером, а параметр new_size позволит нам указать новый размер. Вам нужно сделать значение new_size вдвое больше значения current_ptr, чтобы избежать необходимости постоянно вызывать realloc.Это только начало функций, которые нужно написать для создания вектора. Вам нужно будет написать функции для добавления к нему элементов, удаления элементов, полного удаления вектора или создания новых векторов. Вам также нужно будет принять во внимание, как работает управление памятью C, чтобы создать программу, которая не дает сбоев. Узнайте больше о написании эффективных программ на языке C из этого курса.

Последнее обновление страницы: июнь 2014 г.

Программа C для реализации вектора

 #include  

 #include  

 #ifndef VECTOR_H 

 #define VECTOR_H 

OR #define VECTOR_H 
 #define VECTOR_INIT (vec) вектор vec; vector_init (& vec) 

 #define VECTOR_ADD (vec, item) vector_add (& vec, (void *) item) 

 #define VECTOR_SET (vec, id, item) vector_set (& vec, id, (void *) элемент) 

 #define VECTOR_GET (vec, type, id) (type) vector_get (& vec, id) 

 #define VECTOR_DELETE (vec, id) vector_delete (& vec, id) 

OR #define (vec) vector_total (& vec) 

 #define VECTOR_FREE (vec) vector_free (& vec) 

 typedef struct vector {

 void ** items; 

 внутренняя емкость; 

 внутр.  Всего; 

} вектор; 

 void vector_init (vector *); 

 int vector_total (вектор *); 

 static void vector_resize (vector *, int); 

 void vector_add (vector *, void *); 

 void vector_set (vector *, int, void *); 

 void * vector_get (vector *, int); 

 void vector_delete (vector *, int); 

 void vector_free (vector *); 

 #endif 

 void vector_init (vector * v) {

 v-> capacity = VECTOR_INIT_CAPACITY; 

 v-> total = 0; 

 v-> items = malloc (sizeof (void *) * v-> capacity); 

} 

 int vector_total (vector * v) {

 return v-> total; 

} 

 static void vector_resize (vector * v, int capacity) {

 #ifdef DEBUG_ON 

 printf ("vector_resize:% d to% d \ n", v-> емкость, емкость); 

 #endif 

 void ** items = realloc (v-> items, sizeof (void *) * capacity); 

 if (items) {

 v-> items = items; 

 v-> емкость = емкость; 

} 

} 

 void vector_add (vector * v, void * item) {

 if (v-> capacity == v-> total) 

 vector_resize (v, v-> емкость * 2); 

 v-> items [v-> total ++] = item; 

} 

 void vector_set (vector * v, int index, void * item) {

 if (index> = 0 && index  total) 

 v-> items [index] = item; 

} 

 void * vector_get (vector * v, int index) {

 if (index> = 0 && index  total) 

 return v- > предметы [индекс]; 

 return NULL; 

} 

 void vector_delete (vector * v, int index) {

 if (index <0 || index> = v-> total) 

 return; 

 v-> items [index] = NULL; 

 int i; 

 для (i = 0; i  total - 1; i ++) {

 v-> items [i] = v-> items [i + 1]; 

 v-> items [i + 1] = NULL; 

} 

 v-> всего -; 

 if (v-> total> 0 && v-> total == v-> capacity / 4) 

 vector_resize (v, v-> capacity / 2); 

} 

 void vector_free (vector * v) {

 free (v-> items); 

} 

 int main (пусто) {

 int i; 

 вектор v; 

 vector_init (& v); 

 vector_add (& v, "Bonjour"); 

 vector_add (& v, "tout"); 

 vector_add (& v, "le"); 

 vector_add (& v, "monde"); 

 для (i = 0; i 

 printf ("% s", (char *) vector_get (& v, i)); 

 printf ("\ n"); 

 vector_delete (& v, 3); 

 vector_delete (& v, 2); 

 vector_delete (& v, 1); 

 vector_set (& v, 0, "Привет"); 

 vector_add (& v, «Мир»); 

 для (i = 0; i 

 printf ("% s", (char *) vector_get (& v, i)); 

 printf ("\ n"); 

 vector_free (& v); 

} 

Как использовать C ++ Vector - Linux Hint

Введение

Массив - это серия объектов одного и того же типа в последовательных ячейках памяти. Массив не может увеличить длину руды. Вектор похож на массив, но его длина может быть увеличена или уменьшена. Следовательно, вектор имеет гораздо больше операций, чем массив.

C ++ имеет множество библиотек, каждая из которых составляет стандартную библиотеку C ++. Одна из этих библиотек - это библиотека контейнеров. Контейнер - это набор объектов, и с этой коллекцией можно выполнять определенные операции. Контейнеры C ++ можно сгруппировать в два набора: контейнеры последовательности и ассоциативные контейнеры.Контейнеры последовательности - это vector, array (не тот массив, который обсуждался ранее), deque, forward_list и list. Это разные коллекции (структуры данных, подобные массивам), и каждая предлагает различные компромиссы.

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

Если задача включает частые вставки и удаления в середине последовательности, то следует использовать список или forward_list.Если задача включает частые вставки и удаления в начале или конце последовательности, следует использовать двухстороннюю очередь. Вектор следует использовать, когда такого рода операции не требуются.

В этой статье показано, как использовать вектор C ++. Для понимания этой статьи вам потребуются некоторые знания указателей, ссылок и массивов C ++.

Класс и объекты

Класс - это набор переменных и функций, которые работают вместе, где переменным не присвоены значения.Когда переменным присваиваются значения, класс становится объектом. Различные значения, присвоенные одному и тому же классу, приводят к разным объектам; то есть разные объекты могут принадлежать к одному классу, но иметь разные значения. Создание объекта из класса также известно как создание экземпляра объекта.

Термин вектор описывает класс. Объект, созданный из вектора, имеет имя, выбранное программистом.

Функция, принадлежащая классу, необходима для создания экземпляра объекта из класса.В C ++ эта функция имеет то же имя, что и имя класса. Различные объекты, созданные (экземпляры) из класса, имеют разные имена, данные каждому из них программистом.

Создание объекта из класса означает создание объекта; это также означает создание экземпляра объекта.

Класс Vector

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

После включения заголовка становятся доступны все векторные функции (элементы данных и функции-члены).Чтобы использовать объект счетчика для вывода данных на терминал (консоль), также должен быть включен заголовок объекта. Чтобы написать программу с вектором, как минимум должны быть включены следующие заголовки:

#include
#include

Создание экземпляра вектора

Выше - объявление массива с именем «foo» и количеством элементов «10». Это массив целых чисел. Объявление вектора аналогично. Для вектора количество элементов не является обязательным, поскольку длина вектора может увеличиваться или уменьшаться.

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

std :: vector vtr (8);

Здесь вектор принадлежит специальной функции-конструктору. Тип данных, которые будет содержать вектор, - это «int» в угловых скобках. Термин «vtr» - это имя, выбранное программистом для вектора. Наконец, «8» в скобках - это ориентировочное количество целых чисел, которые будет иметь вектор.

Термин «std» означает стандартное пространство имен. В этом контексте после этого термина должно стоять двойное двоеточие. Кто угодно может написать свою собственную библиотеку векторных классов и использовать ее. Однако в C ++ уже есть стандартная библиотека со стандартными именами, включая «вектор». Чтобы использовать стандартное имя, стандартному имени должен предшествовать std ::. Чтобы избежать ввода std :: каждый раз в программе для стандартного имени, файл программы может запускаться следующим образом:

#include
#include
с использованием пространства имен std;

Перегрузка функции

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

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

Построение вектора означает инстанцирование (создание) векторного объекта. Функция-конструктор перегружается следующим образом:

вектор имя

Это создает вектор нулевой длины и тип «T.» Следующая инструкция создает вектор нулевой длины типа «float» с именем «vtr:»

вектор имя (n)

Это создает вектор с n элементами типа «T.Выражение для этого вектора с четырьмя элементами с плавающей запятой выглядит следующим образом:

вектор имя (n, t)

Создает вектор из n элементов, инициализированных значением t. Следующий оператор создает вектор из 5 элементов, каждый из которых имеет значение 3,4:

vector vtr (5, 3.4);

Построение с инициализацией

Вектор может быть сконструирован (создан) и инициализирован одновременно одним из следующих двух способов:

вектор vtr = {1.1, 2.2, 3.3, 4.4};

или

vector vtr {1.1, 2.2, 3.3, 4.4};

Обратите внимание, что сразу после имени объекта нет скобок. Круглые скобки, используемые сразу после имени объекта, должны содержать список инициализаторов, как показано ниже:

vector vtr ({1.1, 2.2, 3.3, 4.4});

Вектор может быть сконструирован и инициализирован позже с помощью списка инициализаторов. В этом случае круглые скобки использоваться не будут:

вектор vtr;
vtr = {1.1, 2.2, 3.3, 4.4};

вектор V2 (V1)

Это конструктор копирования. Он создает вектор V2 как копию вектора V1. Следующий код иллюстрирует это:

вектор vtr1 (5, 3.4);
вектор vtr2 (vtr1);

Назначение вектора во время строительства

Во время построения может быть создан пустой вектор, в то время как ему назначен другой, как показано ниже:

вектор vtr1 {1.1, 2.2, 3.3, 4.4};
вектор vtr2 = vtr1;

Второй оператор эквивалентен:

вектор vtr2 = {1.1, 2.2, 3.3, 4.4};

const Вектор

Постоянный вектор - это вектор, элементы которого не могут быть изменены. Значения в этом векторе доступны только для чтения. При создании вектор выглядит следующим образом:

const vector vtr {1.1, 2.2, 3.3, 4.4};

В этом векторном типе ни один элемент не может быть добавлен или удален.Более того, никакое значение не может быть изменено.

Построение с итератором

Шаблон обеспечивает общее представление типа данных. Итератор обеспечивает общее представление сканирования значений контейнера. Синтаксис для создания вектора с итератором следующий:

шаблон <класс InputIterator>
вектор (сначала InputIterator, затем InputIterator, const Allocator & = Allocator ());

Создает вектор для диапазона [first, last) с использованием указанного распределителя, который будет обсуждаться позже в этой статье.

Уничтожение вектора

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

Vector Емкость

size_type capacity () const noexcept

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

vector vtr (4);
int число = vtr.capacity ();
cout << число << '\ n';

Выход 4.

резерв (н)

Пространство памяти не всегда доступно. Дополнительное место можно зарезервировать заранее. Рассмотрим следующий сегмент кода:

vector vtr (4);
Втр. Резерв (6);
cout << vtr.capacity () << '\ n';

Результат - 6. Таким образом, зарезервировано дополнительное пространство 6 - 4 = 2 элемента. Функция возвращает void.

размер () const noexcept

Возвращает количество элементов в векторе.Следующий код иллюстрирует эту функцию:

vector vtr (4);
float sz = vtr.size ();
cout << sz << '\ n';

Результат 4.

shrink_to_fit ()

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

vector vtr (4);
Втр. Резерв (6);
vtr.shrink_to_fit ();
интервал sz = vtr.размер();
cout << sz << '\ n';

На выходе будет 4, а не 6. Функция возвращает void.

изменение размера (sz), изменение размера (sz, c)

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

вектор vtr1 {1.1, 2.2, 3.3, 4.4};
vtr1.resize (2);
cout << "Новый размер vtr1:" << vtr1.size () << '\ n';
vector vtr2 {1.1, 2.2};
vtr2.resize (4, 8,8);
cout << "vtr2:" << vtr2 [0] << "" << vtr2 [1] << "
" << vtr2 [2] << "" << vtr2 [3] << '\ n ';

Результат следующий:

Новый размер vtr1: 2
vtr2: 1,1 2,2 8,8 8,8

Функции возвращают значение void.

пусто () const noexcept

Эта функция возвращает 1 для истины, если в векторе нет элементов, и 0 для false, если вектор пуст.Если вектор имеет 4 местоположения для определенного типа данных, таких как float, без какого-либо значения float, то этот вектор не является пустым. Следующий код иллюстрирует это:

vector vtr;
cout << vtr.empty () << '\ n';
vector vt (4);
cout << vt.empty () << '\ n';

вектор v (4,3.5);
cout << v.empty () << '\ n';

Результат следующий:

Доступ к элементу вектора

Вектор может быть подписан (проиндексирован) как массив.Подсчет индекса начинается с нуля.

vectorName [i]

Операция «vectorName [i]» возвращает ссылку на элемент с индексом i ^th вектора. Следующий код выводит 3.3 для указанного выше вектора:

vector vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr [2];
cout << fl << '\ n';

vectorName [i] const

Операция «vectorName [i] const» выполняется вместо «vectorName [i]», когда вектор является постоянным вектором.Эта операция используется в следующем коде:

const vector vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr [2];
cout << fl << '\ n';

Выражение возвращает постоянную ссылку на i ^-й элемент вектора.

Присвоение значения с нижним индексом

Непостоянному вектору может быть присвоено значение, как показано ниже:

vector vtr {1.1, 2.2, 3.3, 4.4};
vtr [2] = 8,8;
cout << vtr [2] << '\ n';

Выход 8.8.

vectorName.at (i)

«vectorName.at (i)» похож на «vectorName [i]», но «vectorName.at (i)» более надежен. Следующий код показывает, как использовать этот вектор:

vector vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr.at (2);
cout << fl << '\ n';
at () - это векторная функция-член.

vectorName.at (i) const

«vectorName.at (i) const» подобен «vectorName [i] const», но «vectorName.at (i) const »более надежен. «VectorName.at (i) const» выполняется вместо «vectorName.at (i)», когда вектор является постоянным вектором. Этот вектор используется в следующем коде:

const vector vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr.at (2);
cout << fl << '\ n';
at () const является векторной функцией-членом.

Присвоение значения с помощью функции at ()

Значение может быть присвоено непостоянному вектору с помощью функции at (), как показано ниже:

вектор vtr {1.1, 2.2, 3.3, 4.4};
Втр. При (2) = 8,8;
cout << vtr [2] << '\ n';

Выход 8.8.

Проблема с подпрограммой

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

передний ()

Возвращает ссылку на первый элемент вектора без удаления элемента. Результатом следующего кода является 1.1.

вектор vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr.front ();
cout << fl << '\ n';

Элемент не удаляется из вектора.

перед () const

Когда конструкции вектора предшествует const, выражение «front () const» выполняется вместо «front ()». Это используется в следующем коде:

const vector vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr.front ();
cout << fl << '\ n';

Возвращается постоянная ссылка.Элемент не удаляется из вектора.

назад ()

Возвращает ссылку на последний элемент вектора без удаления элемента. Вывод следующего кода - 4.4.

vector vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr.back ();
cout << fl << '\ n';

назад () const

Когда построению вектора предшествует const, выражение «back () const» выполняется вместо «back ()».”Это используется в следующем коде:

const vector vtr {1.1, 2.2, 3.3, 4.4};
float fl = vtr.back ();
cout << fl << '\ n';

Возвращается постоянная ссылка. Элемент не удаляется из вектора.

Доступ к векторным данным

data () noexcept; data () const noexcept;

Любой из них возвращает указатель, такой что [data (), data () + size ()) - является допустимым диапазоном.

Более подробно об этом будет сказано ниже.

Возвращающие итераторы и вектор

Итератор похож на указатель, но имеет больше функций, чем указатель.

begin () noexcept

Возвращает итератор, указывающий на первый элемент вектора, как в следующем сегменте кода:

vector vtr {1.1, 2.2, 3.3, 4.4};
vector :: iterator iter = vtr.begin ();
cout << * iter << '\ n';

Выход 1.1. Обратите внимание, что объявление, которое получает итератор, было объявлено.Итератор разыменовывается в возвращаемом выражении для получения значения так же, как разыменование указателя.

begin () const noexcept;

Возвращает итератор, указывающий на первый элемент вектора. Когда конструкции вектора предшествует const, выражение «begin () const» выполняется вместо «begin ()». При этом условии соответствующий элемент в векторе не может быть изменен. Это используется в следующем коде:

const vector vtr {1.1, 2.2, 3.3, 4.4};
вектор :: const_iterator iter = vtr.begin ();
cout << * iter << '\ n';

Выход 1.1. Обратите внимание, что на этот раз был использован «const_iterator» вместо простого «итератора» для получения возвращенного итератора.

конец () noexcept

Возвращает итератор, который указывает сразу за последним элементом вектора. Рассмотрим следующий сегмент кода:

vector vtr {1.1, 2.2, 3.3, 4.4};
вектор :: iterator iter = vtr.конец();
cout << * iter << '\ n';

Результатом будет 0, что не имеет смысла, поскольку за последним элементом нет конкретного элемента.

конец () const noexcept

Возвращает итератор, который указывает сразу за последним элементом вектора. Когда конструкции вектора предшествует «const», выражение «end () const» выполняется вместо «end ()». Рассмотрим следующий сегмент кода:

const vector vtr {1.1, 2.2, 3.3, 4.4};
вектор :: const_iterator iter = vtr.end ();
cout << * iter << '\ n';

Результатом является 0. Обратите внимание, что на этот раз был использован «const_iterator» вместо просто «iterator» для получения возвращенного итератора.

Обратная итерация

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

rbegin () noexcept

Возвращает итератор, указывающий на последний элемент вектора, как в следующем сегменте кода:

вектор vtr {1.1, 2.2, 3.3, 4.4};
вектор :: reverse_iterator rIter = vtr.rbegin ();
cout << * rIter << '\ n';

Выход 4.4.

Обратите внимание, что было объявлено объявление, которое получает обратный итератор. Итератор разыменовывается в возвращаемом выражении для получения значения так же, как разыменование указателя.

rbegin () const noexcept;

Возвращает итератор, указывающий на последний элемент вектора.Когда конструкции вектора предшествует «const», выражение «rbegin () const» выполняется вместо «rbegin ()». При этом условии соответствующий элемент в векторе не может быть изменен. Эта функция используется в следующем коде:

const vector vtr {1.1, 2.2, 3.3, 4.4};
вектор :: const_reverse_iterator rIter = vtr.rbegin ();
cout << * rIter << '\ n';

Выход 4.4.

Обратите внимание, что на этот раз был использован const_reverse_iterator вместо только reverse_iterator для получения возвращенного итератора.

rend () noexcept

Возвращает итератор, который указывает непосредственно перед первым элементом вектора. Рассмотрим следующий сегмент кода:

vector vtr {1.1, 2.2, 3.3, 4.4};
вектор :: reverse_iterator rIter = vtr.rend ();
cout << * rIter << '\ n';

Результатом будет 0, что не имеет смысла, поскольку непосредственно перед первым элементом нет конкретного элемента.

rend () const noexcept

Возвращает итератор, который указывает непосредственно перед первым элементом вектора.Когда конструкции вектора предшествует «const», выражение «rend () const» выполняется вместо «rend ()». Рассмотрим следующий сегмент кода:

const vector vtr {1.1, 2.2, 3.3, 4.4};
вектор :: const_reverse_iterator rIter = vtr.rend ();
cout << * rIter << '\ n';

На выходе будет 0.

Обратите внимание, что на этот раз был использован const_reverse_iterator вместо только reverse_iterator для получения возвращенного итератора.

Векторные модификаторы

Модификатор, изменяющий вектор, может принимать или возвращать итератор.

а. Место (p, args)

Вставляет объект типа T, созданный с помощью std :: forward (args)… перед p.

Подробнее - позже

вставить (iteratorPosition, значение)

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

вектор vtr {10, 20, 30, 40};
вектор :: iterator iter = vtr.begin ();
++ iter;
++ iter;
Втр. Вставка (итер, 25);
cout << vtr [1] << '' << vtr [2] << '
' << vtr [3] << '\ n';

Результат: 20 25 30.

Обратите внимание, что итератор был расширен (увеличен) точно так же, как указатель.

Также можно вставить список инициализаторов, как показано в следующем коде:

вектор vtr {10, 20, 30, 40};
вектор :: итератор iter = vtr.начинать();
++ iter;
++ iter;
vtr.insert (iter, {25, 28});

cout << vtr [1] << '' << vtr [2] << '
' << vtr [3] << '' << vtr [4] << '\ n';

Вывод: 20 25 28 30.

стереть (позиция)

Удаляет элемент в позиции, на которую указывает итератор, затем возвращает позицию итератора. Следующий код иллюстрирует это:

вектор vtr {10, 20, 30, 40};
вектор :: iterator iter = vtr.начинать();
++ iter;
++ iter;
vtr.erase (iter);
cout << vtr [0] << '' << vtr [1] << '
' << vtr [2] << '\ n';

Вывод: 10 20 40

push_back (т), push_back (rv)

Используется для добавления одного элемента в конец вектора. Используйте push_back (t) следующим образом:

vector vtr {1.1, 2.2, 3.3, 4.4};
vtr.push_back (5.5);
float fl = vtr [4];
cout << fl << '\ n';

Выход 5.5.

push_back (rv): - см. Позже.

pop_back ()

Удаляет последний элемент, не возвращая его. Размер вектора уменьшается на 1. Следующий код иллюстрирует это:

vector vtr {1.1, 2.2, 3.3, 4.4};
vtr.pop_back ();
float sz = vtr.size ();
cout << sz << '\ n';

Выход 3.

а. обмен (б)

Два вектора можно поменять местами, как показано в следующем сегменте кода:

вектор vtr1 {1.1, 2.2, 3.3, 4.4};
vector vtr2 {10, 20};
vtr1.swap (vtr2);
cout << "vtr1:" << vtr1 [0] << "" << vtr1 [1] << "
" << vtr1 [2] << "" << vtr1 [3] << '\ n' ;

cout << "vtr2:" << vtr2 [0] << "" << vtr2 [1] << "
" << vtr2 [2] << "" << vtr2 [3] << '\ n ';

Вывод:

vtr1: 10 20 0 0
vtr2: 1,1 2,2 3,3 4,4

Обратите внимание, что длина вектора при необходимости увеличивается.Кроме того, значения, для которых не было замен, заменяются некоторым значением по умолчанию.

прозрачный ()

Удаляет все элементы из вектора, как показывает следующий сегмент кода:

vector vtr {1.1, 2.2, 3.3, 4.4};
vtr.clear ();
cout << vtr.size () << '\ n';

На выходе будет 0.

Операторы равенства и отношения для векторов

Оператор ==

Возвращает 1 для истины, если два вектора имеют одинаковый размер и соответствующие элементы равны; в противном случае он возвращает 0 для ложного.Например:

вектор U {1, 2, 3};
вектор V {4, 5, 6};
bool bl = U == V;
cout << bl << '\ n';

На выходе будет 0.

Оператор! =

Возвращает 1 для истины, если два вектора не имеют одинакового размера и / или соответствующие элементы не равны; в противном случае он возвращает 0 для ложного. Например:

вектор U {1, 2, 3};
вектор V {4, 5, 6};
bool bl = U! = V;
cout << bl << '\ n';

Выход 1.

Оператор <

Возвращает 1 для истины, если первый вектор является начальным подмножеством второго вектора, причем элементы двух равных частей одинаковы и находятся в одном порядке. Если оба вектора имеют одинаковый размер и движутся слева направо, и в первом векторе встречается элемент, который меньше соответствующего элемента во втором векторе, то все равно будет возвращено 1. В противном случае возвращается 0 для false. Например:

вектор U {3, 1, 1};
вектор V {3, 2, 1};
bool bl = U cout << bl << '\ n';

Выход 1.<не распространяется на случай, когда размер и порядок совпадают.

Оператор

Возвращает! (U

Оператор <=

Возвращает U <= V, где U - первый вектор, а V - второй вектор, согласно приведенным выше определениям.

Оператор> =

Возвращает! (U <= V), где U - это первый вектор, а V - второй вектор, согласно приведенным выше определениям.