Vector of Pair in C++
In this article, we have covered the idea of Vector of Pair in C++ with code examples along with basics of Pair and vector in C++.
Table of contents:
- Basic of Pair in C++
- Basic of Vector in C++
- Vector of pairs in C++
Let us get started with Vector of Pair in C++.
Basic of Pair in C++
Pair is a container that stores two data elements in it. It is not necessary that the two values or data elements have to be of the same data type.
Syntax:
The first value given in above pair could be accessed by using pair_name.first similarly, the second value could be accessed using pair_name.second.
Code:
Output: 
Basic of Vector in C++
Vectors are containers that can store multiple data elements that can change in size. The data elements in vectors are of the same data type. Vector is a dynamic array where the size of the array can changed. Vectors are stored in the stack but the elements of this Vector are stored in the heap memory.
Syntax:
There are some functions that are used in vectors to iterate,access elements,modify elements,to check the capacity of the vectors.
1.begin(): This function returns an iterator pointing to the first element of vector.
2.end(): This function return an iterator pointing to the element behind the last element of the vector.
3.cbegin(): This function returns a constant iterator pointing to the first element of vector.
4.cend(): This function returns an iterator pointing to the element behind last element of vector.
5.rbegin():This function returns a reverse iterator pointing to the last element of vector.
6.rend():This function returns a reverse iterator pointing to the preceding element before the first element of vector.
Accessing the elements:
1.at(j)-Returns a reference to element at position ‘j’.
2.front()-Returns a reference to first element.
3.back()- Returns a reference to last element;
4.a.operator()[j]:Returns a reference to element at position ‘j’
1.size() – Returns the number of elements in the vector.
2.max_size() – Returns the maximum number of elements that the vector can hold.
3.capacity() – Returns the size of the storage space currently allocated to the 4.vector expressed as number of elements.
5.resize(n) – Resizes the container so that it contains ‘n’ elements.
6.empty() – Returns whether the container is empty.
1.push_back(): The function inserts the elements into a vector from the back.
2.assign(): It assigns a new value to the vector elements by replacing old ones.
3.pop_back(): The pop_back() function is used to pop or remove the last elements from a vector.
4.insert(): This function inserts new elements before the position specified by the iterator.
5.erase(): This function is used to remove elements from a container from the specified position or range.
6.swap(): This function is used to swap the contents of one vector with another vector of the same type. Sizes may differ.
7.clear(): This function is used to remove all the elements of the vector container
Code:
Output: 
Vector of pairs in C++
Vector of Pairs is a dynamic array filled with pairs instead of any primitive data type. Vector of pairs are no different from vectors when it comes to declaration and accessing the pairs.
How do I declare a vector of pair? :
Ans: To declare a vector of pairs we can use the syntax : vector<pair<string,int>> a;
How can I add a pair to an existing vector of pairs? :
Ans: To add a pair to an existing vector of pairs we can use the statement below: a.push_back(make_pair("ABC",15));
or
a.emplace_back("ABC",15);
push_back function helps in adding the elements to a vector, make_pair function converts the parameters into pairs.
How to delete a pair from a vector?:
Ans: We can use a.pop_back(); to delete the last pair,
or
We can use a.erase(a.begin() + i); to delete from a specified position ‘i’.
Code to add and delete pairs from vectors:
Output: 
Performance Of Vectors:
Vectors are quite similar to arrays when it comes to its functioning, despite that vectors are comparatively faster to arrays. Vectors are better when used for frequent insertion and deletion of elements, Arrays are quite better when it comes to frequent accessing of elements. In terms of space, vectors occupy more space than arrays.
- Random access — constant ��(1)
- Insertion or removal of elements at the end — amortized constant ��(1)
- Insertion or removal of elements — linear in the distance to the end of the vector ��(n)
Applications:
Vectors are dynamic arrays, that means the size of the vector changes after every insertion or deletion of data elements.Vectors can be very helpful in scenarios where there is a frequent change of data elements.
In real time , Vectors are quite helpful in Computer vision, Artificial Intelligence, etc where the data is constantly being stored and being utilized for decision making.In this case the size of the data being interpreted is not fixed.
Vectors are quite suitable for any applications making use of grid representation.
FAQs
Which function inserts elements at a specific position in vectors?
Answer: insert() function helps in inserting elements at a specified position in vectors.
- How can I delete all the elements of a vector?
Answer: clear() function can be used to delete all elements in a vector.
- How to check the number of elements present in a vector?
Answer: size() function can be used to find the size of elements.
- How can I access a vector?
Answer: A vector can be accessed by either indexing it directly using reference operator or we can make use of at() function with some position passed as a parameter. To access the first element of vector we can use front() and back() can be used for the last element.
With this article at OpenGenus, you must have the complete idea of Vector of Pairs in C++.
Anubhav Tewari
Anubhav Tewari has been a Machine Learning Developer, Intern at OpenGenus.
Как добавить элемент в вектор пару с
Для добавления элементов в вектор применяется функция push_back() , в которую передается добавляемый элемент:
Векторы являются динамическими структурами в отличие от массивов, где мы скованы его заданым размером. Поэтому мы можем динамически добавлять в вектор новые данные.
Функция emplace_back() выполняет аналогичную задачу — добавляет элемент в конец контейнера:
Добавление элементов на определенную позицию
Ряд функций позволяет добавлять элементы на определенную позицию.
emplace(pos, value) : вставляет элемент value на позицию, на которую указывает итератор pos
insert(pos, value) : вставляет элемент value на позицию, на которую указывает итератор pos, аналогично функции emplace
insert(pos, n, value) : вставляет n элементов value начиная с позиции, на которую указывает итератор pos
insert(pos, begin, end) : вставляет начиная с позиции, на которую указывает итератор pos, элементы из другого контейнера из диапазона между итераторами begin и end
insert(pos, values) : вставляет список значений начиная с позиции, на которую указывает итератор pos
Удаление элементов
Если необходимо удалить все элементы вектора, то можно использовать функцию clear :
Функция pop_back() удаляет последний элемент вектора:
Если нужно удалить элемент из середины или начала контейнера, применяется функция std::erase() , которая имеет следующие формы:
erase(p) : удаляет элемент, на который указывает итератор p. Возвращает итератор на элемент, следующий после удаленного, или на конец контейнера, если удален последний элемент
erase(begin, end) : удаляет элементы из диапазона, на начало и конец которого указывают итераторы begin и end. Возвращает итератор на элемент, следующий после последнего удаленного, или на конец контейнера, если удален последний элемент
Также начиная со стандарта С++20 в язык была добавлена функция std::erase() . Она не является частью типа vector. В качестве первого параметра она принимает вектор, а в качестве второго — элемент, который надо удалить:
В данном случае удаляем из вектора numbers3 все вхождения числа 1.
Размер вектора
С помощью функции size() можно узнать размер вектора, а с помощью функции empty() проверить, путой ли вектор:
С помощью функции resize() можно изменить размер вектора. Эта функция имеет две формы:
resize(n) : оставляет в векторе n первых элементов. Если вектор содержит больше элементов, то его размер усекается до n элементов. Если размер вектора меньше n, то добавляются недостающие элементы и инициализируются значением по умолчанию
resize(n, value) : также оставляет в векторе n первых элементов. Если размер вектора меньше n, то добавляются недостающие элементы со значением value
Важно учитывать, что применение функции resize может сделать некорректными все итераторы, указатели и ссылки на элементы.
Изменение элементов вектора
Функция assign() позволяет заменить все элементы вектора определенным набором:
В данном случае элементы вектора заменяются набором из четырех строк «C++».
Также можно передать непосредственно набор значений, который заменит значения вектора:
Еще одна функция — swap() обменивает значения двух контейнеров:
Сравнение векторов
Векторы можно сравнивать — они поддерживают все операции сравнения: <, >, <=, >=, ==, !=. Сравнение контейнеров осуществляется на основании сравнения пар элементов на тех же позициях. Векторы равны, если они содержат одинаковые элементы на тех же позициях. Иначе они не равны:
C++
станд :: вектор
Вектор представляет собой динамический массив с автоматически обрабатываемым хранилищем. Элементы в векторе могут быть доступны так же эффективно, как и элементы в массиве с преимуществом, заключающиеся в том, что векторы могут динамически изменять размер.
В терминах хранения векторные данные (обычно) помещаются в динамически распределенную память, что требует некоторых незначительных накладных расходов; наоборот, C-arrays и std::array используют автоматическое хранилище относительно объявленного местоположения и, следовательно, не имеют накладных расходов.
замечания
Использование std::vector требует включения заголовка <vector> используя #include <vector> .
Элементы в std::vector хранятся смежно в свободном хранилище. Следует отметить, что когда векторы вложены как в std::vector<std::vector<int> > , элементы каждого вектора смежны, но каждый вектор выделяет свой собственный базовый буфер в свободном хранилище.
Инициализация std :: vector
std::vector может быть инициализирован несколькими способами, объявляя его:
Вектор может быть инициализирован из другого контейнера несколькими способами:
Скопировать построение (только с другого вектора), которое копирует данные из v2 :
Переместить конструкцию (только из другого вектора), которая перемещает данные из v2 :
Итератор (диапазон) copy-construction, который копирует элементы в v :
Перемещение итератора с использованием std::make_move_iterator , который перемещает элементы в v :
С помощью функции-члена assign() , std::vector может быть повторно инициализирован после его построения:
Вставка элементов
Добавление элемента в конце вектора (путем копирования / перемещения):
Добавление элемента в конец вектора путем создания элемента на месте:
Обратите внимание, что std::vector не имеет функции-члена push_front() из-за причин производительности. Добавление элемента в начале приводит к перемещению всех существующих элементов в векторе. Если вы хотите часто вставлять элементы в начале вашего контейнера, вы можете вместо этого использовать std::list или std::deque .
Вставка элемента в любую позицию вектора:
Вставка элемента в любую позицию вектора путем построения элемента на месте:
Вставка другого вектора в любую позицию вектора:
Вставка массива в любую позицию вектора:
Используйте use reserve() перед тем, как вставить несколько элементов, если результирующий векторный размер известен заранее, чтобы избежать множественных перераспределений (см. Размер и емкость вектора ):
Обязательно не делайте ошибку при вызове resize() в этом случае, или вы случайно создадите вектор с 200 элементами, в которых только последняя ста будет иметь значение, которое вы намеревались.
Итерация над std :: vector
Вы можете перебирать std::vector несколькими способами. Для каждого из следующих разделов v определяется следующим образом:
Итерация в прямом направлении
Итерация в обратном направлении
Хотя нет встроенного способа использовать диапазон, основанный на обратном итерации; относительно просто исправить это. Диапазон, основанный на использовании begin() и end() для получения итераторов, и, таким образом, имитация этого объекта-обертки может обеспечить требуемые результаты.
Принудительные элементы const
Начиная с C ++ 11 cbegin() и cend() позволяют получить константный итератор для вектора, даже если вектор не const. Постоянный итератор позволяет вам читать, но не изменять содержимое вектора, что полезно для обеспечения корректности const:
as_const расширяет это до итерации диапазона:
Это легко реализовать в более ранних версиях C ++:
Замечание об эффективности
Поскольку класс std::vector — это в основном класс, который управляет динамически распределенным смежным массивом, тот же принцип, описанный здесь, относится к векторам C ++. Доступ к содержимому вектора по индексу намного эффективнее при соблюдении принципа строкового порядка. Разумеется, каждый доступ к вектору также помещает его содержимое управления в кеш, но, как обсуждалось много раз (особенно здесь и здесь ), разница в производительности для итерации по std::vector по сравнению с необработанным массивом является незначительным. Таким образом, тот же принцип эффективности для необработанных массивов в C также применяется для std::vector C ++.
Доступ к элементам
Существует два основных способа доступа к элементам в std::vector
- доступ по индексу
- итераторы
Доступ по индексу:
Это можно сделать либо с помощью оператора индекса [] , либо с помощью функции-члена at() .
Оба возвращают ссылку на элемент в соответствующей позиции в std::vector (если это не vector<bool> ), так что он может быть прочитан, а также изменен (если вектор не const ).
[] и at() отличаются тем, что [] не гарантированно выполняет проверку границ, а at() . Доступ к элементам, где index < 0 или index >= size является неопределенным поведением для [] , а at() выбрасывает исключение std::out_of_range .
Примечание. В приведенных ниже примерах для ясности используется инициализация типа C ++ 11, но операторы могут использоваться со всеми версиями (если не указано C ++ 11).
Поскольку метод at() выполняет проверку границ и может генерировать исключения, он медленнее, чем [] . Это делает [] предпочтительным кодом, где семантика операции гарантирует, что индекс находится в границах. В любом случае доступ к элементам векторов осуществляется в постоянное время. Это означает, что доступ к первому элементу вектора имеет одинаковую стоимость (по времени) доступа к второму элементу, третьему элементу и так далее.
Например, рассмотрим этот цикл
Здесь мы знаем, что индексная переменная i всегда находится в границах, поэтому было бы потерей циклов ЦП, чтобы проверить, что i находится в границах для каждого вызова operator[] .
Функции функции front() и back() позволяют легко обращаться к первому и последнему элементу вектора соответственно. Эти позиции часто используются, и специальные аксессоры могут быть более читабельными, чем их альтернативы, используя [] :
Примечание . Неопределенное поведение вызывает функцию front() или back() для пустого вектора. Вы должны проверить , что контейнер не опустошить , используя empty() функции — члена (который проверяет , если контейнер пуст) перед вызовом front() или back() . Простой пример использования 'empty ()' для проверки пустого вектора:
В приведенном выше примере создается вектор с последовательностью чисел от 1 до 10. Затем он выталкивает элементы вектора до тех пор, пока вектор не станет пустым (используя «empty ()»), чтобы предотвратить неопределенное поведение. Затем вычисляется сумма чисел в векторе и отображается пользователю.
Метод data() возвращает указатель на необработанную память, используемую std::vector для внутреннего хранения своих элементов. Это чаще всего используется при передаче векторных данных в устаревший код, который ожидает массив C-стиля.
Перед C ++ 11 метод data() можно моделировать, вызывая front() и принимая адрес возвращаемого значения:
Это работает, потому что векторы всегда гарантированно сохраняют свои элементы в смежных ячейках памяти, предполагая, что содержимое вектора не переопределяет унарный operator& . Если это произойдет, вам придется повторно реализовать std::addressof в pre-C ++ 11. Он также предполагает, что вектор не пуст.
итераторы:
Итераторы более подробно объясняются в примере «Итерация по std::vector » и статье « Итераторы» . Короче говоря, они действуют аналогично указателям на элементы вектора:
Это соответствует стандарту, что итераторы std::vector<T> на самом деле являются T* s, но большинство стандартных библиотек этого не делают. Не делая этого и улучшает сообщения об ошибках, улавливает непереносимый код и может использоваться для управления итераторами с проверками отладки в сборках без релиза. Затем в релиз-сборках класс, обтекающий базовый указатель, оптимизирован.
Вы можете сохранить ссылку или указатель на элемент вектора для косвенного доступа. Эти ссылки или указатели на элементы в vector остаются стабильными, и доступ остается определенным, если вы не добавляете / не удаляете элементы в элементе или перед элементом в vector , или вы не можете изменить vector емкость. Это то же самое, что и правило для недействительности итераторов.
Использование std :: vector в качестве массива C
Существует несколько способов использования std::vector в качестве массива C (например, для совместимости с библиотеками C). Это возможно, потому что элементы в векторе хранятся смежно.
В отличие от решений, основанных на предыдущих стандартах C ++ (см. Ниже), функция-член .data() также может применяться к пустым векторам, поскольку в этом случае она не вызывает неопределенного поведения.
Перед C ++ 11 вы берете адрес первого элемента вектора для получения эквивалентного указателя, если вектор не пуст, эти оба метода взаимозаменяемы:
Примечание. Если вектор пуст, v[0] и v.front() не определены и не могут быть использованы.
При сохранении базового адреса данных вектора обратите внимание, что многие операции (такие как push_back , resize и т. Д.) Могут изменить местоположение памяти данных вектора, тем самым аннулируя предыдущие указатели данных . Например:
Итератор / указатель Invalidation
Итераторы и указатели, указывающие на std::vector могут стать недействительными, но только при выполнении определенных операций. Использование недействительных итераторов / указателей приведет к неопределенному поведению.
Операции, которые делают недействительными итераторы / указатели, включают:
Любая операция вставки, которая изменяет capacity vector , аннулирует все итераторы / указатели:
Любая операция вставки, которая не увеличивает емкость, все равно приведет к недействительности итераторов / указателей, указывающих на элементы в позиции вставки и мимо нее. Это включает в себя end итератор:
Любая операция удаления приведет к недействительности итераторов / указателей, указывающих на удаленные элементы и на любые элементы, прошедшие удаленные элементы. Это включает в себя end итератор:
operator= (копирование, перемещение или иное) и clear() приведет к аннулированию всех итераторов / указателей, указывающих на вектор.
Удаление элементов
Удаление последнего элемента:
Удаление всех элементов:
Удаление элемента по индексу:
Примечание. Для vector удаляющего элемент, который не является последним элементом, все элементы за удаленным элементом должны быть скопированы или перемещены, чтобы заполнить пробел, см. Примечание ниже и std :: list .
Удаление всех элементов в диапазоне:
Примечание . Вышеуказанные методы не изменяют емкость вектора, а только размер. См. Размер и емкость файла .
Метод erase , который удаляет ряд элементов, часто используется как часть идиомы стирания-удаления . То есть, сначала std::remove перемещает некоторые элементы в конец вектора, а затем erase их. Это относительно неэффективная операция для любых индексов, меньших последнего индекса вектора, потому что все элементы после стертых сегментов должны быть перемещены в новые позиции. Для критически важных приложений, требующих эффективного удаления произвольных элементов в контейнере, см. Std :: list .
Удаление элементов по значению:
Удаление элементов по условию:
Удаление элементов с помощью лямбда, не создавая дополнительной функции предиката
Удаление элементов по условию из цикла:
Хотя важно не увеличивать it в случае удаления, вам следует рассмотреть возможность использования другого метода при повторном стирании в цикле. Рассмотрим remove_if для более эффективного способа.
Удаление элементов по условию из обратной петли:
Обратите внимание на некоторые моменты для предыдущего цикла:
Учитывая обратный итератор it , указывая на какой — то элемент, метод base дает регулярный (не обратный) итератор , указывающий на тот же элемент.
vector::erase(iterator) стирает элемент, на который указывает итератор, и возвращает итератор элементу, который следует за данным элементом.
reverse_iterator::reverse_iterator(iterator) строит обратный итератор с итератора.
Помещенный в целом, линия it = rev_itr(v.erase(it.base())) говорит: взять реверсивный итератор it , есть v Сотрите элемент указал его регулярной итератора; принимает полученный итератор, построить обратный итератор от него, и назначить его на обратный итератор it .
Удаление всех элементов с помощью v.clear() не освобождает память ( capacity() вектора остается неизменной). Чтобы освободить место, используйте:
shrink_to_fit() освобождает неиспользованную емкость вектора:
Функция shrink_to_fit не гарантирует shrink_to_fit освобождения пространства, но большинство современных реализаций.
Поиск элемента в std :: vector
Функция std::find , определенная в заголовке <algorithm> , может использоваться для поиска элемента в std::vector .
std::find использует operator== для сравнения элементов для равенства. Он возвращает итератор в первый элемент в диапазоне, который сравнивается с значением.
Если этот элемент не найден, std::find возвращает std::vector::end (или std::vector::cend если вектор const ).
Если вам нужно выполнить много запросов в большом векторе, вы можете сначала рассмотреть сортировку вектора, прежде чем использовать алгоритм binary_search .
Чтобы найти первый элемент в векторе, который удовлетворяет условию, можно использовать std::find_if . В дополнение к двум параметрам, заданным для std::find , std::find_if принимает третий аргумент, который является объектом функции или указателем функции на функцию предиката. Предикат должен принять элемент из контейнера в качестве аргумента и вернуть значение, конвертируемое в bool , без изменения контейнера:
Преобразование массива в std :: vector
Массив можно легко преобразовать в std::vector , используя std::begin и std::end :
C инициализатор_класса C ++ 11 может также использоваться для инициализации вектора сразу
вектор : Исключение для многих, так много правил
Стандарт (раздел 23.3.7) указывает, что предоставляется специализация vector<bool> , которая оптимизирует пространство, упаковывая значения bool , так что каждый занимает только один бит. Поскольку биты не адресуются в C ++, это означает, что на vector<bool> не помещаются несколько требований к vector :
- Сохраненные данные не обязательно должны быть смежными, поэтому vector<bool> не может быть передан в API C, который ожидает массив bool .
- at() , operator [] , а разыменование итераторов не возвращает ссылку на bool . Скорее они возвращают прокси-объект, который (несовершенно) имитирует ссылку на bool , перегружая его операторы присваивания. В качестве примера следующий код может быть недействительным для std::vector<bool> , поскольку разыменование итератора не возвращает ссылку:
Аналогично, функции, ожидающие bool& аргумент, не могут использоваться с результатом operator [] или at() примененного к vector<bool> , или с результатом разыменования его итератора:
Реализация std::vector<bool> зависит как от компилятора, так и от архитектуры. Специализация реализуется путем упаковки n Booleans в младший адресный раздел памяти. Здесь n — это размер в битах самой младшей адресуемой памяти. В большинстве современных систем это 1 байт или 8 бит. Это означает, что один байт может хранить 8 булевых значений. Это улучшение по сравнению с традиционной реализацией, где 1 булево значение хранится в 1 байт памяти.
Примечание. В приведенном ниже примере показаны возможные побитовые значения отдельных байтов в традиционном и оптимизированном vector<bool> . Это не всегда верно для всех архитектур. Это, однако, хороший способ визуализации оптимизации. В приведенных ниже примерах байт представлен как [x, x, x, x, x, x, x, x].
Традиционный std::vector<char> Сохранение 8 Булевых значений:
Специализированный std::vector<bool> Сохранение 8 Булевы значения:
Обратите внимание, что в традиционной версии std::vector<bool> 8 булевых значений занимают 8 байт памяти, тогда как в оптимизированной версии std::vector<bool> они используют только 1 байт объем памяти. Это значительное улучшение использования памяти. Если вам нужно передать vector<bool> в API стиля C, вам может потребоваться скопировать значения в массив или найти лучший способ использования API, если память и производительность подвержены риску.
Размер и емкость вектора
Размер вектора — это просто количество элементов в векторе:
Текущий размер вектора запрашивается функцией size() . Функция удобство empty() возвращает true если размер равен 0:
По умолчанию сконструированный вектор начинается с размера 0:
Добавление N элементов к вектору увеличивает размер на N (например, с помощью функций push_back() , insert() или resize() ).
Удаление N элементов из вектора уменьшает размер на N (например, с помощью pop_back() , pop_back() erase() или clear() ).
Вектор имеет верхний предел для реализации по размеру, но вы, скорее всего, исчерпаете ОЗУ до его достижения:
Общая ошибка: размер не обязательно (или даже обычно) int :
Векторная емкость отличается от размера . В то время как размер — это просто количество элементов, которые вектор имеет в настоящее время, емкость для количества элементов, на которые он выделил / зарезервировал память. Это полезно, потому что слишком частые (пере) выделения слишком больших размеров могут быть дорогими.
Текущая емкость вектора запрашивается функцией функции capacity() . Емкость всегда больше или равна размеру :
Вы можете вручную зарезервировать емкость по reserve( N ) функции (она меняет векторную емкость на N ):
Вы можете запросить избыточную емкость, которая будет выпущена с помощью shrink_to_fit() (но реализация не должна вас подчиняться). Это полезно для сохранения использованной памяти:
Вектор частично управляет емкостью автоматически, когда вы добавляете элементы, которые он может решить, чтобы расти. Исполнители любят использовать 2 или 1,5 для фактора роста (золотое соотношение будет идеальным значением, но нецелесообразным из-за рационального числа). С другой стороны, вектор обычно не сжимается автоматически. Например:
Конкатенационные векторы
Один std::vector может быть добавлен к другому с помощью функции-члена insert() :
Однако это решение выходит из строя, если вы пытаетесь добавить вектор к себе, потому что стандарт указывает, что итераторы, данные для insert() не должны быть того же диапазона, что и элементы объекта получателя.
Вместо использования функций-членов вектора можно использовать функции std::begin() и std::end() :
Это более общее решение, например, поскольку b также может быть массивом. Однако это решение не позволяет вам добавлять вектор к себе.
Если порядок элементов в принимающем векторе не имеет значения, учитывая количество элементов в каждом векторе, можно избежать ненужных операций копирования:
Уменьшение пропускной способности вектора
std::vector автоматически увеличивает свою емкость при вставке по мере необходимости, но никогда не уменьшает ее емкость после удаления элемента.
Чтобы уменьшить его емкость, мы можем скопировать содержимое вектора в новый временный вектор. Новый вектор будет иметь минимальную емкость, необходимую для хранения всех элементов исходного вектора. Если уменьшение размера исходного вектора было значительным, то уменьшение емкости для нового вектора, вероятно, будет значительным. Затем мы можем поменять исходный вектор на временный, чтобы сохранить его минимальную емкость:
В C ++ 11 мы можем использовать shrink_to_fit() члена shrink_to_fit() для аналогичного эффекта:
Примечание. Функция shrink_to_fit() является запросом и не гарантирует уменьшение емкости.
Использование сортированного вектора для быстрого поиска элементов
Заголовок <algorithm> предоставляет ряд полезных функций для работы со отсортированными векторами.
Важным предварительным условием для работы с отсортированными векторами является то, что сохраненные значения сравнимы с < .
Несортированный вектор можно отсортировать с помощью функции std::sort() :
Сортированные векторы позволяют эффективно искать элементы, используя функцию std::lower_bound() . В отличие от std::find() , он выполняет эффективный двоичный поиск на векторе. Недостатком является то, что он дает только действительные результаты для отсортированных диапазонов ввода:
Примечание. Если запрошенное значение не является частью вектора, std::lower_bound() вернет итератор в первый элемент, который больше запрашиваемого значения. Такое поведение позволяет нам вставить новый элемент в нужное место в уже отсортированном векторе:
Если вам нужно вставить сразу несколько элементов, возможно, более эффективно сначала вызвать push_back() для всех них, а затем вызвать std::sort() после того, как будут вставлены все элементы. В этом случае увеличенная стоимость сортировки может окупиться сниженной стоимостью вставки новых элементов в конце вектора, а не в середине.
Если ваш вектор содержит несколько элементов одного значения, std::lower_bound() попытается вернуть итератор первому элементу std::lower_bound() значения. Однако, если вам нужно вставить новый элемент после последнего элемента std::upper_bound() значения, вы должны использовать функцию std::upper_bound() поскольку это приведет к меньшему смещению элементов:
Если вам нужны итераторы верхней и нижней границ, вы можете использовать функцию std::equal_range() для эффективного извлечения обоих из них одним вызовом:
Чтобы проверить, существует ли элемент в отсортированном векторе (хотя это и не относится к векторам), вы можете использовать функцию std::binary_search() :
Функции, возвращающие большие векторы
В C ++ 11 компиляторы должны неявно перемещаться из локальной возвращаемой переменной. Более того, большинство компиляторов во многих случаях могут выполнять копирование и исключать переход вообще. В результате этого возвращение больших объектов, которые могут быть перемещены дешево, больше не требует специальной обработки:
Перед C ++ 11, копирование elision было уже разрешено и реализовано большинством компиляторов. Однако из-за отсутствия семантики перемещения в устаревшем коде или коде, который должен быть скомпилирован со старыми версиями компилятора, которые не реализуют эту оптимизацию, вы можете найти векторы, передаваемые в качестве выходных аргументов, чтобы предотвратить ненужную копию:
Найти максимальный и минимальный элемент и соответствующий индекс в векторе
Чтобы найти самый большой или самый маленький элемент, хранящийся в векторе, вы можете использовать методы std::max_element и std::min_element соответственно. Эти методы определены в заголовке <algorithm> . Если несколько элементов эквивалентны наибольшему (наименьшему) элементу, методы возвращают итератор в первый такой элемент. Вернуть v.end() для пустых векторов.
maxElementIndex: 3, maxElement: 10
minElementIndex: 1, minElement: 2
Минимальный и максимальный элемент в векторе можно получить одновременно, используя метод std::minmax_element , который также определен в заголовке <algorithm> :
минимальный элемент: 2
максимальный элемент: 10
Матрицы с использованием векторов
Векторы могут использоваться в качестве 2D-матрицы, определяя их как вектор векторов.
Матрица с 3 строками и 4 столбцами с каждой ячейкой, инициализированной как 0, может быть определена как:
Синтаксис для их инициализации с использованием списков инициализации или иначе аналогичен синтаксису нормального вектора.
Значения в таком векторе могут быть доступны аналогично двумерному массиву
Итерация по всей матрице аналогична и для нормального вектора, но с дополнительной размерностью.
Вектор векторов — удобный способ представления матрицы, но это не самый эффективный: отдельные векторы разбросаны по памяти, а структура данных не кэширована.
Кроме того, в соответствующей матрице длина каждой строки должна быть одинаковой (это не относится к вектору векторов). Дополнительная гибкость может быть источником ошибок.
Name already in use
https://en.cppreference.com/w — это сайт с документацией по языку C++. Там вы можете найти много полезной информации как о самом языке, так и о его стандартных библиотеках. Здесь же вы сможете найдите краткое изложение самого полезного из STL.
Поговорим об обычных сишных массивах
Если вы пишите так, прекращайте, у этого метода много проблем, давайте напишем правильную реализацию и обговорим плюсы и минусы.
Указатели (итераторы) на начало и конец — прекрасная вещь, которую мы обсудим позже
Сишные массивы уже сейчас противоречат шаблону, в будущем их хотят вообще убрать, так что лучше от них отказаться сейчас
Быстрый переход от массива к вектору
- Тяжело отвыкнуть от старого массива.
vector — это динамический массив. Это означает, что его размер может меняться во время исполнения программы, вы можете добавлять элементы в конец и так далее. Чтобы объявить пустой vector , способный содержать в себе целые числа типа T , необходимо воспользоваться следующей конструкцией:
Здесь T — это тип элементов, которые будут содержаться в vector , а vector_name — имя самого vector . Как и другие контейнеры C++, vector не может содержать элементы разных типов!
Чтобы добавить элемент в конец вектора, необходимо воспользоваться функцией push_back . Эта функция работает в среднем за $O(1)$ .
Существуют два способа обращения к ‘vector’. Оба мы уже обсудили в массивах.
Кроме этого вам также могут потребоваться следующие методы :
Как работает vector?
Как уже было сказано, добавление в конец вектора работает в среднем за $O(1)$ . Это означает, что, если вы сделаете $n$ операций push_back , они будут в сумме работать за $O(n)$ . (Но при этом некоторые из них могли работать и за линейное время!)
У vector есть 2 важные величины: size и capacity — размер и вместимость. Размер — это то, сколько элементов сейчас находится в векторе. Вместимость — то, под сколько элементов памяти выделено. Когда size < capacity , push_back просто добавляет новый элемент в первую свободную ячейку уже выделенной памяти, поэтому работает за $O(1)$ . Когда size = capacity , так сделать не удастся. Поэтому, происходит следующее:
- capacity увеличивается примерно в 2 раза.
- Выделяется область памяти, вмещающая capacity элементов.
- Элементы из старой области памяти копируются в новую.
- Старая область памяти освобождается.
Поймём, почему амортизированное время работы push_back действительно равно $O(1)$ . Пусть сейчас capacity = $n$ . Тогда мы выделяли $n + \frac
Получить capacity у vector можно с помощью одноимённой функции. Рассмотрим пример того, как изменяется capacity .
pair — это тип, содержащий пару значений, притом значения могут быть разных типов. Объявление пары выглядит так:
Здесь T1 и T2 — это имена первого и второго типов, соответственно.
Первый элемент пары — это p.first ; второй — p.second .
make_pair(a, b) — функция, которая создаёт пару $(a, b)$ .
Рассмотрим пример работы с pair .
В c++ уже реализована такая структура, как очередь, она названа queue.
Очередь — структура, реализующая принцип FIFO (первый пришел — первый вышел), то есть для очереди существуют две основные функции : Вставить в конец и достать с начала.
deque — структура, позволяющая работать и с началом и концом одновременно, то есть вставка и удаление с двух сторон
Очередь и дек будут более подробно рассмотрены на одном из следующих занятий.
Итератор — это объект, указывающий на элемент контейнера. Чтобы получить элемент, на который указывает итератор it , необходимо воспользоваться оператором разыменования: *it . Также если вам нужно перейти к следующему элементу надо использовать инкремент: ++it .
Есть несколько категорий итераторов:
- InputIterator . Он поддерживает только операции разыменования и инкремента, притом после того, как был произведён инкремент, все копии его предыдущего значения могут стать невалидными.
- ForwardIterator . Поддерживает то же, что и InputIterator , но итератор, указывающий на какой-то конкретный элемент, можно инкрементировать сколько угодно раз.
- BidirectionalIterator . Поддерживает то же, что и ForwardIterator , но также есть возможность производить декремент ( it— ) — переходить к предыдущему элементу коллекции.
- RandomAccessIterator . Поддерживает то же, что и BidirectionalIterator , но также есть возможность переходить к элементу коллекции, который находится от данного на каком-то расстоянии $k$ . Так, например, для итератора it возможны следующии операции: it + k , it — k , it += k , it -= k . Также можно находить расстояние между двумя позициями, на которые указывают итератора. Так, например, выражение a — b будет означать расстояние между двумя элементами коллекции, на которые указывают итераторы a и b .
Рассмотрим использование итераторов на примере vector . Для вектора a итератор на его первый элемент можно получить так: a.begin() . Также есть функция, которая возвращает итератор на фиктивный элемент, следующий за последним элементом вектора: a.end() . Таким образом, весь a задаётся полуинтервалом [a.begin(); a.end()) (левый конец включается, правый — нет).
Итераторы у vector относятся к категории RandomAccessIterator , то есть например мы можем узнать размер vector $a$ , просто взяв a.begin() — a.end() . При этом у vector типа vector<T> итератор будет иметь тип vector<T>::iterator .
Рассмотрим пример работы с итераторами у vector .
list — структура, которая поддерживает быструю вставку и удаление элементов из любой позиции в контейнере. Быстрый произвольный доступ, к сожалению, не поддерживается (то есть мы не можем быстро взять $i$ -й элемент). Он реализован в виде двусвязного списка
set — это коллекция, которая содержит множество уникальных упорядоченных элементов.
Чтобы добавить элемент в set , есть функция insert . В случае, если элемент уже был в множестве, ничего не происходит.
Чтобы удалить элемент из set , есть функция erase (в нее можно передать либо итератор на элемент, либо просто элемент). В случае, если элемента не было в множестве, ничего не происходит.
Чтобы посмотреть, если ли элемент в set , есть функция count . Она вернёт $0$ , если элемента нет в множестве, и $1$ , если он есть. Также есть метод find , который возвращает итератор на элемент или end , если элемента нет.
Все операции с элементами set (добавление, удаление, поиск) работают за $O(\log n$ ), где $n$ — количество элементов в нём, так как он реализован с помощью сбалансированного двоичного дерева поиска.
Итераторы set относятся к категории BidirectionalIterator и имеют тип set<T>::iterator . Начало set можно получить с помощью функции begin , конец — с помощью функции end . Как и в случае с вектором, end указывает на конец полуинтервала. Инкремент и декремент итераторов set также работают за логарифмическое время.
Стоит отметить, что, так как элементы в set упорядочены, с помощью begin и end можно искать наименьший/наибольший элемент в set . Чтобы найти наименьший элемент, больший или равный заданному, есть функция lower_bound .
Чтобы найти наименьший элемент, строго больший заданному, есть функция upper_bound .
Каждая из этих функций возвращает итератор на искомый элемент или end() , если такого элемента не существует.
set может содержать только элементы тех типов, для которых определён оператор < , поскольку ему важен порядок элементов.
Рассмотрим пример простейших операций с set .
multiset — то же, что и set , но может содержать повторяющиеся элементы.
count работает за $O(\log n + c)$ , где $c$ — количество искомых элементов. Поэтому, чтобы проверить наличие элемента $el$ в multiset s , надо воспользоваться: s.find(el) != s.end() .
erase удаляет все элементы с таким значением. Чтобы удалить один надо делать так: `s.erase(s.find(el)).
Примеры применения сета для решения задач
Очень часто использование сета позволяет решить задачу, которая решается и абсолютно другим способом. Иногда более сложным, а иногда и более простым. Чаще всего сет используется, если нужно сделать что-то, связанное с количеством разных элементов или с минимумом или максимум какого-то множества.
1) Задача Девшука или Юноша
Условие вкратце: Найти чётность числа различных символов в строке.
Решение: вставим все символы в сет и проверим четность размера сета.
Заметим, что эту задачу можно легко решить и подсчетом (как в сортировке подсчетом), так как символов бывает очень мало.
2) A и B и ошибки компиляции
Условие вкратце: Из массива убрали ровно одно число и перемешали элементы. Затем сделали так еще раз. Найдите, какие два элемента исчезли.
Решение: Добавим все числа в 3 различных мультисета, затем просто пройдемся по ним и найдем первый элемент, которого во втором меньше, чем в первои, но есть в первом. Мы нашли первую ошибку, вторая находится точно также.
Заметим, что эту задачу можно было бы легко решить и просто отсортировав все числа, что асимптотически тоже $O(N log N)$ .
3) Минимум на отрезке
Условие вкратце: Найти минимум на каждом отрезке длины $K$ в массиве.
Решение: Давайте положим в мультисет первые $K$ элементов. Далее мы будем двигать это «окно»: добавлять новый элемент справа и убирать самый левый элемент. Каждый раз будем выводить минимум в сете, который лежит в s.begin() .
Также эта задача решается такими структурами данных как
Очередь с минимумом (за $O(N)$ !)
Но решить задачу сетом гораздо проще.
map — это ассоциативный контейнер: он содержит пары ключ-значение, при этом все ключи уникальны. Внутри контейнера все ключи упорядочены по возрастанию. Так же, как и в set , операции работают за логарифмическое время.
Объявление map выглядит так: map<T1, T2> map_name , где T1 — тип ключа, T2 — тип значения.
Доступ к элементам map осуществляется с помощью оператора [] . map , аналогично set , поддерживает поиск по ключу с помощью find , lower_bound , upper_bound . При разыменовании итератора получается пара, первый элемент которой — ключ, второй — значение.
При обращении к несуществующему элементу map с помощью [] , значение инициализируется значением по умолчанию для данного типа.
Рассмотрим работу map на примере:
Unordered структуры данных
Единственная проблема set и map — то что они работают за $\log(n)$ , что в некоторых задачах долго. Тогда возникает идея построить их не на двоичном дереве, а например на хештаблице (о ней вы узнаете на втором курсе), тогда unordered_set поддерживает вставку и удаление за $O(1)$ , единственная проблема — он содержит элементы в неотсортированном порядке, то есть мы уже не сможем искать минимум, максимум.
На питоне встроенные set и dict — это именно аналоги unordered_set и unordered_map. Упорядоченного сета и мэпа на питоне нет.
Полезные функции из algorithm
swap(a, b) — обменивает значения переменных a и b местами.
min_element и max_element
min_element(first, last) — возвращает итератор на минимум на полуинтервале [first; last) .
max_element(first, last) — возвращает итератор на максимум на полуинтервале [first; last) .
Если минимумов/максимумов несколько, то возвращается первое вхождение.
reverse(first, last) — переворачивает полуинтервал [first; last) (элементы идут в обратном порядке).
В этом примере будет выведено 3 2 5 10 17 .
sort, unique и компараторы
sort(first, last) — сортирует полуинтервал [first; last) .
В этом примере будет выведено 2 2 3 5 10 11 .
Функция sort может принимать третий параметр — компаратор. Компаратор — это функция, которая принимает два объекта и возвращает true , если первый строго меньше второго, и false иначе.
Допустим, нам хотелось бы отсортировать числа по возрастанию их последней цифры, а при совпадении — по самому значению. Тогда мы могли бы написать следующий код:
В данном примере, как мы и хотели, будет выведено 30 12 32 15 7 .
unique(first, last) — принимает полуинтервал и удаляет все последовательные повторения элементов в нём. Функция возвращает итератор на конец полуинтервала, соответствующему уникализированным элементам. Значения элементов, которые следуют после этого полуинтервала, становятся неопределёнными. Поэтому рекомендуется использовать функцию unique , например, вместе с функцией resize .
В данном примере будет выведено 5 1 5 4 7 1 .
Часто требуется сначала отсортировать элементы, а потом убрать все повторения. Это делается следующей комбинацией:
Функция ставит на переданную позицию элемент, который был бы на этом месте после сортировки массива(работает за линию).
Генерирует следующую и предыдущую перестановку массива на отрезке с l по r;
Слияние двух массивов, которое используется в сортировке слиянием.
lower_bound, upper_bound, binary_search
Все эти функции принимают полуинтервал [first; last) и значение value . Полуинтервал должен быть упорядочен по отношению element < value (сначала те элементы, которые удовлетворяют этому, потом остальные).
lower_bound — возвращает первый элемент, больший или равный value .
upper_bound — возвращает первый элемент, строго больший value .
binary_search — возвращает, присутствует ли value на этом полуинтервале.
Не используйте lower_bound , upper_bound , binary_search вместе с set / map ! Они будут работать за линейное время. Используйте их собственные функции: set::lower_bound (вызывается через . ) и так далее.
Ускорение ввода и вывода
Стандартные cin и cout работают очень медленно. Чтобы исправить это, в начале вашей функции main пишите следующее:
Это позволяет ускорить ввод и вывод в разы!
Также крайне не рекомендуется использовать endl (кроме интерактивных задач). Используйте «\n» . Они отличаются тем, что endl делает flush вывода, то есть сразу же выводит то, что вы хотите. Если вы будете использовать «\n» , вывод будет накапливаться, а потом единожды выводиться, что гораздо быстрее.
Это просто олимпиадные задачи, но почти в любой задаче можно использовать STL, чтобы упростить себе жизнь.