Vector
Рассмотрим первый контейнер — альтернативу массиву — vector. Представленный в C++03, vector — это динамический массив, который может сам управлять выделенной для себе памятью. Это означает, что вы можете создавать массивы, длина которых задается во время выполнения. vector находится в заголовочном файле vector
Подобно массивам доступ к элементам может выполняться как через оператор [] (который не выполняет проверку диапазона), так и через функцию at(). Отличие метода at от обращения при помощи квадратных скобок в том, что при использовании метода at происходит проверка правильности индекса, и в случае выхода за границы вектора происходит ошибка исполнения. Это полезно при отладке программ.
Также vector позволяет верунть “первый” и “последний” эдемент с помощью функций front и back
Изменение размера вектора
Размер вектора можно узнать при помощи метода size() . Также есть метод empty() , возвращающий логическое значение (true, если вектор пустой).
Размер вектора можно изменить в любой момент, при помощи метода resize . У этого метода может быть один или два параметра. Вызов метода resize(n) изменяет размер вектора до n элементов (длина вектора может как уменьшится, так и увеличиться). Вызов метода resize(n, val) изменяет размер вектора до n элементов, и если при этом размер вектора увеличивается, то новые элементы получают значение, равное val.
Очень часто бывает полезно добавлять элементы в конец вектора по одному и удалять элементы из конца вектора по одному. Для добавления нового элемента, равного val, в конец вектора, используется метод push_back(val) . Для удаления последнего элемента вектора используется метод pop_back() — он не возвращает значения.
Добавление элемента в конец вектора осуществляется в среднем за O(1) (подробнее об O-нотации будет позже. Для нас счейчас можно отметить, что данная операция самая быстрая). Это реализовано за счет того, что память для хранения элементов вектора выделяется “с запасом”, то есть можно будет добавлять элементы по одному, пока не кончится запас памяти. Если запас памяти исчерпан, выделяется новая память, при этом “запас” размера вектора удваивается.
Очистить вектор можно при помощи метода clear() . Есить глобальная функиця swap , которая позволяем поменять местами содержимое двух векторов.
Вставка и удаление элементов в середину вектора
Метод erase позволяет удалять из середины вектора один или несколько элементов. Этот метод работает с итераторами. Подробнее
Метод insert позволяет вставлять в середину вектора новый элемент, или несколько равных элементов, или другой вектор, или фрагмент другого вектора. Подробнее
Поскольку вставка и удаление элементов требуют сдвига других элементов вектора, эти операции имеют линейную сложность, то есть выполняются за время, пропорциональное длине вектора.
Присваивание и сравнение векторов
Содержимое одного вектора можно целиком скопировать в другой вектор при помощи операции присваивания: A = B .
Также вектора можно сравнивать на равенство и неравенство ( A == B , A != B ), и сравнивать их содержимое в лексикографическом порядке ( A < B , A <= B , A > B , A >= B ).
Создание многомерных векторов
Элементами вектора могут быть и другие вектора. Например, можно сделать вектор, каждый элемент которого представляет собой вектор целых чисел:
Тем самым, a[i] будет вектором целых чисел, а обращаться к j-му элементу вектора a[i] можно через a[i][j].
Чтобы создать двумерный вектор размером n×m можно внешний вектор объявить размером n, а затем в цикле изменить размер каждого вложенного вектора:
Но можно сделать это и в одну строку, если передать вторым параметром для конструктора вектора конструктор, который создает вектор целых чисел длины m:
Просто о списках, словарях и множествах или ТОП 5 структур данных
Привет. Ей! Не говорите “Да блин! Я знаю, чем отличается список от вектора, мне не нужна эта статья”. Прошу, загляните под кат и освежите свои знания. Я надеюсь, однако, что вы сможете почерпнуть из этой статьи намного больше и, некоторые, возможно, наконец-то разберутся, почему существует так много типов данных для коллекций объектов.
Введение
Так уж сложилось, что в программировании коллекции представляет много, нет ОЧЕНЬ МНОГО различных сущностей — списки, массивы, вектора, множества, стеки, очереди, ассоциативные массивы и у большинства из этих структур данных есть еще по несколько подвидов.
Должны же быть причины, чтобы для простого представления какой-либо совокупности объектов существовало настолько много различных вариаций.
Должны же быть отличия между списком и массивом? Между ассоциативным массивом и хеш-таблицей?
Коллекция
Для начала — самое скучное (да, я люблю такое). Что такое коллекция вообще?
Коллекция — структура данных (тип, класс, даже лучше сказать интерфейс), которая создана, чтобы содержать в себе некоторое количество объектов (в зависимости от языка и терминологии они должны быть одного типа или могут быть разных типов).
Различные типы коллекций могут быть статическими или динамическими, т.е. изменять свой размер или оставаться постоянными, могут быть упорядоченными (точнее учитывающими порядок элементов) и неупорядоченными (соответственно не учитывающими).
Над коллекциями предусмотрено несколько стандартных операций (сейчас мы поговорим о мутабельных, т.е. изменяемых коллекциях), таких как: получение размера, добавление элемента, удаление элемента, поиск (есть какой-либо элемент в коллекции или нет), их очень много.
Ладно, свой негласный долг я выполнил, теперь поехали!
1 Вектор (Vector, Array)
А вы чего ждали?
Вектор (он же одномерный массив) — упорядоченный набор элементов с произвольным доступом по числовому индексу. Что для нас важно в этом определении? Да ничего. Шучу, на самом деле нам важно почти каждое слово:
Доступ к элементам производится по числовому индексу (обычно начиная с 0-го индекса, хотя есть и исключения), обычно доступ к элементу коллекции по индексу записывается как myFavoriteCats[i] или blackKitties[5]. Причем для обозначения этого самого числа — индекса используют букву i.
А когда одной буквы не хватает приплетают сюда j и k.
Итак, далее мы понимаем, что доступ произвольный — значит мы можем обращаться к элементам под индексами 0, 42, 2014 и вобщем-то ожидаем, что операция будет сложности O(1), т.е. константной и независимо от того какой из элементов мы запросим он нам со скоростью света тут же вернется.
Далее — вектор — упорядоченная коллекция, что собственно понятно — у нас есть такие понятия как первый, последний элемент, для каждого конкретно взятого элемента мы также можем назвать предыдущий и следующий.
Релизация
Обычно вектор (как низкоуровневая структура) будет представлять из себя дескриптор, содержащий различную информацию, неотделимую от самой структуры (разумнее всего держать там только размер вектора) и указатель на первый элемент.
Такая реализация позволит за константное время получить доступ к произвольному элементу вектора по его индексу, а также позволит выполнять копирование, конкатенацию и другие простые операции на низком уровне.
И действительно, получить доступ к определенному элементу очень просто — прибавляем к указателю на первый элемент индекс (с некоторыми поправками на размер типа данных) и получаем указатель на нужный элемент! Осталось разыменовать и у нас в переменной нужная кошечка!
Ладно, вектор — классная структура, но и у него есть недостатки (а у кого их нет?!), например нельзя просто так взять и добавить в вектор новый элемент! Особенно втиснуть его в середину. Нельзя также сказать, что кошки с номерами 0, 1 и 4 у нас есть, а с номерами 2 и 3 — нет (раньше они были, но оказалось, что это собаки).
Можно представить себе вектор, как книжную полку с отделениями, в каждом из которых помещается ровно одна книга. Чтобы засунуть новый роман Донцовой между 10-ым и 11-ым томом Большой Совецкой Энциклопедии нужно сильно постараться и переложить все тома с 11-го по 65-ый тома (можно схитрить и поставить 11-ый том в конец, но я вам этого не говорил, да и мы в таком случае потеряем упорядоченность).
В моей памяти все именно так
Применение
В нашем случае вектор бы идеально подошел для топ-10 самых милых котят, т.к. добавлять и удалять элементы не нужно (только изменять), пропусков между 1-ым и 5-ым местом быть не должно, да и удобно обращаться по номеру.
Ладно. В любом случае вектор классный, мы просто посмотрим какие есть еще коллекции.
2 Список (List)
Первый том
Ух! Список задач на сегодня, список покупок в магазине. Список гостей на свадьбу… Так. Ближе к делу.
Мы уже знаем, что элементы вектора лежат акуратненько друг за другом, красиво и ровно. Это дает нам как преимущества так и недостатки.
Список в этом плане полностью противоположная вещь — его элементы могут быть разбросаны по памяти как угодно! Из-за этого мы теряем возможность быстро получить элемент по индексу, а также не можем быстро скопировать весь список, но получаем довольно приятную штуку — мы можем вставлять элементы за константное время в любое место! По слухам удаляются элементы из списка тоже за O(1).
Реализация
Хм. А как с формальным определением?
Список — упорядоченный набор элементов, для каждого из которых хранится указатель на следующий (или для двусвязного списка и на следующий и на предыдущий) элементы списка.
Для последнего элемента списка мы храним нулевой указатель (на диаграммах я буду использовать указатель на нулевую кошку (Null Cat), не пугайтесь).
Внимание! В каноничной реализации списка, для того, чтобы получить размер списка, необходимо обойти весь список — дойдя до нулевого указателя (линейное время — сложность O(n)) и хотя в некоторых реализациях размер кешируется в дескрипторе списка (или в первом элементе), не стоит на это полагаться.
Если бы я мог, я бы один элемент списка разместил на северном полюсе, а другой где-нибудь в окресностях Бетельгейзе
Применение
Список бы подошел для (внимание!) списка бездомных котят, отсортированных по возрасту (по возрастанию). Нам как-раз нужно часто добавлять и удалять элементы из списка (вы не подумайте ничего такого — котят забирают), да и чаще понадобятся первые элементы списка — я бы взял себе маленького пушистого котенка, а не 8-ми-летнего манула.
Ладно. Списки это вроде простая структура. Что есть еще?
3 Множество (Set)
Это Сет
Похожее понятие есть в математике, а точнее в теории множеств. Множество отличается и от вектора и от списка, хотя их реализация может быть похожа.
Множество — неупорядоченный набор элементов, без повторов. Ух. И все? Ни тебе произвольного доступа, ничего! Зачем такое нужно?
Как мы знаем в векторе можно быстро получить элемент по индексу, в списке можно быстро добавить или удалить элемент, а что с множеством?
В множестве можно быстро проверить, есть какой-либо элемент внутри, или его нет. Скажем если бы я хотел узнать, находится ли конкретная кошка в моем списке любимых, то и для списка и для вектора мне пришлось бы перебрать (в худжем случае) все элементы!
Реализация
В множестве, т.к. оно неупорядочено можно сортировать элементы при добавлении и в случае чего устроить бинарный поиск. Хм. Вот ведь парадокс, коллекция неупорядоченная, а внутри все будет по-порядку. Тут важно понять, что если вы добавите новый элемент в множество, не факт, что он пойдет в конец.
На самом деле, работая с множеством вообще нельзя полагаться на какой-либо порядок элементов, он может быть любым — именно поэтому множество и неупорядоченная коллекция.
Стоит отметить, что множество может быть реализовано множеством различных способов, например можно использовать хеширование, для еще более быстрого поиска элементов, поэтому подробно реализацию я рассматривать не буду. Скажу лишь, что можно схитрить и использовать наши знания по спискам.
Вообще есть еще упорядоченные множества, множества с повторами (мультимножество), и вероятно должно быть упорядоченное мультимножество.
Теория множеств дается проще, если брать множество котят
Применение
Множество идеально подойдет для списка любимых котят, потому что их множество. Ха! Шучу.
Но оно действительно подойдет, потому-что такую коллекцию не нужно сортировать (упорядоченность не важна) и мы легко сможем проверить, находится ли какой-нибудь конкретный кот в этом множестве (скажем у меня 100 котят и любимых я кормлю креветками).
Ну ладно. Множества тоже хороши, но неужели есть что-то еще?
4 Словарь (Associative Array, Map, Dictionary)
Признайтесь, это лучше, чем просто словарь
Словарь (он же ассоциативный массив) — это тот-же вектор, но с небольшими отличиями. В качестве индекса (который в словаре будет называться ключ) могут выступать не только числа, но и любые другие типы данных (даже другие коллекции!). Также допустимы пропуски, если мы все-таки будем использовать в качестве ключа целое число, например у нас может быть элемент связанный с ключем 5, но при этом отсутствовать элемент связанный с ключем 4.
Что все это значит на практике? Всего-лишь, то, что в квадратных скобках для ображения к элементу по “индексу” мы можем указывать произвольный тип, например allMyCats[“Murka”].
Реализация
Невооруженным видно, что можно просто завести массив (или список) пар (Ключ, Значение) и добавить специальную функцию, которая будет пробегать по этому списку и возвращать определенное значение по связанному с ним ключу.
Мы также не можем сказать какая пара первая, какая последняя и что раньше “Murka” или “Borka”, поэтому словарь считается неупорядоченной структурой.
Опять-же с каждым ключем может быть связано лишь одно значение, поэтому для приведенного примера с именами кошек словарь в чистом виде подходит слабо.
Реализация, как и в случае со множеством, может быть совершенно различной, можно упорядочить пары по ключу и использовать для получения элемента бинарный поиск (в таком случае элементы должны быть упорядочеваемыми). Опять-же можно реализовать словарь с помощью хеширования ключа, что довольно часто используется со строками.
Применение
Самый правдоподобный и грамотный способ — использовать словарь вместе со списком, где ключем словаря будет строка — имя кошки, а значением — список кошек с таким именем. Это позволит быстро найти всех кошек по имени Мурка и выбрать из них ту, которая в данный момент нужна.
Примерно так выглядит в памяти std::map<std::color, std::list<std::cat>>
И у меня для вас новость — типы коллекций закончились. Ну все. Вообще больше нет. Совсем.
5 Стек (Stack)
Еще один кот и будет Stack Overflow
Ха! Я вас обманул (всмысле пошутил)! Есть еще пара структур данных, которые представляют коллекции.
Итак стек — коллекция с необычным доступом, точнее с необычными правилами относительно того, как могут быть добавлены и удалены элементы.
Все просто — добавляемый элемент, называемый “последним”, первый выбывает из из стека.
Стек очень нужен и полезен в программировании. Например с помощью стека осуществляется вложенный вызов процедур — в стек сохраняются адрес возврата и аргументы вызванной функции.
Реализация
В высокоуровневой реализации ничего особенно интересного нет — указатель на список и элементы добавляются в начало этого списка, и удаляются с него-же.
В низкоуровневой реализации (точнее то, как он реализован в современных архитектурах) есть интересные моменты.
Стек там является небольшим зарезервированным участком памяти и совместно с ним хранится два указателя — на начало стека (где лежит первый доавленный элемент) и конец стека — где лежит последний добавленный.
Если в стек поместить слишком много данных программа завершится со всем знакомой ошибкой — Stack Overflow, это значит, что указатель на конец стека превысил верхний допустимый предел.
Также может случиться обратная ситуация (Stack Underflow), если попытаться забрать из стека больше чем в нем есть, но в высокоуровневых языках она не встречается (понятно почему — нам не дают напрямую работать со стеком).
Если кому интересно как это все работает — изучение ассемблера для какой-нибудь популярной архитектуры, вроде i386, может вам помочь.
Применение
Можно было-бы описать в этом месте стек из бедных котят высотой с гору, но на самом деле в высокоуровневых языках стек редко необходим, часто хватает рекурсии, которая использует стек неявно. Я не стал прикладывать надуманный пример (и не смог придумать нормальный, простите), поэтому переходим к следующему пункту.
Разное
На самом деле есть еще куча коллекций, таких как очередь, двусторонняя очередь (дек), двусвязанный список, кольцевое множество, очереди с приоритетом.
Есть деревья (да их целый лес!) и графы.
Есть вероятностные структуры данных, такие как вероятностное множество и список с пропусками.
Я очень хочу про все это написать, но времени и места на хабре не всегда мало.
Однако есть множество (или вектор) вещей, относящихся к теме, которые я хотел бы упомянуть хоть вскользь, да просит меня любопытный читатель и пойдет читать умную книгу.
Строки
В первую очередь то, как реализованы строки в некоторых языках может показаться странным. Самое простое и эффективное решение это наверное решение C — строка это набор символов, с нулевым символом в конце, что позволяет обходиться без дескриптора.
В C++ std::string уже больше походит на вектор.
Ну а в старом паскале дескриптор (точнее всего-лишь длина) хранится в нулевом элементе массива.
В Haskell String — это список символов ([Char]), из чего вытекает, что получение длины строки имеет сложность O(n). Зато их очень удобно оббегать рекурсивно.
В общем случае, строка — это упорядоченный набор символов и не более. Какой именно тип коллекции будет использован — не важно (ну я бы не советовал использовать множество, ха!).
Очередь (Queue)
Очередь очень похожа на стек и в тоже время является его противоположностью — первым мы получим обратно не тот элемент, что мы добавили последним, а тот, что “стоит в очереди” дольше всех. Очередь очень удобная структура, но несмотря, на то, что принцип ее работы схож со стеком, в эффективной реализации есть небольшое отличие.
Для стека мы могли схитрить и выделить приемлемый по размеру участок памяти, в случае чего его расширяя, потому-что стек то уменьшается, то увеличивается, т.к. элементы и добавляются и удаляются “с одного конца”. Если же мы представим работу очереди, то она будет “ползти в памяти” — начало будет постоянно сдвигаться вверх, поэтому трюк, который применим для стека, будет работать хуже и тут уже намного лучше будет использовать двусвязный список (и не забудьте хранить указатели на первый и последний элементы).
Еще можете попробовать реализвать очередь на двух стеках, но это тоже менее эффективно.
Также есть дек (двусторонняя очередь — deque). В ней можно добавлять элементы как в конец, так и в начало. И забирать их тоже и с конца и с начала.
Заключение
Ух. Я начинаю повторяться
Я совсем не упомянул, про комбинирование различных коллекций, благодаря которым образуются матрицы, таблицы. Также я не затронул деревья, кольцевое множество, почти ничего не написал про очереди, очень мало информации по хешированию (я таки отделался парой слов от этой темы) и другим методам оптимизации.
Однако я думаю статья исполнит свою роль — просто и понятно изложит основы структур данных для читателей разной степени подготовленности. И я буду рад продолжить и осветить множество (или очередь, ха!) других тем в таком-же ключе.
Спасибо тем, кто смог дочитать аж до этих строк (как они это выдержали?).
Урок №95. std::vector (векторы)
На предыдущем уроке мы рассматривали std::array, который является более безопасной и удобной формой обычных фиксированных массивов в языке C++. Аналогично, в Стандартной библиотеке C++ есть и улучшенная версия динамических массивов (более безопасная и удобная) — std::vector.
В отличие от std::array, который недалеко отходит от базового функционала обычных фиксированных массивов, std::vector идет в комплекте с дополнительными возможностями, которые делают его одним из самых полезных и универсальных инструментов в языке C++.
Векторы
Представленный в C++03, std::vector (или просто «вектор») — это тот же динамический массив, но который может сам управлять выделенной себе памятью. Это означает, что вы можете создавать массивы, длина которых задается во время выполнения, без использования операторов new и delete (явного указания выделения и освобождения памяти). std::vector находится в заголовочном файле vector. Объявление std::vector следующее:
Обратите внимание, что в неинициализированном, что в инициализированном случаях вам не нужно явно указывать длину массивов. Это связано с тем, что std::vector динамически выделяет память для своего содержимого по запросу.
Подобно std::array, доступ к элементам массива может выполняться как через оператор [] (который не выполняет проверку диапазона), так и через функцию at() (которая выполняет проверку диапазона):
В любом случае, если вы будете запрашивать элемент, который находится вне диапазона array , длина вектора автоматически изменяться не будет. Начиная с C++11, вы также можете присваивать значения для std::vector, используя список инициализаторов:
В таком случае вектор будет самостоятельно изменять свою длину, чтобы соответствовать количеству предоставленных элементов.
Нет утечкам памяти!
Когда переменная-вектор выходит из области видимости, то она автоматически освобождает память, которую контролировала (занимала). Это не только удобно (так как вам не нужно это делать вручную), но также помогает предотвратить утечки памяти. Рассмотрим следующий фрагмент:
Если переменной value присвоить значение true , то array никогда не будет удален, память никогда не будет освобождена и произойдет утечка памяти.
Однако, если бы array был вектором, то подобное никогда бы и не произошло, так как память освобождалась бы автоматически при выходе array из области видимости (независимо от того, выйдет ли функция раньше из области видимости или нет). Именно из-за этого использование std::vector является более безопасным, чем динамическое выделение памяти через оператор new.
Длина векторов
В отличие от стандартных динамических массивов, которые не знают свою длину, std::vector свою длину запоминает. Чтобы её узнать, нужно использовать функцию size():
The length is: 7
Изменить длину стандартного динамически выделенного массива довольно проблематично и сложно. Изменить длину std::vector так же просто, как вызвать функцию resize():
The length is: 7
0 1 2 0 0 0 0
Здесь есть две вещи, на которые следует обратить внимание. Во-первых, когда мы изменили длину array , существующие значения элементов сохранились! Во-вторых, новые элементы были инициализированы значением по умолчанию в соответствие с определенным типом данных (значением 0 для типа int).
Длину вектора также можно изменить и в обратную сторону (обрезать):
The length is: 4
0 1 4 7
Изменение длины вектора является затратной операцией, поэтому вы должны стремиться минимизировать количество подобных выполняемых операций.
Заключение
Это вводная статья, предназначенная для ознакомления с основами std::vector. На следующих уроках мы детально рассмотрим std::vector, в том числе и разницу между длиной и ёмкостью вектора, и то, как в std::vector выполняется выделение памяти.
Поскольку переменные типа std::vector могут сами управлять выделенной себе памятью (что помогает предотвратить утечку памяти), отслеживают свою длину и легко её изменяют, то рекомендуется использовать std::vector вместо стандартных динамических массивов.
Урок №94. Введение в std::array
Комментариев: 21
Есть ли разница в позиции ключевого слова const в объявлении цикла foreach или оба варианта эквивалентны и обозначают константную ссылку на текущий элемент массива?
Когда мы пытаемся работать с элементом массива вне диапазона то происходит ошибка времени выполнения, правильно? Ибо с этой ошибкой проект собирается(VS2019).
Поскольку ошибка возникает во время работы кода, а не на этапе компиляции, то это ошибка времени выполнение. При желании можно проверить это, запустив этот код:
В данном случае код компилируется и начинает работу, и после объявления вектора выполнение кода ставиться на паузу
Я не очень поняла один момент, может, кто-то сможет подсказать, буду признательна)
В начале урока написано: "Начиная с C++11, вы также можете присваивать значения для std::vector, используя список инициализаторов … В таком случае вектор будет самостоятельно изменять свою длину, чтобы соответствовать количеству предоставленных элементов."
А в конце показывают функцию resize( ), которая делает то же самое, но при этом является затратной.
Так вооот, насколько затратным будет изменить длину вектора через список инициализаторов и зачем тогда нужна отдельная функция? Только для работы с крупными объемами данных, чтобы не переписывать их все вручную? Или есть ещё что-то?
Мне кажется что изменять длину std::vector что через метод resize(), что через список инициализаторов будет одинаково затратным (возможно в будущих уроках это будет более подробно описано).
Отличие же resize() от списка инициализаторов в том что при вызове метода resize() он изменяет длину std::vector и при этом те элементы которые входят в диапазон размера будет сохранены без изменений.
Изменения размера с помощью списка инициализаторов изменит не только длину std::vector но и запишит вместо старых элементов новые (те которые были записаны в списке инициализаторов).
Юрий, вы восхитительны! У вас не только классные уроки, но и абсолютно замечательная система кросс-навигации между ними — на сайт изначально попала в поисках информации про классы. Пойду читать ваши уроки с самого начала, у меня хоть какая-то минимальная база знаний и есть, но всё равно так много новых и полезных штук открываю ��
alt=»Avatar photo» width=»50″ height=»50″ />Юрий :
Доброго времени суток!
В этой статье нет ни слова про дву-х, трё-х, *N — мерные векторы и массивы пространства имён std. Подозреваю что можно реализовать аналогично указателю на указатель (древовидная структура) массив в массиве, но надеюсь есть способ проще и удобней. Конечно сам доберусь до этого, но надеюсь получить ответ и возможно мой вопрос поможет улучшить/дополнить 95-й урок.
Это было вводное занятие, поверхностное обозрение темы, написано же в конце. Дальше, естественно, будет подробнее
10.23 – Знакомство с std::vector
В предыдущем уроке мы представили std::array , который обеспечивает функциональность встроенных фиксированных массивов C++ в более безопасной и удобной форме.
Аналогичным образом стандартная библиотека C++ предоставляет функциональные возможности, которые делают более безопасной и простой работу с динамическими массивами. Это средство называется std::vector .
В отличие от std::array , который точно соответствует базовой функциональности фиксированных массивов, std::vector содержит некоторые дополнительные возможности. Это помогает сделать std::vector одним из самых полезных и универсальных инструментов в вашем наборе инструментов C++.
Знакомство с std::vector
Представленный в C++03, std::vector предоставляет функциональность динамического массива, которая обеспечивает собственное управление памятью. Это означает, что вы можете создавать массивы, длина которых устанавливается во время выполнения, без необходимости явно выделять и освобождать память с помощью операторов new и delete . std::vector находится в заголовке <vector> .
Объявить std::vector просто:
Обратите внимание, что как в неинициализированном, так и в инициализированном случае вам не нужно указывать длину массива во время компиляции. Это связано с тем, что std::vector будет динамически выделять память для своего содержимого, сколько потребуется.
Как и в std::array , доступ к элементам массива может осуществляться с помощью оператора [] (который не проверяет границы) или функции at() (которая выполняет проверку границ):
В любом случае, если вы запрашиваете элемент, который находится за пределами массива, вектор не будет автоматически изменять свой размер.
Начиная с C++11, вы также можете присваивать значения std::vector , используя список инициализаторов:
В этом случае вектор автоматически изменит размер, чтобы соответствовать количеству предоставленных элементов.
Самоочистка предотвращает утечку памяти
Когда переменная вектор выходит за пределы области видимости, она (при необходимости) автоматически освобождает память, которую она контролирует. Это не только удобно (поскольку вам не нужно делать это самостоятельно), но и помогает предотвратить утечки памяти. Рассмотрим следующий фрагмент:
Если для earlyExit установлено значение true , массив никогда не будет освобожден, и произойдет утечка памяти.
Однако если array является std::vector , этого не произойдет, потому что память будет освобождена, как только массив выйдет за пределы области видимости (независимо от того, завершится функция раньше или нет). Это делает std::vector более безопасным в использовании, чем самостоятельное выделение памяти.
Векторы запоминают свою длину
В отличие от встроенных динамических массивов, которые не знают длину массива, на который они указывают, std::vector отслеживает свою длину. Мы можем запросить длину вектора с помощью функции size() :
Приведенный выше пример печатает:
Как и в случае с std::array , size() возвращает значение вложенного типа size_type (полный тип в приведенном выше примере будет std::vector<int>::size_type ), который является целочисленным значением без знака.
Изменение размера вектора
Изменение размера встроенного динамически размещаемого массива сложно. Изменить размер std::vector так же просто, как вызвать функцию resize() :
Этот код печатает:
Здесь следует отметить два момента. Во-первых, когда мы изменили размер вектора, значения существующих элементов были сохранены! Во-вторых, новые элементы инициализируются значением по умолчанию для типа (которое для int равно 0).
Размер векторов может быть уменьшен:
Этот код печатает:
Изменение размера вектора требует больших вычислительных ресурсов, поэтому вы должны стремиться минимизировать количество таких операций. Если вам нужен вектор с определенным количеством элементов, но вы не знаете значений элементов в момент объявления, вы можете создать вектор со значениями элементов по умолчанию:
Эта программа печатает:
Мы поговорим о том, почему прямая инициализация и инициализация с фигурными скобками обрабатываются по-разному в уроке «16.7 – Список инициализаторов std::initializer_list ». Практическое правило: если тип представляет собой какой-то список, и вы не хотите инициализировать его списком, используйте прямую инициализацию.
Уплотнение логических значений
У std::vector есть еще один крутой трюк. Существует специальная реализация для std::vector типа bool , которая сжимает 8 логических значений в один байт! Это происходит за кулисами и не меняет способ использования std::vector .
Этот код печатает:
Еще не всё
Обратите внимание, что это вводная статья, предназначенная для ознакомления с основами std::vector . В уроке «11.11 – Емкость и стековое поведение std::vector » мы рассмотрим некоторые дополнительные возможности std::vector , включая разницу между длиной и емкостью вектора, и более подробно рассмотрим, как std::vector обрабатывает выделение памяти.
Заключение
Поскольку переменные типа std::vector обеспечивают собственное управление памятью (что помогает предотвратить утечки памяти), запоминают свою длину и могут легко изменять размер, мы рекомендуем использовать std::vector в большинстве случаев, когда необходимы динамические массивы.