Вектор

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

Тип Vec (вектор) представляет из себя непрерывную последовательность элементов, размер которой может определяться и изменяться во время выполнения программы.

Note

Vec<T> является обобщённой (generic) структурой. И генерики, и структуры мы изучим только несколько глав спустя, однако вектор является настолько вездесущей структурой данных, что изучать даже базовые конструкции Rust без него будет очень сложно. Поэтому, на данном этапе мы только разберёмся, как с ним работать и как он располагается в памяти.
Если же вы знакомы с C++, то вы уже, скорее всего, провели аналогию с шаблонным классом std::vector, и оказались полностью правы.
Если вы знакомы с Java, то считайте вектор близким родственником класса ArrayList<T>.

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

fn main() {
  // Создаём пустой вектор
  let mut my_vec: Vec<i32> = Vec::new();

  my_vec.push(1); // Добавляем 1 в конец вектора
  my_vec.push(2); // Добавляем 2 в конец вектора
  my_vec.push(3); // Добавляем 3 в конец вектора

  // Копируем в переменную third значение элемента с индексом 2 (индексация с нуля)
  let third: i32 = my_vec[2];
  println!("3-rd element: {}", third);
}

Как видно, с точки зрения использования, вектор можно рассматривать просто как динамически расширяемый массив.

Лэйаут (расположение) в памяти

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

На стеке хранятся такие 3 поля:

• указатель на начало буфера в куче — в этом буфере хранятся сами элементы вектора
• счётчик количества элементов, записанных в буфере в куче
• размер буфера в куче

Лэйаут (layout) вектора из примера выше в оперативной памяти выглядит так:

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

Если желаемый размер буфера в куче известен заранее, то его можно задать явно, заменив Vec::new() на Vec::with_capacity(размер). Это приведёт к тому, что вектор аллоцирует первичный буфер в куче ровно такого размера, чтобы иметь возможность вместить ровно заданное количество элементов.

При добавлении элементов в вектор, счётчик элементов в буфере (len) увеличивается. Когда len становится равным capacity — то есть буфер в куче будет полностью заполнен, тогда вектор аллоцирует новый буфер большего размера, копирует в него все элементы из старого буфера и затем удаляет старый буфер. Последующее добавление элементов продолжится уже в новый буфер.

#![allow(unused)]
fn main() {
  let mut my_vec: Vec<i32> = Vec::with_capacity(3);

  my_vec.push(1);
  my_vec.push(2);
  my_vec.push(3);

  // <- на этом месте буфер, чья вместимость - 3 элемента, уже заполнен

  // Добавление 4-го элемента приведёт к выделению нового буфера
  // и копированию в него 1,2,3.
  // После этого 4 будет добавлено уже в новый буфер.
  my_vec.push(4);
}

Макрос vec!

В предыдущем примере для создания вектора с элементами мы сначала создали пустой вектор, а затем один за другим добавили в него все необходимые элементы. Согласитесь, что добавлять элементы по одному — весьма неудобно. Поэтому, учитывая, что вектор является наиболее часто используемой структурой данных, в стандартную библиотеку Rust включили специальный макрос vec![], который берёт на себя бремя поэлементного добавления элементов в вектор.

При помощи этого макроса, мы можем переписать пример выше таким образом:

fn main() {
  let mut my_vec = vec![1,2,3];

  let third: i32 = my_vec[2];
  println!("3-rd element: {}", third);
}

Как работает этот макрос станет понятно только после прочтения главы Декларативные макросы.