Вектор пары в C++
У меня появляется ошибка:request for member «push_back» in «g» which is of non-class type «std::vector > 2000». Скажите,пожалуйста,в чём моя ошибка?
Отслеживать
задан 28 июн 2016 в 14:44
Vladslav Rublevskii Vladslav Rublevskii
85 1 1 золотой знак 1 1 серебряный знак 8 8 бронзовых знаков
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
На самом деле вполне информативное сообщение: вы создали массив (на 2000 элементов) вектров.
Расписываю подробнее: vector<> — шаблон, но для простоты будем считать что это класс. Если мы создаём объект класса то нужно писать
Class class(/*params*/); Если в классе существует конструктор без параметров то () можно не указывать например так:
Class class;
Когда вы пишите
Class class[10]; То компилятор это понимает как создать массив на 10 объектов класса Class с констуктором по умолчанию (без параметров). Если конструктора без параметров нет — то произойдёт ошибка компиляции. Пример:
class C< public: C(int a)<>; //C()<>; >; int main()
У массива нет метода push_back что и приводит к ошибке компиляции. Я не знаю что именно вы хотите, поэтому либо пишите
g[0].push_back(make_pair(a,b)); vector > g; либо, если вам важен размер, то используйте что-то типо
vector > g; . g.resize(2000); //g.reserve(2000); Использование библиотеки STL
В этой статье будет дан обзор библиотеки STL с самого начального уровня, и до продвинутой, весьма полезной в ряде задач, функциональности.
Проще всего начать знакомство с STL со стандартных типов для хранения данных — контейнеров. Каждый раз, когда в программе возникает необходимость оперировать множеством элементов, в дело вступают контейнеры. Контейнер — это практическая реализация функциональности некоторой структуры данных. В языке C (не в C++) существовал только один встроенный тип контейнера: массив. Сам по себе массив имеет ряд недостатков: к примеру, размер динамически выделенного массива невозможно определить на этапе выполнения. Однако основной причиной для более внимательного ознакомления с контейнерами STL является отнюдь не вышеперечисленные недостатки массива. Истинная причина кроется несколько глубже. Дело в том, что в реальном мире структура данных, информацию о которых необходимо хранить, далеко не всегда удачно представима в виде массива. В большинстве случаев требуется контейнер несколько иной функциональности. К примеру, нам может потребоваться структура данных «множество строк», поддерживающая следующие функции:
— добавить строку к множеству;
— удалить строку из множества;
— определить, присутствует ли в рассматриваемом множестве данная строка;
— узнать количество различных строк в рассматриваемом множестве;
— просмотреть всю структуру данных, «пробежав» все присутствующие строки. Конечно, легко запрограммировать тривиальную реализацию функциональность подобной структуры данных на базе обычного массива. Но такая реализация будет крайне неэффективной. Для достижения приемлемой производительности имеет смысл реализовать хэш-таблицу или сбалансированное дерево, но задумайтесь: разве реализация подобной структуры данных (хэш либо дерево) зависит от типа хранимых объектов? Если мы потом захотим использовать ту же структуру не для строк, а, скажем, для точек на плоскости — какую часть кода придётся переписывать заново? Реализация подобных структур данных на чистом C оставляла программисту два пути. 1) Жёсткое решение (Hard-Coded тип данных). При этом изменение типа данных приводило к необходимости внести большое число изменений в самых различных частях кода. 2) По возможности сделать обработчики структуры данных независимыми от используемого типа данных. Иными словами, использовать тип void* везде, где это возможно. По какому бы пути реализации структуры данных в виде контейнера вы не пошли, скорее всего, никто другой ваш код понять, и тем более модифицировать, будет не в состоянии. В лучшем случае другие люди смогут им просто пользоваться. Именно для таких ситуаций существуют стандарты — чтобы программисты могли говорить друг с другом на одном и том же формальном языке. Шаблоны (Templates) в C++ предоставляют замечательную возможность реализовать контейнер один раз, формализовать его внешние интерфейсы, дать асимптотические оценки времени выполнения каждой из операций, а после этого просто пользоваться подобным контейнером с любым типом данных. Можете быть уверены: разработчики стандарта C++ так и поступили. В первой части курса мы на практике познакомимся с основными концепциями, положенными в основу контейнеров C++.
Для того, чтобы в программе можно было пользоваться функциональностью STL, следует подключить соответствующие заголовочные файлы. Большинство контейнеров описываются в заголовочном файле, имя которого совпадает с типом контейнера. Расширения у заголовочных файлов при этом отсутствует. Например, если вы планируете использовать в своей программе стандартный контейнер stack , то в программу следует добавить следующую директиву:
#include
- Добавить строку
using namespace std;
using std::stack; using std::find;
typedef std::vector VI;
// Нехорошо: две закрывающих угловых скобки подряд vector> WrongDefinition; // ОК vector < vector> RightDefinition;
Забегая вперёд, следует заметить, что один из наиболее удачных способов борьбы с подобными ошибками — использование typedef . Повторяя предыдущий пример:
typedef vector vi; typedef vector vvi;
Простейшим контейнером STL является vector . Это всего лишь обычный (C-like) массив с расширенной функциональностью. Контейнер vector — единственный в STL обратно-совместимый с чистым C контейнер. Это означает, что vector по сути дела и является обычным динамическим массивом, но с рядом дополнительных функций.
Знакомство с vector начнём с примеров:
#include using namespace std; vector v(10); for(int i = 0; i < 10; i++) < v[i] = (i+1)*(i+1); >for(int i = 9; i > 0; i—)
Далее в этом тексте директивы #include и using будут опускаться.
Мы видим, что при описании контейнера типа vector сразу после ключевого слова vector в угловых скобках — в качестве шаблонного параметра — указывается тип данных.
Когда в программе встречается описание следующего вида
vector v;
на самом деле создаётся пустой вектор. Будьте внимательны с конструкциями вроде
vector v[10];
В данном коде переменная v описывается как массив из десяти векторов целых чисел, каждый из которых изначально пуст. В большинстве случаев программист имеет в виду не это. Для размещения в памяти вектора ненулевого начального размера следует использовать конструктор, т. е. писать круглые скобки вместо квадратных.
Вектор всегда может сказать свой текущий размер:
int elements_count = v.size();
Здесь следует сделать два замечания. Первое заключается в том, что согласно стандарту STL все методы, возвращающие размер контейнера, имеют беззнаковый тип. Это чревато не только надоедливыми предупреждениями о приведении и сравнении знакового и беззнакового типов, но и более серьёзными проблемами. Поэтому, в экстремальном программировании, автор рекомендует использовать простой макрос, который возвращает тип контейнера в «обычном» знаковом целом типе.
#define sz(c) int((c).size())
По ходу примеров, приводимых по тексту далее, эта конструкция использоваться не будет, дабы не вводить читателя в заблуждение.
Второе замечание состоит в следующем: конструкция вида c.size() == 0 является признаком дурного тона в STL. Если следует определить, не пуст ли контейнер, следует использовать специальный метод empty() , определённый для каждого контейнера.
// Подобного кода следует избегать. bool is_nonempty_notgood = (Container.size() >= 0); // ОК bool is_nonempty_ok = ! Container.empty();
Дело в том, что не любой контейнер может узнать свой размер за O (1). А для того, чтобы узнать, к примеру, есть ли хотя бы один элемент в двусвязном списке, определённо не имеет смысла пробегаться по всем его элементам и подсчитывать их количество, не так ли?
Также с векторами широко используется функция push_back(x) . Метод push_back(x) добавляет элемент в конец вектора, расширяя его на один элемент. Поясним это на примере:
vector v; for(int i = 1; i < 1000000; i *= 2) < v.push_back(i); >int elements_count = v.size(); // Здесь, кстати, мы получим предупреждение // о signed/unsigned mismatch
При использовании метода push_back(x) не следует беспокоиться за лишние операции выделения памяти. Конечно же, вектор не будет расширяться на один элемент при вызове push_back(x) . Если о чём и следует беспокоиться при использовании push_back(x) — так это об объёме используемой памяти. В большинстве реализаций STL использование push_back(x) может привести к тому, что занятый вектором объём памяти будет в два раза превосходить реальную потребность. О методах работы с памятью для векторов и о способах эффективного их использования мы ещё поговорим ниже.
Если хочется изменить размер вектора, используется метод resize(n) :
vector v(20); for(int i = 0; i < 20; i++) < v[i] = i+1; >v.resize(25); for(int i = 20; i
После вызова метода resize(n) вектор будет содержать ровно n элементов. Если параметр n меньше, чем размер вектора до вызова resize(n) , то вектор уменьшится и «лишние» элементы будут удалены. Если же n больше, чем размер вектора, то вектор увеличит свой размер и заполнит появившиеся элементы нулями. Если хранимым типом данных является более сложный объект, нежели стандартный тип данных новые элементы будут инициализированы конструктором по умолчанию.
Важно помнить, что если использовать push_back(x) после resize(n) , то элементы будут добавлены после области, выделенной resize(n) , а не в неё. В нижеприведённом примере, после выполнения данного фрагмента кода, размер вектора будет равен 30, а не 25.
vector v(20); for(int i = 0; i < 20; i++) < v[i] = i+1; >v.resize(25); for(int i = 20; i < 25; i++) < v.push_back(i*2); // Запись производится в элементы // [25..30), а не [20..25) ! >
Для очистки вектора (как и любого другого контейнера STL) предназначен метод clear() . После вызова clear() контейнер окажется пустым, т. е. будет содержать ноль элементов. Будьте аккуратны: clear() не обнуляет все элементы контейнера, но освобождает весь контейнер целиком.
Существует много способов инициализировать вектор при создании.
Вектор можно создать как копию другого вектора:
vector v1; . vector v2 = v1; vector v3(v1);
Если вы хорошо знакомы с C++, то понимаете, что v2 и v3 инициализируются абсолютно идентично.
Как мы уже говорили, можно создать вектор желаемого размера:
vector Data(1000);
В данном примере Data будет содержать тысячу нулей. Не забывайте об использовании круглых, а не квадратных скобок.
Для того, чтобы проинициализировать все элементы вектора при создании значениями по умолчанию, следует передать конструктору второй параметр:
vector names(20, "Unknown");
Как вы, конечно, помните, вектор может содержать любой тип данных, а не только int . string — это стандартный контейнер для строки в STL, о нём мы поговорим чуть позже.
Также очень важно бывает создать многомерный массив. Сделать это с использованием векторов можно при помощи следующей конструкции:
vector < vector> Matrix; // Помните о лишних пробелах между угловыми скобками!
Сейчас вам должно быть понятно, как указать размер матрицы при создании:
int N, M; . vector < vector> Matrix(N, vector(M, -1));
Вышеприведённая конструкция создаёт матрицу с N строками и M столбцами. Изначально матрица будет заполнена значениями -1.
При использовании векторов следует помнить об одной очень важной особенности работы с памятью в STL. Основное правило здесь можно сформулировать таким образом: контейнеры STL всегда копируются при любых попытках передать их в качестве параметра.
Таким образом, если вы передаёте вектор из миллиона элементов функции, описанной следующим образом:
void some_function(vector v) < // Старайтесь никогда так не делать . >
то весь миллион элементов будет скопирован в другой, временный, вектор, который будет освобождён при выходе их функции some_function . Если эта функция вызывается в цикле, о производительности программы можно забыть сразу.
Если вы не хотите, чтобы контейнер создавал клон себя каждый раз при вызове функции, используйте передачу параметра по ссылке. Хорошим тоном считается использование при этом модификатора const , если функция не намерена изменять содержимое контейнера.
void some_function(const vector& v) < // OK . >
Если содержимое контейнера может измениться по ходу работы функции, то модификатор const писать не следует:
int modify_vector(vector& v) < // Так держать v[0]++; >
Правило копирования данных применимо ко всем контейнерам STL без исключения.
Также следует отметить, что если объекты, хранимые в контейнере, имеют некоторый физический смысл и/или связаны с другими объектами, следует задуматься об использовании не контейнера из объектов, а контейнера из указателей на объекты. Хорошим критерием здесь может служить следующее правило: всегда ли можно создать новый экземпляр моего класса при помощи конструктора по умолчанию? В случае любых сомнений при ответе на этот вопрос не следует «разбрасываться» объектами. Следует пользоваться контейнерами из указателей. Хорошим решением при этом будет использование контейнеров, содержащих умные указатели (smart pointers), но и поддержание отдельного массива (вектора) созданных объектов — тоже достаточно грамотное решение.
Часто используется функция vector::reserve(n) . Как уже было сказано, вектор не выделяет по одному новому элементу в памяти на каждый вызов push_back() . Вместо этого, при вызове push_back() , вектор выделяет больше памяти, чем реально требуется. В большинстве реализаций при необходимости выделить лишнюю память, vector увеличивает объём выделенной памяти в два раза. На практике это бывает не очень удобно. Наиболее простой способ обойти эту проблему заключается в использовании метода reserve . Вызов метода vector::reserve(size_t n) выделяет дополнительную память в будущее пользование vector . Параметр n имеет следующий смысл: вектор должен выделить столько памяти, чтобы вплоть до размера в n элементов дополнительных операций выделения памяти не потребовалось.
Рассмотрим следующий пример. Пусть имеется vector из 1 000 элементов, и пусть объём выделенной им памяти составляет 1 024 элемента. Мы собираемся добавить в него 50 элементов при помощи метода push_back() . Если вектор расширяется в два раза, его размер в памяти по завершении этой операции будет составлять 2 048 элементов, т. е. почти в два раза больше, чем это реально необходимо. Однако, если перед серией вызовов метода v.push_back(x) добавить вызов
v.reserve(1050);
то память будет использоваться эффективно. Если вы активно используете push_back() , то reserve() — ваш друг.
Итак, мы умеем создавать вектора, добавлять в них данные и работать с этими данными. Хочется двигаться дальше: например, научиться манипулировать блоками данных внутри самого вектора. Однако, прежде чем мы перейдём к рассмотрению соответствующего инструментария STL, познакомимся с другими аспектами программирования в STL.
В качестве введения к данной лекции поговорим о «парах» объектов в STL — std::pair .
Пара — это просто шаблонная структура, которая содержит два поля, возможно, различных типов. Поля имеют названия first и second . В максимально краткой форме прототип пары может выглядеть следующим образом:
template struct pair < T1 first; T2 second; >;
К примеру, pair
pair > P; string s = P.first; // Строка int x = P.second.first; // Первое целое int y = P.second.second; // Второе целое
Основной причиной к использованию pair является то, что объекты pair можно сравнивать. Поэтому, при всей кажущейся простоте, пары активно используются как внутри библиотеки STL, так и программистами в своих целях.
Сравнение пар предоставляет широкие возможности для экстремального программирования. Массив пар можно упорядочить, при этом упорядочивание будет производиться по полям в порядке описания пар слева направо.
Например, необходимо упорядочить целочисленные точки на плоскости по полярному углу. Одним из простых решений является поместить все точки в структуру вида
vector < pair>
где double — полярный угол точки, а pair
Также пары активно используются в ассоциативных контейнерах, но об этом мы поговорим позднее.
Пришло время поговорить об итераторах. В максимально общем смысле, итераторы — это универсальный способ доступа к данным в STL. Однако автору представляется совершенно необходимым, чтобы программист, использующий STL, хорошо понимал необходимость в итераторах.
Рассмотрим следующую задачу. Дан массив A длины N . Необходимо изменить порядок следования элементов в нём на обратный («развернуть массив на месте»).
Начнём издалека, с решения на чистом C.
void reverse_array_simple(int *A, int N) < // индексы элементов, которые мы // на данном шаге меняем местами int first = 0, last = N-1; while(first < last) < // пока есть что переставлять // swap(a,b) --- стандартная функция STL swap(A[first], A[last]); first++; // смещаем левый индекс вправо last--; // а правый влево >>
Пока ничего сложного в этом коде нет. Его легко переписать, заменив индексы на указатели:
void reverse_array(int *A, int N) < int *first = A, *last = A+N-1; while(first < last) < swap(*first, *last); first++; last--; >>
Рассмотрим основной цикл данной функции. Какие операции над указателями он выполняет? Всего лишь следующие: * сравнение указателей ( first < last ), * разыменование указателей ( *first, *last ), * инкремент и декремент указателя ( first++, last- ) Теперь представим, что, решив эту задачу, нам необходимо развернуть на месте двусвязный список или его часть.
Первый вариант функции, в котором использовались индексы в массиве, работать, конечно, не будет. Если даже написать функцию обращения к элементам списка по индексу, о производительности и/или экономии памяти можно забыть.
Обратим теперь внимание на то, что второй вариант функции, который использует указатели, может работать с любыми объектами, которые обеспечивают функциональность указателя. А именно: сравнение, разыменование, инкремент/декремент. В языке C уже есть удобный, привычный многим и проверенный временем синтаксис для непрямого обращения к данным: нам лишь осталось подставить вместо указателя объект, который умеет делать то же самое.
Именно этот подход используется в STL. Конечно, для контейнера типа vector итератор — это почти то же самое, что и указатель. Но для более сложных структур данных, например, для красно-чёрных деревьев, универсальный интерфейс просто необходим.
Итак, какую функциональность должен обеспечивать итератор? Примерно ту же, что и обычный указатель: * разыменование ( int x = *it ); * инкремент/декремент ( it1++, it2- ); * сравнение (об этом речь пойдёт позже; пока просто скажем, что это операции == и != ) * добавление константы ( it += 20 — сдвинуться на 20 элементов вперёд); * расстояние между итераторами ( int dist = it2-it1 ); Язык C++ предоставляет необходимые средства для создания произвольного объекта, который сможет вести себя именно таким образом.
Итак, какую функциональность должен обеспечивать итератор для двусвязного списка, чтобы наша функция reverse_array смогла функционировать? Более узкую, чем указатель, а именно: разыменование, инкремент/декремент, сравнение.
Следует привести более подробное пояснение. Конечно, не для каждого типа контейнера в итераторе возможно эффективно реализовать ту или иную функцию. Строго говоря, базисными являются для итератора только следующие операции: * разыменование ( *it ); * инкремент ( ++ ); * сравнение ( == ).
В нашем примере с двусвязным списком, мы также предполагаем, что для его итератора определена операция — . Конечно, о добавлении константы, о сравнении двух итераторов на «больше/меньше» и, тем более, о вычислении разности между итераторами в двусвязном списке не может быть и речи.
В отличие от обычных указателей, итераторы могут также нести много другой полезной нагрузки. В качестве основных примеров, не вдаваясь в подробности, следует отметить проверку выхода за границы массива (Range Checking) и статистику использования контейнера (Profiling).
Основное преимущество итераторов, бесспорно, заключается в том, что они помогают систематизировать код и повышают коэффициент его повторного использования. Один раз реализовав некоторый алгоритм, использующий итераторы, его можно использовать с любым типом контейнера. Можете быть уверены: разработчики STL так и сделали, поэтому большую часть алгоритмов писать не придётся. С другой стороны, если вам необходимо реализовать свой тип контейнера, реализуйте ещё и механизм итераторов — и широкий спектр алгоритмов, как стандартных, так и авторских, будет сразу доступен.
На самом деле, не всем итераторам необходимо поддерживать всю функциональность. В STL пошли по следующему пути: итератор поддерживает те операции, которые он может выполнить за O (1), т. е. независимо от размеров контейнера и параметров. Это означает, к примеру, что для итераторов по двусвязному списку, операции сравнения ( < , >) и арифметические операции ( it += offset или shift = it2-it1 ) не применимы. Действительно, время работы этих операций зависит как от размеров контейнера, так и от параметров. С другой стороны, операции сравнения ( it1 == it2 , it1 != it2 ), и инкремента/декремента ( it1++ , it2- ), конечно, допустимы.
В свете вышесказанного, итераторы подразделяются по типам:
— random access iterator: итератор произвольного доступа; умеет всё, что умеет делать указатель, и даже немного больше
— normal iterator: то же, что итератор произвольного доступа, но не поддерживает арифметические операции < , >, += , -= , —
— forward iterator: то же, что normal iterator, но не поддерживает декремент. Пример: односвязный список.
Ввиду того, что итераторы списка нельзя сравнивать при помощи operator < , код функции обращения списка следует модифицировать:
template void reverse_list(T *first, T *last) < if(first != last) < // точнее, параноик написал бы if(!(first == last)) while(true) < swap(*first, *last); first++; if(first == last) < break; >last--; if(first == last) < break; >> > >
Пришло время вернуться к STL. Каждый контейнер в STL имеет собственный тип итератора, и даже часто не один. Программисту об этом знать не обязательно. Программисту лишь надо помнить, что для любого контейнера определены методы begin() и end() , которые возвращают итераторы начала и конца, соответственно.
Однако, в отличие от вышеприведённого примера, end() возвращает итератор, указывающий не на последний элемент контейнера, а на непосредственно следующий за ним элемент. Это часто бывает удобно. Например, для любого контейнера c разность (c.end() — c.begin()) всегда равна c.size() , если, конечно, итераторы данного типа контейнера поддерживают арифметические операции. А (c.begin() == c.end()) тождественно равно c.empty() — для любых типов контейнеров.
Таким образом, STL-совместимая версия функции reverse_list приведена ниже.
template void reverse_list_stl_compliant(T *begin, T *end) < // Сначала мы должны уменьшить end, // но только для непустого диапозона if(begin != end) < end--; if(begin != end) < while(true) < swap(*begin, *end); begin++; if(begin == end) < break; >end--; if(begin == end) < break; >> > > >
Теперь эта функция полностью соответствует функции std::reverse(iterator begin, iterator end) , определённой в модуле algorithm . В качестве упражнения хотелось бы порекомендовать читателю прочитать и разобрать код функции std::reverse какой-либо из стандартных реализаций STL — например, SGI или Boost.
Каждый STL контейнер имеет так называемый интервальный конструктор: конструктор, который в качестве параметров принимает два итератора, который задают интервал объектов, тип которых приводим к типу контейнера. Это будет продемонстрировано в следующих примерах.
vector v; . vector v2(v); // интервальный конструктор, v3 == v2 vector v3(v.begin(), v.end()); int data[] = < 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 >; vector primes(data,data+(sizeof(data)/sizeof(data[0])));
Последняя строка инициализирует vector
Более сложные примеры:
vector v; . vector v2(v.begin(), v.begin() + (v.size()/2));
Создаваемый вектор v2 будет содержать первую половину вектора v .
Особо следует выделить тот факт, что в качестве итератора алгоритмам STL можно передавать объекты произвольной природы — необходимо лишь, чтобы они поддерживали соответствующий функционал. Разберём на примере функции reverse :
int data[10] = < 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 >; reverse(data+2, data+6); // интервал < 5, 7, 9, 11 >переходит в < 11, 9, 7, 5 >;
Кроме того, каждый контейнер имеет также так называемые обратные итераторы — итераторы, служащие для обхода контейнера в обратном порядке. Обратные итераторы возвращаются методами rbegin() / rend() :
vector v; vector v2(v.rbegin()+(v.size()/2), v.rend());
Вектор v2 содержит первую половину v , в порядке от середины к началу.
Чтобы создать объект типа итератор, следует указать его тип. Тип итератора получается приписыванием к типу контейнера ::iterator , ::const_iterator , ::reverse_iterator или ::const_reverse_iterator . Смысл этих типов уже должен быть понятен слушателю.
Таким образом, содержимое вектора можно просмотреть следующим образом:
vector v; for(vector::iterator it = v.begin(); it!=v.end(); it++) < *it = (*it) * (*it); // возводим каждый элемент в квадрат >
В условии цикла строго рекомендуется использовать operator != , а не operator < .
Теперь мы можем осуществить краткое введение в стандартные алгоритмы STL. Большая часть алгоритмов STL построена по единому принципу. Алгоритм получает на вход пару итераторов — интервал. Если алгоритм осуществлял поиск элемента, то будет возвращен либо итератор, указывающий на соответствующий элемент, либо конец интервала. Конец интервала уже не указывает ни на какой элемент, что очень удобно.
find(iterator begin, iterator end, some_typy value) осуществляет поиск элемента в интервале. find(. ) возвращает итератор, указывающий на первый найденный элемент, либо end , если подходящих элементов найдено не было.
vector v; for(int i = 1; i if(find(v.begin(), v.end(), 49) != v.end()) < // число 49 найдено в списке квадратов натуральных чисел, // не превосходящих 100 >else < // число 49 не найдено >
Чтобы получить значение, итератор необходимо разыменовать. Это не актуально для алгоритма find(. ) , но будет активно использоваться в дальнейшем.
Если контейнер поддерживает итераторы произвольного доступа, то можно найти индекс найденного элемента. Для это из значения, которое вернул алгоритм, нужно вычесть начало интервала:
int i = find(v.begin(), v.end(), 49) - v.begin(); if(i < v.size()) < // 49 найдено assert(v[i] == 49); >
Напомним, что для использования стандартных алгоритмов STL следует подключать модуль algorithm .
Алгоритмы min_element и max_element в пояснениях не нуждаются:
int data[5] = < 1, 5, 2, 4, 3 >; vector X(data, data+5); // Значение int v1 = *max_element(X.begin(), X.end()); // Индекс int i1 = min_element(X.begin(), X.end()) - X.begin()); int v2 = *max_element(data, data+5); // Либо же просто в массиве int i3 = min_element(data, data+5) - data;
В рамках введения в экстремальное программирование следует присмотреться к следующему макросу:
#define all(c) c.begin(),c.end()
(скобки вокруг правой части здесь ставить ни в коем случае нельзя!)
Также часто используется алгоритм sort(iterator begin, iterator end) .
vector X; . sort(X.begin(), X.end()); // Стандартный вызов sort(all(X)); // Почувствуйте разницу sort(X.rbegin(), X.rend()); // Сортировка в обратном порядке
Алгоритм сортировки активно использует арифметику на указателях, он может работать только на итераторах произвольного доступа. Отсортировать двусвязный список — нетривиальная алгоритмическая задача. На практике в такой ситуации проще сделать из него vector , а затем осуществить обратное преобразование. В этом помогут интервальные конструкторы:
deque q; . // Упорядочим элементы в q по неубыванию vector v(all(q)); // то же, что vector v(q.begin(), q.end()); sort(all(v)); q.assign(all(v)); // то же, что q = deque(all(v));
Следует сделать важное замечание о компиляции программ в STL. Дело в том, что STL распространяется в исходных кодах (это существенно влияет на производительность результирующего кода), поэтому зачастую строка с ошибкой будет указывать не на ваш код, а на внутренности STL. При этом строка с описанием ошибки будет занимать несколько сотен символов, что не сразу проливает свет на истинную причину её возникновения. Разберём только один простой пример.
Пусть мы передаём vector как const reference параметр (как это и следует делать) в некую функцию. А в этой функции мы работаем с этим массивом посредством итераторов:
void f(const vector& v) < for( vector::iterator it = v.begin(); // ну что же здесь не так . . >
В этом коротком участке кода есть ошибка. Вы можете её обнаружить?
Дело в том, что из немодифицируемого (const) объекта мы пытаемся получить модифицируемый (non-const) итератор при помощи функции begin() . Подобное преобразование является недопустимым. Корректный код выглядит следующим образом:
void f(const vector& v) < int r = 0; // используется const_iterator for(vector::const_iterator it = v.begin(); it != v.end(); it++) < r += (*it) * (*it); >return r; >
В свете всего вышесказанного, имеет смысл знать про одну очень интересную функцию компилятора GNU C++. Заметим, что данная функция не входит в cтандарт C++, поэтому в большинстве других компиляторов её нет.
Итак, «оператор» typeof(x) . На этапе компиляции он заменяется на тип выражения в скобках. Пример:
typeof(a+b) x = (a+b);
Переменная x будет иметь тип, соответствующий типу выражения a+b . Напомним, что typeof(c.size()) — unsigned int для всех контейнеров STL. Но наибольшую пользу можно извлечь из typeof в следующем контексте:
#define tr(container, iterator) \ for(typeof(container.begin()) iterator=container.begin(); \ it != container.end(); it++)
Данный макрос — сокращение от traverse — будет работать даже для самого сложного типа контейнера, независимо от того, каким образом этот контейнер к моменту использования определён. Для const -объектов он породит const_iterator ‘ы:
void f(const vector& v) < int r = 0; tr(v, it) < r += (*it)*(*it); >return r; >
Подобные ухищрения не столь важны при работе с векторами, но они совершенно незаменимы при работа с более сложными контейнерами. Это чувствуется особенно хорошо, когда код принимает примерно следующий вид:
void operate(const map < set< pair>, vector < pair< double, pair> > > &object) < for( . ) // MAMMA MIA! >
Хотя, например, такая операция, как подсчитать сумму всех double из правой части map с использованием макроса tr выполняется сравнительно просто:
void operate(const map < set< pair>, vector < pair< double, pair> > > &c) < double result = 0; tr(c, it) < tr(it->second, it2) < result += it2->first; > > return result; >
Добавление данных в vector выполняется при помощи метода insert . У insert есть несколько форм.
vector v; . // Добавить элемент со значением 42 // непосредственно после первого элемента вектора v.insert(v.begin() + 1, 42);
При выполнении такой операции:
— вектор расширится на один элемент;
— все элементы вектора, начиная со второго (индекс 1) по последний, сместятся вправо, освобождая место для нового элемента;;
— новый элемент со значением 42 займёт своё место.
Если необходимо добавить много элементов в середину вектора, логично выполнить один сдвиг сразу на несколько элементов. Для этого используется интервальная форма insert : insert(iterator1 where, iterator2 what_begin, iterator2 what_end) . При этом типы итераторов iterator1 и iterator2 могут не совпадать — insert может, к примеру, вставить в vector содержимое контейнера set .
vector v; vector v2; . // вставить содержимое v2 в обратном порядке в середину v v.insert(v.begin() + (v.size()/2), v2.rbegin(), v2.rend());
Для удаления элементов из vector используется метод erase . У erase также есть две формы:
erase(iterator what); erase(iterator from, iterator to);
Технология методов insert / erase так или иначе используется во всех типах контейнеров STL.
В STL существует специальный контейнер для работы со строками: string . Этот контейнер не очень сильно отличается от vector . Различия, в основном, сосредоточены в функциях для манипулирования строками и в политике работы с памятью. Для того, чтобы узнать длину строки, принято использовать string::length() , а не vector::size() .
У строк есть метод substr для быстрого получения подстроки в виде отдельной строки. Этот метод принимает в качестве параметров только индексы, и никаких итераторов:
string s = "hello"; string s1 = s.substr(0, 3), // "hel" s2 = s.substr(1, 3), // "ell" s3 = s.substr(0, s.length()-1), "hell" s4 = s.substr(1); // "ello"
Как и в случае с vector::size() , string::length() возвращает беззнаковый тип. Поэтому будьте аккуратны с конструкциями вроде (s.length()-1) : для пустой строки s результат, скорее всего, не оправдает ваших ожиданий.
Также бывает удобным использовать метод string::find() . Он возвращает индекс начала первого вхождения символа или строки.
Кроме string::find , бывает удобно использовать метод string::find_first_of . Если передать в качестве параметра find_first_of один символ, вызов find_first_of будет полностью аналогичен вызову find . Однако, если передать в качестве параметра find_first_of строку, метод вернёт индекс первого вхождения любого символа из данной строки:
string s = "Hello, World!"; int index = s.find_first_of(' '); // поиск первого пробела int index2 = s.find_first_of(", !"); // поиск первого пробела, //знака восклицания или запятой
Особенно find_first_of удобно использовать для того, чтобы разделить строку на множество строк. Это актуально, потому как встроенных функций для string splitting в STL, к сожалению, нет.
// разбить строку на вектор строк, // используя пробелы и запятые как разделители vector v; size_t i; while((i = s.find_first_of(", ")) != string::npos) < // кусок строки до первого разделителя v.push_back(s.substr(0, i)); // вырезать вместе с разделителем s = s.substr(i+1); >v.push_back(s); // дописать остаток строки
Строки можно складывать с помощью оператора + :
string s = "hello"; string s1 = s.substr(0, 3), // "hel" s2 = s + s1; // " helloell"
Строки можно складывать с помощью оператора + и с символами, но нужно быть аккуратными с константными строками. Запись «jdklasj» — это переменная типа const char* . В большинстве случаев, но не всегда, объекты типа const char* по мере необходимости приводятся к типу string напрямую. Этого не происходит лишь в одном случае: складывать две константных строки нельзя. Для этого нужно привести первую из них к типу string напрямую. Впрочем, если обе строки — действительно константные, можно просто опустить знак + .
У string нет конструктора от одного char . Для того, чтобы создать строку, состоящую из одного символа, можно либо добавить этот символ к пустой строке ( string(«») + ‘A’ ), либо использовать инициализацию в стиле vector : string(1, ‘B’) . Соответственно, таким же образом создаются строки, состоящие из фиксированного числа одинаковых символов.
В общем случае лучше работать с типом string , чем с const char* . Иначе может так случиться, что компилятор подумает совсем не то, что вы имели в виду:
string s = "word", s2; s = 'S' + s + '!'; // "Sword!" s2 = 'A' + " and " + 'B'; //таких конструкций следует избегать. фактически здесь мы //к числу типа char прибавили указатель, а потом еще раз число s2 = 'X' + string(" and ") + 'Y'; // "X and Y" √-- это корректно string s3wrong = "p " + " and q "; // не компилируется string s3 = "p" " and q"; // так можно, //но всегда проще написать string("p") + ' ' + "and q";
Также строки можно сравнивать с помощью операторов сравнения. Таким образом, vector можно упорядочивать стандартными методами. Строки сравниваются в лексикографическом порядке.
Мы подошли к двум наиболее интересным с точки зрения изучения STL контейнерам: set и map . С которым из них стоит познакомиться в первую очередь — вопрос, не имеющий однозначного ответа. Мнение автора заключается в том, что при академическом подходе к изучению STL, в первую очередь следует познакомиться с set , как с более простым контейнером из рассматриваемой пары. Всё, что можно сделать с set , можно сделать и с map , обратное же утверждение не всегда истинно. С алгоритмической точки зрения map является логическим продолжением set , в то время как многие программисты-практики зачастую смутно понимают назначение контейнера set , и всегда используют map , что менее элегантно и часто более сложно для понимания сторонними людьми.
Контейнер set , как уже было упомянуто, содержит множество элементов. Строго говоря, set обеспечивает следующую функциональность:
— добавить элемент в рассматриваемое множество, при этом исключая возможность появления дублей;
— удалить элемент из множества;
— узнать количество (различных) элементов в контейнере;
— проверить, присутствует ли в контейнере некоторый элемент.
Об алгоритмической эффективности контейнера set мы поговорим позже, вначале познакомимся с его интерфейсом.
set s; for(int i = 1; i s.insert(42); // ничего не произойдёт --- // элемент 42 уже присутствует в множестве for(int i = 2; i // set::size() имеет тип unsigned int int N = int(s.size()); // N будет равно 50
У set нет метода push_back() . Это неудивительно: ведь такого понятия, как порядок элементов или индекс элемента, в set не существует, поэтому слово «back» здесь никак не применимо.
А раз уж у set нет понятия «индекс элемента», единственный способ просмотреть данные, содержащиеся в set , заключается в использовании итераторов:
set S; . // вычисление суммы элементов множества S int r = 0; for(set::const_iterator it = S.begin(); it != S.end(); it++)
Если вы пользуетесь GNU C++, то Traversing Macros будет весьма кстати. Показательный пример:
set < pair> > SS; . int total = 0; tr(SS, it) < total += it->second.first; >
Обратите внимание на синтаксис it->second.first . Ввиду того, что it является итератором, перед использованием его необходимо разыменовать. «Верным» синтаксисом было бы (*it).second.first . Однако, в C++ есть негласное правило, что если при описании некоторого объекта есть возможность обеспечить тождественное равенство конструкций (*it). и it-> , то это следует сделать, дабы не вводить пользователей в заблуждение. Разработчики STL, конечно, позаботились об этом в случае с итераторами.
Основным преимуществом set перед vector является, несомненно, быстродействие. В основном это быстродействие проявляется при выполнении операции поиска. (При добавлении операция поиска также неявно присутствует, потому как дубли в set не допускаются). Однако, с операцией поиска в set / map есть существенный нюанс.
Нюанс заключается в том, что вместо глобального алгоритма std::find(. ) следует использовать метод set set::find(. ) .
Это не означает, что std::find(. ) не будет работать с set . Дело в том, что std::find(. ) ничего не знает о типе контейнера, с которым он работает. Принцип работы std::find(. ) крайне прост: он просматривает все элементы до тех пор, пока либо не будет найден искомый элемент, либо не будет достигнут конец интервала. Основное преимущество set перед vector заключается в использовании нелинейной структуры данных, что существенно снижает алгоритмическую сложность операции поиска; использование же std::find(. ) ануллирует все старания разработчиков STL.
Метод set::find(. ) имеет всего один аргумент. Возращаемое им значение либо указывает на найденный элемент, либо равно итератору end() для данного экземпляра контейнера.
set s; . if(s.find(42) != s.end()) < // 42 присутствует >else < // 42 не присутствует >
Кроме find(. ) существует также операция count(. ) , которую следует вызывать как метод set::count(x) , а не как алгоритм std::count(begin, end, x) . Ясно, что set::count(x) может вернуть только 0 или 1. Некоторые программисты считают, что вышеприведённый код лучше выглядит, если использовать count(x) вместо find(x) :
if(s.count(42) != 0)
if(s.count(42))
Мнение автора заключается в том, что подобный код вводит читателя в заблуждение: сам смысл операции count() несовместим со случаями, когда элемент либо присутствует, либо нет. Если же вам предтавляется слишком длинным каждый раз писать «[некоторая форма find]» != container.end() , сделайте следующие макросы:
#define present_member(container, element) \ (find(all(container),element) != container.end()) #define present_global(container, element) \ (container.find(element) != container.end())
Здесь all(c) означает c.begin(),c.end()
Более того, в соответствии с положением cтандарта, которое называется «конкретизация шаблонов», можно написать следующий код:
template bool present(const T& c, const T2& obj) < return find(c.begin(), c.end(), (T::element_type)(obj)) != c.end(); >template bool present(const set& c, const T2& obj)
При работе с контейнером типа set present(container, element) вызовет метод set::find(element) , в других случаях — std::find(container.begin(), container.end(), element) .
Для удаления элемента из set необходимо вызвать метод erase(. ) , передав ему один элемент — элемент, который следует удалить, либо итератор, указывающий на удаляемый элемент.
set s; . s.insert(54); . s.erase(29); s.erase(s.find(57));
Как и полагается erase(. ) , set::erase(. ) имеет интервальную форму.
set s; . set::iterator it1, it2; it1 = s.find(10); it2 = s.find(100); // Будет работать, если как 10, так и 100 присутствуют в множестве if(. ) < s.erase(it1, it2); // при таком вызове будут удалены // все элементы от 10 до 100 не включительно >else < // сдвинем it2 на один элемент вперёд // set::iterator является normal iterator // операция += не определена для итераторов set'а, //но ++ и -- допускаются it2++; s.erase(it1, it2); // а при таком --- от 10 до 100 включительно // приведённый код будет работать, даже если 100 был // последним элементом, входящим в set >
Также, как и полагается контейнерам STL, у set есть интервальный конструктор:
int data[5] = < 5, 1, 4, 2, 3 >; set S(data, data+5);
Кстати, данная функция set предоставляет эффективную возможность избавиться от дубликатов в vector :
vector v; . set s(all(v)); vector v2(all(s));
Теперь v2 содержит те же элементы, что и v , но без дубликатов. Приятной особенностью также является тот факт, что элементы v2 упорядочены по возрастанию, но об этом мы поговорим позже.
В set можно хранить элементы любого типа, которые можно упорядочить. Об этом мы тоже поговорим позже.
Теперь мы можем перейти от set к map . «Введение в map для чайников» могло бы выглядеть следующим образом:
map M; M[«One»] = 1; M[«Two»] = 2; M[«Many»] = 7; int x = M[«One»] + M[«Two»]; if(M.find(«Five») != M.end())
Очень просто, не так ли?
На самом деле, map очень похож на set , за исключением того, что вместо элементов map хранит пары элементов . Поиск при этом осуществляется только по ключу. Крайне приятно наличие оператора обращения по «индексу» ( operator [] ).
Для того, чтобы просмотреть содержимое map , необходимо использовать итераторы. Удобнее всего это делать при помощи нашего макроса tr . Следует помнить, что итератор указывает не на элемент key , а на pair :
map M; . M["one"] = 1; M["two"] = 2; M["google"] = 1e100; . // найдём сумму всех значений --- т.е. всех правых частей // пар int r = 0; tr(M, it) < r += it->second; // (*it).first == [string], (*it).second == [int] >
Как и в случае с set , элементы map хранятся упорядоченными по ключу. Поэтому не следует при работе с map::iterator модифицировать it->first : если вы нарушите правила упорядочивания элементов в map , за последствия никто отвечать не возьмётся.
В остальном контейнер map по интерфейсу практически эквивалентен контейнеру set .
Также важно помнить, что operator [] при обращении к несуществующему элементу в map создаст его. Новый элемент при этом будет инициализирован нулём (либо конструктором по умолчанию, если это не тривиальный тип данных). Данная особенность map может быть удобной, потому как выполнять операции с элементами можно не задумываясь об их присутствии в map . Существенным моментом является то, что operator [] не является константным (то есть может изменить объект, для которого вызван), поэтому им нельзя пользоваться, если map передан как const reference. Используйте map::find(element) :
void f(const map& M) < if(M["the meaning"] == 42) < // Так нельзя! M передан как const reference >if(M.find("the meaning") != M.end() && M.find("the meaning")->second == 42) < // А можно именно так cout >
Литература и ссылки
1. Scott Meyers, Effective STL. Addison Wesley Professional, 2001.
Структура pair
Иногда удобно в одной переменной хранить одновременно два значения, например, два целых числа. Например, координаты точки на плоскости удобно хранить в одной переменной, содержащих два числа: x-координату и y-координату. Для этого в STL есть шаблон pair (пара), особенно удобно использовать pair для сортировки объектов.
Pair является переменной, объединяющей в себе два значения, которые могут быть одного или разных типов. Например, чтобы создать переменную типа pair, содержащую два поля типа int нужно использовать следующее объявление:
pair a;
Теперь переменная a будет хранить в себе два значения типа int . Получить доступ к первому значению можно при помощи записи a.first , а ко второму значению — a.second , они называются полями переменной. Каждому полю можно присваивать независимые значения, например, так:
a.first = 1; a.second = 2;
Присвоить одновременно два значения обоим полям пары можно при помощи функции make_pair , принимающующей два аргумента и возвращающей значение типа pair с соответствующими полями:
a = make_pair(1, 2);
Между тем с переменной типа pair можно работать и как с единым целым, например, если объявить две переменные типа pair с одинаковыми типами полей, то можно одной переменной присвоить значение другой переменной:
pair a, b; . b = a;
Но при вводе-выводе переменных, типа pair нельзя выводить или вводить значение переменной одной командой, то есть нельзя сразу же вывести два значения типа:
cin >> a; coutВместо этого нужно отдельно считывать или выводить каждое поле пары.
Можно создавать пару с полями разных типов, например, чтобы поле first имело тип double , а поле second — string , нужно использовать запись pair .
С парой, как с целым (то есть одновременно с двумя полями структуры) можно выполнять следующие операции: = , == , != , < , , >= , а также использовать в качестве аргумента функции swap . При использовании операций сравнения (типа меньше, больше и т.д.) пары сравниваются в лексикографическом порядке, то есть сначала по полю first , а если поля first равны, то по полю second .
vector < pair< int, int>> aОбратите внимание на пробел между закрывающими угловыми скобками: он обязателен, иначе компилятор будет считать это операцией “ >> ”
Язык программирования Rust
Первым типом коллекции, который мы разберём, будет Vec , также известный как вектор (vector). Векторы позволяют хранить более одного значения в единой структуре данных, хранящей элементы в памяти один за другим. Векторы могут хранить данные только одного типа. Их удобно использовать, когда нужно хранить список элементов, например, список текстовых строк из файла, или список цен товаров в корзине покупок.
Создание нового вектора
Чтобы создать новый пустой вектор, мы вызываем функцию Vec::new , как показано в листинге 8-1.
fn main() let v: Vec = Vec::new(); >Листинг 8-1: Создание нового пустого вектора для хранения значений типа i32
Обратите внимание, что здесь мы добавили аннотацию типа. Поскольку мы не вставляем никаких значений в этот вектор, Rust не знает, какие элементы мы собираемся хранить. Это важный момент. Векторы реализованы с использованием обобщённых типов; мы рассмотрим, как использовать обобщённые типы с вашими собственными типами в Главе 10. А пока знайте, что тип Vec , предоставляемый стандартной библиотекой, может хранить любой тип. Когда мы создаём новый вектор для хранения конкретного типа, мы можем указать этот тип в угловых скобках. В листинге 8-1 мы сообщили Rust, что Vec в v будет хранить элементы типа i32 .
Чаще всего вы будете создавать Vec с начальными значениями и Rust может определить тип сохраняемых вами значений, но иногда вам всё же придётся указывать аннотацию типа. Для удобства Rust предоставляет макрос vec! , который создаст новый вектор, содержащий заданные вами значения. В листинге 8-2 создаётся новый Vec , который будет хранить значения 1 , 2 и 3 . Числовым типом является i32 , потому что это тип по умолчанию для целочисленных значений, о чём упоминалось в разделе “Типы данных” Главы 3.
fn main() let v = vec![1, 2, 3]; >Листинг 8-2: Создание нового вектора, содержащего значения
Поскольку мы указали начальные значения типа i32 , Rust может сделать вывод, что тип переменной v это Vec и аннотация типа здесь не нужна. Далее мы посмотрим как изменять вектор.
Изменение вектора
Чтобы создать вектор и затем добавить к нему элементы, можно использовать метод push показанный в листинге 8-3.
fn main() let mut v = Vec::new(); v.push(5); v.push(6); v.push(7); v.push(8); >Листинг 8-3: Использование метода push для добавления значений в вектор
Как и с любой переменной, если мы хотим изменить её значение, нам нужно сделать её изменяемой с помощью ключевого слова mut , что обсуждалось в Главе 3. Все числа которые мы помещаем в вектор имеют тип i32 по этому Rust с лёгкостью выводит тип вектора, по этой причине нам не нужна здесь аннотация типа вектора Vec .
Чтение данных вектора
Есть два способа сослаться на значение, хранящееся в векторе: с помощью индекса или метода get . В следующих примерах для большей ясности мы указали типы значений, возвращаемых этими функциями.
В листинге 8-4 показаны оба метода доступа к значению в векторе: либо с помощью синтаксиса индексации и с помощью метода get .
fn main() let v = vec![1, 2, 3, 4, 5]; let third: &i32 = &v[2]; println!("The third element is "); let third: Option = v.get(2); match third < Some(third) =>println!("The third element is "), None => println!("There is no third element."), > >Листинг 8-4. Использование синтаксиса индексации и метода get для доступа к элементу в векторе
Обратите внимание здесь на пару деталей. Мы используем значение индекса 2 для получения третьего элемента: векторы индексируются начиная с нуля. Указывая & и [] мы получаем ссылку на элемент по указанному индексу. Когда мы используем метод get содержащего индекс, переданный в качестве аргумента, мы получаем тип Option , который мы можем проверить с помощью match .
Причина, по которой Rust предоставляет два способа ссылки на элемент, заключается в том, что вы можете выбрать, как программа будет себя вести, когда вы попытаетесь использовать значение индекса за пределами диапазона существующих элементов. В качестве примера давайте посмотрим, что происходит, когда у нас есть вектор из пяти элементов, а затем мы пытаемся получить доступ к элементу с индексом 100 с помощью каждого метода, как показано в листинге 8-5.
fn main() let v = vec![1, 2, 3, 4, 5]; let does_not_exist = &v[100]; let does_not_exist = v.get(100); >Листинг 8-5. Попытка доступа к элементу с индексом 100 в векторе, содержащем пять элементов
Когда мы запускаем этот код, первая строка с &v[100] вызовет панику программы, потому что происходит попытка получить ссылку на несуществующий элемент. Такой подход лучше всего использовать, когда вы хотите, чтобы ваша программа аварийно завершила работу при попытке доступа к элементу за пределами вектора.
Когда методу get передаётся индекс, который находится за пределами вектора, он без паники возвращает None . Вы могли бы использовать такой подход, если доступ к элементу за пределами диапазона вектора происходит время от времени при нормальных обстоятельствах. Тогда ваш код будет иметь логику для обработки наличия Some(&element) или None , как обсуждалось в Главе 6. Например, индекс может исходить от человека, вводящего число. Если пользователь случайно введёт слишком большое число, то программа получит значение None и у вас будет возможность сообщить пользователю, сколько элементов находится в текущем векторе, и дать ему возможность ввести допустимое значение. Такое поведение было бы более дружелюбным для пользователя, чем внезапный сбой программы из-за опечатки!
Когда у программы есть действительная ссылка, borrow checker (средство проверки заимствований), обеспечивает соблюдение правил владения и заимствования (описанные в Главе 4), чтобы гарантировать, что эта ссылка и любые другие ссылки на содержимое вектора остаются действительными. Вспомните правило, которое гласит, что у вас не может быть изменяемых и неизменяемых ссылок в одной и той же области. Это правило применяется в листинге 8-6, где мы храним неизменяемую ссылку на первый элемент вектора и затем пытаемся добавить элемент в конец вектора. Данная программа не будет работать, если мы также попробуем сослаться на данный элемент позже в функции:
fn main() let mut v = vec![1, 2, 3, 4, 5]; let first = &v[0]; v.push(6); println!("The first element is: "); >Листинг 8-6. Попытка добавить некоторый элемент в вектор, в то время когда есть ссылка на элемент вектора
Компиляция этого кода приведёт к ошибке:
$ cargo run Compiling collections v0.1.0 (file:///projects/collections) error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable --> src/main.rs:6:5 | 4 | let first = &v[0]; | - immutable borrow occurs here 5 | 6 | v.push(6); | ^^^^^^^^^ mutable borrow occurs here 7 | 8 | println!("The first element is: "); | ----- immutable borrow later used here For more information about this error, try `rustc --explain E0502`. error: could not compile `collections` due to previous errorКод в листинге 8-6 может выглядеть так, как будто он должен работать. Почему ссылка на первый элемент должна заботиться об изменениях в конце вектора? Эта ошибка возникает из-за особенности того, как работают векторы: поскольку векторы размещают значения в памяти друг за другом, добавление нового элемента в конец вектора может потребовать выделения новой памяти и копирования старых элементов в новое пространство, если нет достаточного места, чтобы разместить все элементы друг за другом там, где в данный момент хранится вектор. В этом случае ссылка на первый элемент будет указывать на освобождённую память. Правила заимствования предотвращают попадание программ в такую ситуацию.
Примечание: Дополнительные сведения о реализации типа Vec смотрите в разделе "The Rustonomicon".
Перебор значений в векторе
Для доступа к каждому элементу вектора по очереди, мы итерируем все элементы, вместо использования индексов для доступа к одному за раз. В листинге 8-7 показано, как использовать цикл for для получения неизменяемых ссылок на каждый элемент в векторе значений типа i32 и их вывода.
fn main() let v = vec![100, 32, 57]; for i in &v < println!(""); > >Листинг 8-7. Печать каждого элемента векторе, при помощи итерирования по элементам вектора с помощью цикла for
Мы также можем итерировать изменяемые ссылки на каждый элемент изменяемого вектора, чтобы вносить изменения во все элементы. Цикл for в листинге 8-8 добавит 50 к каждому элементу.
fn main() let mut v = vec![100, 32, 57]; for i in &mut v < *i += 50; >>Листинг 8-8. Итерирование и изменение элементов вектора по изменяемым ссылкам
Чтобы изменить значение на которое ссылается изменяемая ссылка, мы должны использовать оператор разыменования ссылки * для получения значения по ссылке в переменной i прежде чем использовать оператор += . Мы поговорим подробнее об операторе разыменования в разделе “Следование по указателю к значению с помощью оператора разыменования” Главы 15.
Перебор вектора, будь то неизменяемый или изменяемый, безопасен из-за правил проверки заимствования. Если бы мы попытались вставить или удалить элементы в телах цикла for в листингах 8-7 и 8-8, мы бы получили ошибку компилятора, подобную той, которую мы получили с кодом в листинге 8-6. Ссылка на вектор, содержащийся в цикле for, предотвращает одновременную модификацию всего вектора.
Использование перечислений для хранения множества разных типов
Векторы могут хранить значения только одинакового типа. Это может быть неудобно; определённо могут быть случаи когда надо хранить список элементов разных типов. К счастью, варианты перечисления определены для одного и того же типа перечисления, поэтому, когда нам нужен один тип для представления элементов разных типов, мы можем определить и использовать перечисление!
Например, мы хотим получить значения из строки в электронной таблице где некоторые столбцы строки содержат целые числа, некоторые числа с плавающей точкой, а другие - строковые значения. Можно определить перечисление, варианты которого будут содержать разные типы значений и тогда все варианты перечисления будут считаться одним и тем же типом: типом самого перечисления. Затем мы можем создать вектор для хранения этого перечисления и, в конечном счёте, для хранения различных типов. Мы покажем это в листинге 8-9.
fn main() enum SpreadsheetCell < Int(i32), Float(f64), Text(String), >let row = vec![ SpreadsheetCell::Int(3), SpreadsheetCell::Text(String::from("blue")), SpreadsheetCell::Float(10.12), ]; >Листинг 8-9: Определение enum для хранения значений разных типов в одном векторе
Rust должен знать, какие типы будут в векторе во время компиляции, чтобы точно знать сколько памяти в куче потребуется для хранения каждого элемента. Мы также должны чётко указать, какие типы разрешены в этом векторе. Если бы Rust позволял вектору содержать любой тип, то был бы шанс что один или несколько типов вызовут ошибки при выполнении операций над элементами вектора. Использование перечисления вместе с выражением match означает, что во время компиляции Rust гарантирует, что все возможные случаи будут обработаны, как обсуждалось в главе 6.
Если вы не знаете исчерпывающий набор типов, которые программа получит во время выполнения для хранения в векторе, то техника использования перечисления не сработает. Вместо этого вы можете использовать типаж-объект, который мы рассмотрим в главе 17.
Теперь, когда мы обсудили некоторые из наиболее распространённых способов использования векторов, обязательно ознакомьтесь с документацией по API вектора, чтобы узнать о множестве полезных методов, определённых в Vec стандартной библиотеки. Например, в дополнение к методу push , существует метод pop , который удаляет и возвращает последний элемент.
Удаление элементов из вектора
Подобно структурам struct , вектор высвобождает свою память когда выходит из области видимости, что показано в листинге 8-10.
fn main() < let v = vec![1, 2, 3, 4]; // do stuff with v >// >Листинг 8-10. Показано как удаляется вектор и его элементы
Когда вектор удаляется, всё его содержимое также удаляется: удаление вектора означает и удаление значений, которые он содержит. Средство проверки заимствования гарантирует, что любые ссылки на содержимое вектора используются только тогда, когда сам вектор действителен.
Давайте перейдём к следующему типу коллекции: String !