Вектор как параметр функции c

Функции

right
Вектор, содержащий элементы, которые будут заменены, или вектор, элементы которого должны быть заменены на элементы вектора left .

left
Вектор, элементы которого должны поменяться местами с элементами вектора right .

Замечания

Функция шаблона — это алгоритм, специализированный для вектора класса контейнера для выполнения функции-члена left. vector::swap (right) . Это экземпляры частичного упорядочивания шаблонов функций компилятором. Если функции шаблона перегружены таким образом, чтобы совпадение шаблона с вызовом функции не было уникальным, компилятор выберет самую специализированную версию функции шаблона. Общая версия функции шаблона, template void swap(T&, T&) в классе алгоритма работает по назначению и является медленной операцией. Специализированная версия в каждом контейнере работает гораздо быстрее, так как она может работать с внутренним представлением класса контейнера.

Пример

Пример кода для функции-члена vector::swap см. в примере, использующего версию swap шаблона.

Передача вектора в качестве аргумента функции

Здравствуйте, я только недавно начал изучать C++, поэтому проблема может показаться дурацкой, но надеюсь, что поможете.
Проблема такая, решил для практики написать простую программку, которая запрашивает количество заказанных блюд, их названия и цену, а потом выводит на экран уже с общей суммой.
Для цен и наименований блюд сделал два вектора, а вывод и подсчёт суммы выделил в отдельную функцию, но компилятор ругается на вызов этой функции и выдаёт ошибку «no matching function for call to «total»». Я пробовал сделать то же уже с обычным массивом и всё заработало, но всё же хочется узнать, что не так я делал с векторами.

#include #include #include using namespace std; void line() < for (int i=0; icout int total(int kol_vo, string dish[], int cost[]) < int sum=0; line(); for (int i=0; i int main()< cout>kol; vectordishes(kol); vectorcost(kol); for (int i=0; i>dishes[i]; cout>cost[i]; > cout

Отслеживать

219k 15 15 золотых знаков 119 119 серебряных знаков 230 230 бронзовых знаков

Обобщенное программирование

Зачастую при реализации какой-либо структуры данных или алгоритма хочется, чтобы один и тот же код работал для разных типов элементов и в целом не зависел от их типа. С примерами вы уже сталкивались ранее — это контейнеры стандартной библиотеки такие как vector , list , set и др., а также обобщённые алгоритмы: sort , accumulate и т.д. Создавать такой код возможно благодаря использованию шаблонов.

Рассмотрим небольшой пример — мы хотим реализовать класс трёхмерного вектора, который может состоять из скаляров разного типа: double , float , int , bool и т.д.:

template typename T> class Vector3  private: T elements[3]; public: Vector3(T x, T y, T z)  this->elements[0] = x; this->elements[1] = y; this->elements[2] = z; > T& operator[](int i)  return elements[i]; > const T& operator[](int i) const  return elements[i]; > >;

Чтобы наш класс был шаблонным, перед его объявлением используется ключевое слово template , за которым в угловых скобках следует список параметров шаблона. Параметры имеют тип — в нашем случае это typename — то есть параметр T сам является каким-то типом. После этого мы можем свободно использовать T внутри нашего класса как какой-то определённый, но пока неизвестный нам тип.

Теперь, чтобы создать экземпляры нашего вектора, мы указываем шаблонный тип и затем его параметры в угловых скобках:

Vector3double> real_vec(1.0, 2.0, 3.0); Vector3int> int_vec(2, 4, 6);

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

template typename T> Vector3T> operator+(const Vector3T>& a, const Vector3T>& b)  Vector3T> result; for (int i = 0; i  3; ++i)  result[i] += a[i] + b[i]; > return result; > template typename T> T dot(const Vector3T>& a, const Vector3T>& b)  T result = T(0); for (int i = 0; i  3; ++i)  result += a[i] * b[i]; > return result; >

Теперь мы можем использовать эти функции:

Vector3double> a(1.0, 2.0, 3.0), b(3.0, 2.0, 1.0); Vector3double> c = a + b; double d = dot(a, b);

Обратите внимание, что после dot мы не указываем параметр несмотря на то, что это шаблонная функция (как и оператор сложения). Дело в том, что в данном случае компилятор самостоятельно может определить тип параметра T из аргументов функции.

Целочисленные параметры

Наш вектор может хранить произвольный тип компонентов, однако что делать если мы захотим использовать двумерный или четырёхмерный вектор помимо трёхмерного? Оказывается, параметризовать можно также и размерность вектора.

template typename T, int N> class Vector  private: T elements[N]; public: // . >;

В данном случае N это не тип, а целое число. Пример такого шаблона с целочисленным параметром в стандартной библиотеке — массив фиксированного размера array .

Так же можно определить и шаблонные функции:

template typename T, int N> T dot(const VectorT, N>& a, const VectorT, N>& b)  T result = T(0); for (int i = 0; i  N; ++i)  result += a[i] * b[i]; > return result; >

Создаём наши вектора:

Vectordouble, 3> real3; Vectorint, 4> int4;

Есть очевидное ограничение — параметр N должен быть известен во время компиляции. Мы не сможем сделать так:

int n; std::cin >> n; Vectordouble, n> v; // ошибка компиляции

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

Частичная специализация

Иногда возникает ситуация, когда для какого-то определённого типа реализация шаблона должна отличаться от основной реализации. Например, в случае вектора, элементами которого является bool хранить массив bool elements[N]; было бы расточительно (т.к. каждый bool занимает целый байт, хотя достаточно одного бита). В таком случае нам поможет частичная специализация:

template int N> class Vectorbool, N>  private: unsigned char bits[(N - 1) / 8 + 1]; public: bool operator[](int i) const  return (bits[i / 8] >> (i % 8)) & 1; > void set(int i, bool v)  bits[i / 8] = (bits[i / 8] & ~(1  <(i % 8))) | ((unsigned char)v  <(i % 8)); > >;

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

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

Вариативные шаблоны

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

template typename T, int N> class Vector  private: T elements[N]; template int I, typename. Args> unwind(T x, Args. args)  static_assert(I  N, "Too many arguments"); this->elements[I] = x; unwindI + 1>(args. ); > template int I> unwind()  static_assert(I == N, "Too few arguments"); > public: template typename. Args> Vector(Args. args)  this->unwind0>(args. ); > // . >;

Давайте разберёмся по порядку, что тут происходит.

template typename. Args> Vector(Args. args)  this->unwind0>(args. ); >

Это объявление шаблонной функции (конструктора) с вариативным параметром, то есть принимающим произвольное число аргументов (начиная с нуля включительно). Вариативный параметр определяется тремя точками. Конструктор принимает произвольное число аргументов и вызывает перегруженную шаблонную функцию unwind . Разматывание (unwinding) — это единственный возможный способ работать с вариативными параметрами, так как C++ не позволяет просто пройтись по аргументам как по массиву. Рассмотрим, как работает разматывание.

Мы создаём две функции unwind :

Первая функция — основная. Она принимает индекс аргумента в качестве целочисленного шаблонного параметра, значение этого параметра в качестве первого аргумента, и все последующие аргументы в виде вариативного параметра.

template int I, typename. Args> unwind(T x, Args. args)  static_assert(I  N, "Too many arguments"); this->elements[I] = x; unwindI + 1>(); >

static_assert(I < N, "Too many arguments"); Сперва мы проверяем (см. static_assert ), что индекс аргумента не выходит за границу массива (т.е. что число аргументов не больше, чем размер вектора). Если аргументов больше, то произойдёт ошибка компиляции с сообщением Too many arguments .
this->elements[I] = x; Тут мы просто записываем очередной аргумент в вектор в нужную позицию.
unwind(); И, наконец, снова рекурсивно вызываем функцию unwind со следующим индексом, передавая ей оставшиеся аргументы. Если число оставшихся аргументов 1 и больше, то вызывается снова эта же версия функции, которая будет откусывать аргументы до тех пор, пока они не закончатся. Если список аргументов пуст, то вызовется вторая версия функции unwind , которую мы сейчас рассмотрим.

Вторая функция unwind — завершающая. Она не принимает аргументов, и вызывается, когда вариативные аргументы закончились.

template int I> unwind()  static_assert(I == N, "Too few arguments"); >

static_assert(I == N, «Too few arguments»); Единственное, что делает эта функция — проверяет, что индекс совпадает с размером массива, что означает, что число аргументов в точности равно размеру вектора. Если аргументов меньше, то на этом этапе произойдёт ошибка компиляции с сообщением Too few arguments .

Таким образом мы получили конструктор, который принимает произвольное число аргументов, и выдаёт ошибку компиляции, если число аргументов не соответствует размеру вектора.

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

template typename T, int. Dims> class Tensor  // . >;

И создать объекты:

Tensordouble, 2> vector2; Tensordouble, 3, 4> matrix3x4; Tensordouble, 3, 2, 4> tensor3x2x4;

Псевдонимы шаблонов

Можно создавать псевдонимы шаблонов так же как и псевдонимы типов, используя ключевое слово using . Например:

template typename T> using Vector4 = VectorT, 4>;

Тут мы создали псевдоним Vector4 , зафиксировав второй аргумент шаблонного класса Vector .

Заключение

Шаблоны — очень полезный инструмент в компилируемых языках. В C++ возможности шаблонного программирования чрезвычайно обширны, и позволяют создавать произвольные программы, которые будут выполняться и производить необходимые вычисления и проверки во время компиляции.

За бортом этого обзора остались многие инструменты обобщённого программирования на C++, такие как type traits стандартной библиотеки, механизм SFINAE, constexpr -функции и так далее. Вы можете ознакомиться с ними самостоятельно.

Ссылки

Шаблоны C++
Вариативный шаблон
Типовые и нетиповые параметры шаблонов
Частые вопросы про шаблоны

Цели и критерии

Цель: освоить std::vector на базовом уровне.

Критерии полноты

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

Введение

Для организации хранения наборов объектов Стандартная библиотека C++ предоставляет ряд шаблонов классов, называемых контейнерами containers . Стандартные контейнеры обладают определённой общностью интерфейсов, позволяющей в некоторых случаях заменять один контейнер другим, не изменяя при этом кода, ими оперирующего. Существуют сторонние библиотеки, предоставляющие контейнеры, совместимые со стандартными (например, из состава пакета библиотек Boost).

Контейнер задаёт способ хранения помещённых в него объектов (элементов контейнера) и распоряжается их существованием. При уничтожении контейнера все хранимые им элементы также уничтожаются (деструктором контейнера).

Наиболее популярным контейнером является std::vector — “вектор”, которому посвящена данная работа. Название “вектор” сложилось исторически и означает “динамический массив, способный автоматически увеличивать размер хранилища по мере надобности”, а не вектор в математическом смысле.

Вектор является шаблоном класса и в качестве первого (и единственного обязательного) параметра принимает тип хранимых объектов: std::vector — вектор целых чисел, std::vector — вектор строк и т.п.

Для доступа к вектору следует подключить стандартный заголовочный файл vector:

#include

Шаблоны

Шаблон template в C++ — конструкция языка программирования, позволяющая задавать семейства функций (шаблоны функций function templates ) и типов (в частности, шаблоны классов class templates ), параметризованные типами или константами (целочисленных типов, указателей или ссылок). Подстановка параметров шаблона выполняется во время компиляции. Результат подстановки — конкретные функции (из шаблонов функций) или типы (из шаблонов классов).

Данное определение проще пояснить на примерах.

Представим, что мы пишем функцию возведения в квадрат (для простоты).

double sqr(double x) < return x * x; >

Выбор типа double в качестве параметра и результата функции достаточно произволен. Что, если мы возводим в квадрат целые числа и лишние преобразования типа и операции с плавающей точкой ни к чему?

int sqr(int x) < return x * x; >

Точно такую же по сути функцию можно написать для любого числового типа.

size_t sqr(size_t x) < return x * x; >

Очевидно, что клонирование одной и той же функции для разных типов — не слишком осмысленная операция. Обычным выходом из подобной ситуации в C++ является определение шаблона функции.

template class Num> Num sqr(Num x) < return x * x; >

Заголовок template < параметры шаблона > вводит шаблон (определение “заготовки” функции или типа находится под заголовком). Собственно шаблон не является функцией или типом до тех пор, пока не заданы фактические значения всех его параметров. Для подстановки параметров шаблона их следует перечислить после имени шаблона через запятую, взяв в “угловые скобки” (знаки “меньше” < и “больше” >), что напоминает вызов функции с параметрами.

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

auto a = sqrint>(10); // Num = int // a имеет тип int и значение 100 auto f = sqrfloat>(2.5f); // Num = float // f имеет тип float и значение 6.25f

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

auto a = sqr(10); // 10 имеет тип int, поэтому Num = int // a имеет тип int и значение 100 auto f = sqr(2.5f); // 2.5f имеет тип float, поэтому Num = float // f имеет тип float и значение 6.25f

Аналогично функциям шаблоны могут принимать параметры по умолчанию.

template class First, class Second = First> struct Pair // Пара значений типов First и Second. < First first; Second second; // Конструктор: First() и Second() -- вызовы конструкторов по умолчанию // для типов First и Second соответственно (определены и для встроенных типов). Pair(const First &first = First(), const Second &second = Second()) : first(first), second(second) /* список инициализации: вызов конструкторов копирования для обоих полей */ <> >;

// Пара чисел с плавающей точкой. Pairdouble> p2(1, 2); // First = double, Second = First = double assert(p2.first == 1. && p2.second == 2.); // Пара "целое, строка". Pair ids; // First = size_t, Second = string; ids.first = 23; ids.second = "23 is the new 42";

Кроме шаблонов функций и классов C++ (начиная с C++11) предоставляет возможность объявлять шаблоны синонимов типов, т.е. записать короткое имя для типа-шаблона с возможностью указать нужные параметры.

template class T> using Id_block = Pair; // Теперь Id_block -- то же, что и Pair для любого T.

Помимо возможности вводить сокращения для сложных шаблонных конструкций, шаблоны синонимов типов позволяют задавать нечто, напоминающее функции, но вычисляющее типы (“метафункции”). Строго говоря, для этого требуется использование других шаблонов, в то время как шаблон синонима типа вводит удобный интерфейс, но если использовать уже готовые конструкции (например, из Стандартной библиотеки уровня C++14), то может сложиться впечатление, что мы пишем что-то вроде функции, параметрами которой являются параметры шаблона, а значением — описание типа, стоящее справа от = .

#include #include // C++14, conditional_t, is_same using namespace std; // Выбор встроенного целочисленного типа, имеющего ширину, // не менее Bits бит, или void, если подходящего типа нет. template unsigned Bits> using Uint = conditional_t<(Bits <= 8), uint8_t, conditional_t<(Bits <= 16), uint16_t, conditional_t<(Bits <= 32), uint32_t, conditional_t<(Bits <= 64), uint64_t, void>>>>; // Проверка условия, выполняемая во время компиляции. static_assert(is_same>, uint32_t>::value, "Uint is flawed!");

Операции с вектором

Создание объекта вектора

Ниже приведены примеры использования некоторых конструкторов std::vector на примере вектора целых чисел.

vectorint> ve; // пустой вектор assert(ve.empty()); vectorint> vn(10); // вектор размера 10 // vn создаёт объекты со значением, возвращаемым конструктором без параметров, // для встроенных типов чисел это 0 assert(!vn.empty()); assert(vn.size() == 10); assert(vn[0] == 0); vectorint> vi(10, 42); // вектор из 10 значений, равных 42 // в качестве второго параметра можно указать конкретное значение // создаваемых объектов assert(vi.size() == 10); assert(vi[0] == 42); int arr[] < 1, 2, 3, 4, 5 >; vectorint> va(arr + 1, arr + 4); // копия диапазона массива // va содержит 3 элемента: 2, 3, 4 assert(va.size() == 3); assert(va[0] == arr[1] && va[1] == arr[2] && va[2] == arr[3]); // Наконец, вектор можно создать из конкретного набора значений, // используя фигурные скобки вместо круглых (C++11). vectorint> vl < 1, 2, 3, 4 >; // можно также ставить "=": vl = < . assert(vl.size() == 4); assert(vl.front() == 1 && vl.back() == 4);

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

// Используем последний конструктор из примера выше. vectorint> vl < 1, 2, 3, 4 >; // Повторно используем тот же конструктор // для создания временного объекта с заданным содержимым. // Обратите внимание -- необходимо указывать тип элемента вектора (здесь int). assert(( vl == vectorint> < 1, 2, 3, 4 > )); assert(( vl != vectorint> < 2, 3, 4 > ));

Обращение к элементам вектора

Вектор представляет собой массив, размещённый в динамической памяти, все элементы которого идут подряд от младших адресов к старшим, точно так же как и в обычном массиве (требование стандарта C++11). Но в отличие от встроенных массивов, вектор “знает” свою длину. Кроме того, вектор может быть пустым (размер 0).

vectorint> vn(100); // сто нулей // Проверить вектор на пустоту -- функция empty. assert(!vn.empty()); // Узнать размер вектора -- функция size. assert(vn.size() == 100); // Получить указатель на хранилище элементов -- функция data. assert(vn.data() == &vn[0]); assert(&vn[99] - vn.data() == 99);

К элементам вектора можно обращаться по числовым индексам с помощью оператора [] . Как и в обычном массиве, первый элемент имеет индекс 0, последний — (размер вектора – 1). Кроме того, для обращения к первому и последнему элементам определены специальные функции front и back . Это сделано для совместимости с контейнерами, не позволяющими обращаться к элементам по индексам, но позволяющими обращаться к первому и последнему элементам особо (например, таким является двусвязный список std::list).

// Обратиться к первому элементу (индекс 0) -- функция front. assert(&vn.front() == &vn[0]); // Обратиться к последнему элементу (индекс size() - 1) -- функция back. assert(&vn.back() == &vn[vn.size() - 1]);

Оператор [] по умолчанию не выполняет проверку допустимости значения индекса. Попытка обратиться к несуществующему элементу ведёт к неопределённому поведению. Вместо [] можно использовать функцию at , бросающую исключение в случае неверного индекса.

assert(&vn.at(10) == &vn[10]); // А здесь будет ошибка -- исключение, но не UB. vn.at(200) = 1000;

Если нет необходимости в прямом использовании индекса в процессе перебора всех элементов вектора, то для осуществления этого перебора можно воспользоваться циклом for(:):

vectorchar> word < 'h', 'e', 'l', 'l', 'o', '!' >; for (char letter: word) cout


Следующий пример — функция, которая вычисляет сумму элементов произвольного вектора.
template class T> T sum(const std::vector &xs) < T s = T(); // ноль или, например, пустая строка (если T = string) for (auto &x: xs) s += x; return s; >
Вставка и удаление элементов вектора
Вектор предоставляет возможность вставки и удаления элементов в любой позиции. Впрочем, следует помнить, что вставка и удаление элементов не с конца вектора обязательно влечёт перемещение его “хвоста” в памяти (так как все элементы вектора идут в памяти подряд как в обычном массиве), что может быть времязатратной операцией.
vectorint> vi; // пустой вектор assert(vi.empty()); // Добавлять элементы в конец вектора можно функцией push_back. vi.push_back(1); assert(vi.size() == 1 && vi[0] == 1); vi.push_back(2); assert(vi.size() == 2 && vi[1] == 2); vi.push_back(3); assert(( vi == vectorint> < 1, 2, 3 > )); // Функция pop_back, наоборот, удаляет последний элемент. vi.pop_back(); assert(( vi == vectorint> < 1, 2 > )); // Функция clear удаляет все элементы. vi.clear(); assert(vi.empty());
Для вставки/удаления элементов в произвольных позициях предназначены функции insert и erase . Позицию можно получить с помощью функции begin (начало; можно добавить сдвиг ∈ [0, size()]) или end (конец; можно вычесть сдвиг ∈ [0, size()]).
vi = < 1, 2, 3, 4 >; // теперь vi содержит 4 элемента: 1, 2, 3, 4. // Вставить значение на место vi[2] (старый vi[2] переходит в vi[3] и т.д.). vi.insert(vi.begin() + 2, 5); assert(( vi == vectorint> < 1, 2, 5, 3, 4 > )); // Вставить группу значений на vi[vi.size() - 2] == vi[3]. vi.insert(vi.end() - 2, < 6, 7 >); assert(( vi == vectorint> < 1, 2, 5, 6, 7, 3, 4 > )); // Удалим один элемент (vi[1]). vi.erase(vi.begin() + 1); // И ещё один (vi[vi.size() - 2] == vi[4]). vi.erase(vi.end() - 2); assert(( vi == vectorint> < 1, 5, 6, 7, 4 > )); // Можно удалить сразу диапазон элементов. // Например, все, кроме первого и последнего. vi.erase(vi.begin() + 1, vi.end() - 1); assert(( vi == vectorint> < 1, 4 > ));
Использование в качестве позиций смещений относительно результатов неких функцией begin и end вместо обычных индексов является элементом совместимости вектора с другими контейнерами (как правило, не позволяющими адресовать элементы по индексам). Значения, возвращаемые begin и end называются итераторы и ведут себя аналогично указателям (указатели — частный случай итераторов). Каждый контейнер определяет свои типы итераторов и набор определённых на них операций. Для вектора этот набор максимален и допускает арифметику, полностью аналогичную арифметике указателей.
Внешние стандартные функции begin и end , будучи применены к вектору, вернут то же самое, что и использовавшиеся выше функции-члены begin и end соответственно. А будучи применены к статическому массиву, данные функции вернут указатели на первый элемент и мнимый элемент, расположенный сразу за последним. Эти указатели суть итераторы статического массива.
Диапазоны в Стандартной библиотеке C++ всегда задаются как полуинтервалы [b, e). Элемент, на который указывает итератор e, в диапазон уже не включается (и может не существовать).
int arr[] = < 9, 8, 7 >; // Вставить на vi[1] содержимое arr целиком. // Вместо arr мог быть объект класса любого стандартного контейнера. vi.insert(begin(vi) + 1, begin(arr), end(arr)); assert(( vi == vectorint> < 1, 9, 8, 7, 4 > ));
С помощью функции resize можно изменять размер вектора.
// В случае уменьшения лишние элементы удаляются с конца. vi.resize(3); assert(( vi == vectorint> < 1, 9, 8 > )); // В случае увеличения новые элементы добавляются с конца. // Если не указать значение, они инициализируются конструктором по умолчанию. vi.resize(4); assert(( vi == vectorint> < 1, 9, 8, 0 > )); vi.resize(6, 99); assert(( vi == vectorint> < 1, 9, 8, 0, 99, 99 > ));
Если в приведённых выше примерах не всё ясно, то рекомендуется попробовать на основе этих примеров написать простую программу, которая:

Заполняет вектор числами от 0 до некоторого n и затем выводит результат (содержимое вектора) в консоль.
Возводит все элементы вектора в квадрат на месте.
Вставляет в середину вектора десять нулей.
Удаляет из начала вектора min(10, размер вектора/2) элементов.
Обращает порядок элементов вектора и выводит финальный результат в консоль.

Принцип управления хранилищем вектора
Вектор обеспечивает вставку элементов в конец в среднем за O(1)-время, несмотря на тот факт, что периодически приходится выделять новый достаточно большой блок памяти и переносить туда всё содержимое вектора, после чего старый блок памяти освобождается. Это достигается за счёт того, что при выделении нового блока вектор обычно выделяет памяти больше, чем требуется именно в момент увеличения, и часть хранилища остаётся до поры незадействованной. Узнать полный объём текущего хранилища (в элементах) можно с помощью функции capacity (из них реально занято size() позиций).
vectorint> vi; // Посмотрим, как полный объём выделенного хранилища // соотносится с занятым объёмом (размером вектора). for (size_t i = 1; i < 35; ++i) < vi.push_back(i); cout '\t' 
При реальном увеличении хранилища реализации вектора обычно используют простую схему: новый объём = g*старый объём, где g ∈ (1, 2] — константа роста ( grow factor ). Обычно g = 1.5 или g = 2. Впрочем, значения g ≥ 2 могут привести к нежелательному эффекту: невозможности повторно задействовать ранее выделенную и затем освобождённую память. Каждая строчка ниже соответствует одному выделению нового хранилища. Предположим, что доступная память простирается на непрерывном диапазоне адресов, достаточном для размещения 16 элементов.
Легко показать, что в этом случае освобождённое начало диапазона никогда не может быть повторно задействовано в качестве хранилища вектора, поскольку всегда будет не хватать ровно одного элемента: 2 0 + 2 1 + … + 2 n = 2 n+1 – 1. В случае g < 2 иногда будет происходить “возврат”, потому что накопленные освобождённые блоки рано или поздно достигнут требуемого для хранилища объёма. Например, g = 1.5 позволяет в том же примере выделить хранилище объёмом на 1 элемент больше:
Вообще, чем больше g, тем реже будет происходить выделение памяти и копирование элементов. Чем меньше g, тем эффективнее будет использоваться доступное хранилище (будет меньше незанятых элементов).
O(1)-время на вставку элемента в среднем достигается в пределе. Пусть было n перераспределений памяти и, начиная с некоторого i, на перераспределении i выделяется блок размера ⌊g i ⌋, в него копируется полный предыдущий блок, т.е. ⌊g i–1 ⌋ элементов. Итак, после n перераспределений было 1 + max(⌊g⌋, 2) + … + ⌊g n–1 ⌋ ≤ (g n – 1)/(g – 1) + O(n) копирований. Так как всего было добавлено ⌊g n–1 ⌋ + 1 элементов, то в среднем на элемент было осуществлено ((g n – 1)/(g – 1) + O(n)) / (⌊g n–1 ⌋ + 1) копирований, что при g > 1 и n → ∞ даёт 1 в пределе.
Вектор позволяет заранее выделить хранилище нужного объёма, не создавая дополнительных элементов, с помощью функции reserve :
vectorint> vi; vi.reserve(100); assert(vi.size() == 0 && vi.capacity() == 100);
Функция reserve не может уменьшить размер выделенного хранилища. Передавая ей некоторое число, мы просим гарантировать наличие хранилища объёмом не менее указанного числа. Впрочем, если мы экономим память, то можно “подогнать” размер хранилища под реально занятый объём с помощью функции shrink_to_fit :
vi.push_back(100); vi.shrink_to_fit(); assert(vi.size() == 1 && vi.capacity() == 1);
Пример выполнения задания
Функцией clamp(x, p, q) назовём функцию, возвращающую x, если x ∈ [p, q]; p, если x < p; q, если x > q. Требуется написать функцию, принимающую вектор некоторых значений и границы p и q и возвращающую (новый) вектор результатов clamp, применённой к каждому элементу исходного вектора.
Для произвольного типа значений Val, на которых задан порядок, функцию clamp можно определить в виде следующего шаблона:
template class Val> inline Val clamp(Val value, Val min_bound, Val max_bound) < return value
Применить clamp к вектору достаточно просто: создаём вектор нужного размера и записываем в него результаты clamp поэлементно. В конце возвращаем из функции новый вектор.
template class Val> vector clamped(const vector &values, Val min_bound, Val max_bound) < vectorclv(values.size()); for (size_t i = 0, sz = values.size(); i < sz; ++i) clv[i] = clamp(values[i], min_bound, max_bound); return clv; >
Тест в данном примере написан на основе чтения чисел в вектор из потока. В заданиях так делать необязательно. Цель примера — показать возможную реализацию чтения вектора заранее неизвестного размера из потока ввода.
template class Val> vector read_vector(istream &in) < vectorvalues; for (Val val; in >> val;) values.push_back(val); in.clear(ios::failbit); values.shrink_to_fit(); return values; >
Чтобы использовать функцию read_vector, необходимо явно указывать тип Val (например read_vector(cin) ), так как компилятору неоткуда узнать, значения какого типа мы планируем прочитать из потока ввода. Собственно тест:
int test_clamped() < stringstream test; test "10 4 -5. 2 51 2222.022 4 1.2 25 7 8.5 -"; auto values = read_vectorfloat>(test); if (clamped(values, 0.f, 100.f) != vectorfloat> < 10.f, 4.f, 0.f, 2.f, 51.f, 100.f, 4.f, 1.2f, 25.f, 7.f, 8.5f >) return 1; if (clamped(values, 3.f, 8.f) != vectorfloat> < 8.f, 4.f, 3.f, 3.f, 8.f, 8.f, 4.f, 3.f, 8.f, 7.f, 8.f >) return 2; return 0; >
Варианты
Обозначим исходный вектор буквой a, результирующий вектор — буквой b.


Похожие публикации:

Nfc в телефоне что это
Как очистить кэш в лайтруме на компьютере
Как сделать крестики нолики в 1с
Как ссылку превратить в текст