Как проверить что вектор пустой c
Перейти к содержимому

Как проверить что вектор пустой c

  • автор:

Как проверить что вектор пустой c

Чаще всего требуется использовать массивы неопределенного размера. В таких случаях будет затратно использовать обычный массив, и выделять фиксированный объем памяти для него. Именно поэтому для таких целей подойдет вектор (vector).

Для использования векторов необходимо включить соответствующий заголовок и объявление using.

#include using std::vector; 

Вектор является контейнером, поскольку он содержит другие объекты. При его использовании необходимо указать тип создаваемого значения. Ниже показаны примеры создания трех пустых векторов:

vector vec1; //vec1 содержит объекты типа int vector vec2; //vec2 содержит объекты типа string vector vec3; //вектор, содержащий другие вектора 

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

Способы инициализации векторов
vector v1 Вектор, содержащий объекты типа T
vector v2(v1) Вектор v2 — копия всех элементов вектора v1
vector v2 = v1 Эквивалент v2(v1), v2 — копия элементов вектора v1
vector v3(n, val) Вектор v3 содержит n элементов со значением val
vector v4(n) Вектор v4 содержит n элементов типа T, инициализированного значением по умолчанию
vector v5

Вектор v5 содержит столько элементов, сколько предоставлено инициализаторов
vector v5 =

Эквивалент v5

Все элементы вектора должны иметь один тип создаваемых значений.

Следует различать инициализацию с разными скобками () и <> .

В случае использования int

vector v1(10); //v1 имеет десять элементов со значением 0 vector v2; //v2 имеет один элемент со значением 10 vector v3(10, 1); //v3 имеет 10 элементов со значением 1 vector v4; //v4 имеет два элемента со значениями 10 и 1 

В случае использования string

vector v5; //v5 имеет 1 элемент (списочная инициализация) vector v6("hi"); //ошибка, нельзя создать вектор из строкового литерала vector v7; //v7 имеет 10 элементов со значением по умолчанию vector v8(10, "hi"); //v8 имеет 10 элементов со значением "hi" 

Если необходимо создать вектор со значениями от 0 до 9, то можно легко использовать списочную инициализацию. Но что же делать, если необходимы элементы от 0 до 99 или от 0 до 999? Списочная инициализация будет слишком громоздкой. В таком случае необходимо создать пустой вектор и использовать функцию push_back() , чтобы добавлять элементы во время выполнения.

Функция push_back() вставляет переданное ей значение в вектор как новый последний элемент. Например:

vector vec1; //пустой вектор for (int i = 0; i < 100; i++) vec1.push_back(i) //по завершении цикла vec1 имеет 100 элементов со значениями от 0 до 99 

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

string word; vector text; //пустой вектор while (cin >> word) < text.push_back(word); //добавить word в text >

Как проверить что вектор пустой c

Вектор представляет контейнер, который содержит коллекцию объектов одного типа. Для работы с векторами необходимо включить заголовок:

#include

Определим простейший вектор:

std::vector numbers;

В угловых скобках указывается тип, объекты которого будут храниться в векторе. То есть вектор numbers хранит объекты типа int. Однако такой вектор пуст. Он не содержит никаких элементов.

Но мы можем инициализировать вектор одним из следующих способов:

std::vector v1; // пустой вектор std::vector v2(v1); // вектор v2 - копия вектора v1 std::vector v3 = v1; // вектор v3 - копия вектора v1 std::vector v4(5); // вектор v4 состоит из 5 чисел, каждое число равно 0 std::vector v5(5, 2); // вектор v5 состоит из 5 чисел, каждое число равно 2 std::vector v6; // вектор v6 состоит из чисел 1, 2, 4, 5 std::vector v7 = ; // вектор v7 состоит из чисел 1, 2, 3, 5

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

std::vector v1(5); // вектор состоит из 5 чисел, каждое число в векторе равно 0 std::vector v2; // вектор состоит из одного числа, которое равно 5 std::vector v3(5, 2); // вектор состоит из 5 чисел, каждое число равно 2 std::vector v4; // вектор состоит из двух чисел 5 и 2

При этом можно хранить в векторе элементы только одного типа, который указан в угловых скобках. Значения других типов в вектор сохранить нельзя, как например, в следующем случае:

std::vector v;

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

Для обращения к элементам вектора можно использовать разные способы:

  • [index] : получение элемента по индексу (также как и в массивах), индексация начинается с нуля
  • at(index) : функция возращает элемент по индексу
  • front() : возвращает первый элемент
  • back() : возвращает последний элемент

Выполним перебор вектора и получим некоторые его элементы:

#include #include int main() < std::vectornumbers ; int first = numbers.front(); // 1 int last = numbers.back(); // 5 int second = numbers[1]; // 2 std::cout << "first: " << first << std::endl; std::cout << "second: " << second << std::endl; std::cout << "last: " << last << std::endl; numbers[0] = 6; // изменяем значение for(int n : numbers) std::cout << n << "\t"; // 6 2 3 4 5 std::cout

При этом следует учитывать, что индексация не добавляет элементов. Например, если вектор содержит 5 элементов, то мы не можем обратиться к шестому элементу:

std::vector numbers ; numbers[5] = 9;

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

Чтобы избежать подобных ситуаций, можно использовать функцию at() , которая хотя также возвращает элемент по индексу, но при попытке обращения по недопустимому индексу будет генерировать исключение out_of_range :

#include #include #include int main() < std::vectornumbers < 1, 2, 3, 4, 5>; try < int n = numbers.at(8); >catch (std::out_of_range e) < std::cout >

Checking whether a vector is empty

Suppose I have a std::vector say Vector Now after performing some operations on the vector(either insertion or deletion) I want to check if the vector is empty and on the basis of that I want to perform some operations. Which approach is better Approach 1

if (Vector.size() == 0) < /* operations */ >

Approach 2

if (Vector.empty()) < /* operations */ >

Which is a better approach, 1 or 2 ?
222k 46 46 gold badges 258 258 silver badges 444 444 bronze badges
asked Oct 5, 2010 at 11:41
Prasoon Saurav Prasoon Saurav
91.8k 50 50 gold badges 240 240 silver badges 345 345 bronze badges
Mar 16, 2015 at 13:55

8 Answers 8

v.size() == 0 says "I'm comparing the size", but does so to check whether the container empty. There's a small algorithm to digest (very small, as it only consists of a comparison) before you know what it does.
OTOH, v.empty() does exactly what it says: it checks whether v is empty.
Due to this, I clearly prefer #2, as it does what it says. That's why empty() was invented, after all.

But there's also an algorithmic reason to prefer empty() : If someone later changes std::vector into a std::list , v.size() might have O(n). (In C++ 03 it's guaranteed to be O(1) for std::vector , but not for std::list . According to James' comment to Prasoon's answer it will be O(1) for all containers in C++1x.)

1 1 1 silver badge
answered Oct 5, 2010 at 11:47
222k 46 46 gold badges 258 258 silver badges 444 444 bronze badges

In reply to your question/comment below, Howard Hinnant wrote up a whitepaper discussing the tradeoffs for list (it's actually a splice()-speed vs. size()-speed tradeoff). I can't seem to get to the whitepaper right now, but Michael Burr summarized it..

Oct 5, 2010 at 11:57

@Donotalo: it's the new C++ standard that is going to be approved soon. For some time it was referred as "C++0x" (where 0x meant "in some year in range [2000, 2010)), but, since they didn't manage to get it approved before 2010, it's now also known as "C++1x". Some people still call it C++0x because it was called in that way or because they say that that "x" is to be intended as a hexadecimal digit.

Oct 5, 2010 at 12:57

@Donotalo: it's just that the original rationale for the name C++0x is no longer valid, so while most of us prefer to stick with the name C++0x to avoid confusion, a few people think the upcoming standard's nickname should be changed to C++1x even if it means no one knows what we're talking about. 😉 To add some bonus confusion, C++0x, whatever we call it, is unlikely to be the only revision to the standard this decade. So if we start calling it C++1x, it might end up clashing with another C++1x, denoting the next standard revision.

Oct 5, 2010 at 14:46

As far as I'm concerned, the bottom line is this: C++0x is not an official name. It is a placeholder, a nickname used to identify the draft that is not yet standardized. As such it doesn't need to be updated. They could call it C++1643 and it'd work just as well. So I'm going to keep calling it C++0x until the day it is standardized and receives an official name.

Oct 5, 2010 at 14:47

@jalf: That x is a placeholder for a not yet fixed digit. If there should be another TR before 2020 (per ISO rules, a new version of the standard must not be released in less than ten years), the x in the standard we're now waiting for is long settled and there's a digit found for it. (Also, by your logic, C++0x should clash with C++03.)

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

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

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

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

Введение

Для организации хранения наборов объектов Стандартная библиотека 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 > ));

Если в приведённых выше примерах не всё ясно, то рекомендуется попробовать на основе этих примеров написать простую программу, которая:

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

Принцип управления хранилищем вектора

Вектор обеспечивает вставку элементов в конец в среднем за 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.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *