Последовательности типа vector

Обычно эти сущности являются тем, чем и должны являться, но это не гарантируется. Они могут быть более сложными объектами.

Итак, vector является аналогом обычного массива в языке С, за исключением того, что он может автоматически изменять память по мере надобности.
Доступ к данным обеспечивается с помощью операции выбора [ ]. Вставка новых элементов эффективна только в конец контейнера (push_back). Удаление — тоже. Данные операции в начале или середине влекут сдвиги всего массива данных, что резко снижает эффективность работы контейнера. Такие операции называются линейными, имея в виду тот факт, что время их выполнения линейно зависит от количества элементов в контейнере. Вставка или удаление в конце называются константными операциями, так как время их выполнения является константой для данной реализации и не зависит от количества элементов. Вот простая программа, иллюстрирующая использование вектора. Так как в приложениях консольного типа обычно возникают проблемы с русификацией, то для вывода текста мы используем английский язык:

#include <vector>



#include <algorithm>

#include <iostream> using namespace std;

//======= Вводим тип для сокращения текста (места)

typedef unsigned int uint;

void main ()

{

//======== Вектор целых

vector<int> v(4);

cout « "\nlnt Vector:\n";

for (uint i=0; i<v.size(); i++)

{

v[i] = rand()%10 + 1;

cout « v[i] « "; ";

}

//======= Сортировка по умолчанию sort (v.begin (), v.end());

cout « "\n\nAfter default sort\n";

for (i=0; i<v.size(); i++) cout « v[i] « "; ";

//======== Удаление элементов

v.erase(v.begin());

cout « "\n\nAfter first element erasure\n";

for (i=0; i<v.size(); i++) cout « v[i] « "; ";

v. erase (v. end ()-2, v.endO);

cout « "\n\nAfter last 2 elements erasure\n";

for (i=0; i<v.size(); i++)

cout « v[i] « "; ";

//======== Изменение размеров

int size = 2; v.resize(size);

cout « "\n\nAfter resize, the new size: " « v.size()

« endl; for (i=0; i<v.size(); i++)

cout « v[i] « "; ";

v.resize(6,-1);

cout « "\n\nAfter resize, the new size: " « v.size()« endl;

for (i=0; i<v.size(); i++)

cout « v[i] « "; ";



//======== Статистика .

cout « "\n\nVector's maximum size: " « v.max_size() « "XnVector's capacity: " « v.capacity() « endl

//======== Резервирование

v.reserve (100);

cout « "\ nAfter reserving storage for 100 elements:\n"

« "Size: " « v.sizeO « endl :

« "Maximum size: " « v.max_size() « endl

« "Capacity: " « v.capacity() « endl;

v.resize(2000);

cout « "\nAfter resizing storage to 2000 elements:\n"

« "Size: " « v.size() « end1

« "Maximum size: " « v.max_size() « end1

« "Capacity: " « v.capacity() « endl; cout « "\n\n";

}

Для того чтобы лучше уяснить смысл и различие методов size, resize, max_size и capacity, мы несколько раз повторяем вызовы этих методов. Если вы читаете книгу вдалеке от компьютера, то вам, возможно, будет интересно узнать, что программа выведет в окно консольного приложения:

Int Vector:

2; 8; 5; 1;

After default sort

1; 2; 5; 8;

After first element erasure

2; 5; 8;

After last 2 elements erasure 2;

After resize, the new size: 2,

Vector capacity: 4 2; 0 ;

After resize, the new size:

6 2; 0; -1; -1; -1; -1;

Vector's maximum size: 1073741823

Vector's capacity: 6 After reserving storage for 100 elements:

Vector's size: 6

Vector's maximum size: 1073741823

Vector's capacity: 100

After resizing storage to 2000 elements:

Vector's size: 2000

Vector's maximum size: 1073741823

Vector's capacity: 2000

Шаблон функции вывода содержимого контейнера

Демонстрация функционирования контейнеров требует часто выводить их содержимое, поэтому будет целесообразно написать шаблон функции, которая выводит содержимое контейнера любого типа. Первый параметр (т& v) функции рг () задает тип контейнера. Он же является параметром шаблона. Второй параметр (string s) задает строку текста (заголовок), который будет выведен в начале блока данных контейнера:

//===== Шаблон функции для вывода с помощью итератора



template <class T> void pr(T& v, string s)

{

cout«"\n\n\t"«s«" # Sequence: \n";

//====== Итератор для любого контейнера

Т::iterator p;

int i;

for (p = v.begin(), i=0; p != v.end(); p++, i++)

cout « endl « i + 1 «". "« *p; cout « '\n';

}

Для пробега по всем элементам любого контейнера используется обобщенный, или абстрактный, указатель, который объявлен как т:: iterator. С помощью итератора, так же как и с помощью обычного указателя, можно получить доступ к элементу, используя операции *, ->. К нему также применима операция ++ — переход к следующему элементу последовательности, но в отличие от указателя с итератором не связана адресная арифметика. Вы не можете сказать, что значение итератора изменится на 4 байта при переходе к следующему элементу контейнера целых чисел, хотя для некоторых типов контейнеров это так и будет. Заметьте, что операция ++ в применении к итератору позволяет перейти к следующему элементу как вектора — элементы расположены в памяти подряд, так и списка — элементы расположены в памяти не подряд. Поэтому итератор — это более сложный механизм доступа к данным, чем простой указатель. Полезно представить итератор в виде рабочего, приставленного к контейнеру и призванного перебирать его элементы.

Возможное присвоение p = v. end (); не означает, что итератор устанавливается на последний элемент последовательности. Вы помните, какую роль играет ноль для обычного указателя при работе с динамическим списком? Примерно такую же роль для итератора выполняет значение v. end () — конец последовательности. Его можно представить в виде итератора, указывающего на воображаемый элемент, следующий за последним элементом контейнера (past-the-end value). Однако инициализатор p = v.begin (); устанавливает итератор в точности на первый элемент последовательности.

Вектор объектов класса

Следующий фрагмент демонстрирует работу с вектором строк типа string. Теперь в контейнере будут храниться объекты класса string, который также является составной частью STL.


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

#include <vector>

#include <string>

#include <algorithm> // Для sort и distance

#include <functional> // Для greater<string>() tinclude <iostream>

using namespace std;

void main ()

{

//========= Вектор строк текста

vector<string> v;

v.push_back("pine apple");

v.push_back("grape") ;

v.push_back("kiwi fruit");

v.push_back("peach") ;

v.push_back("pear") ;

v.push_back("apple") ;

v.push_back("banana") ;

//========= Вызываем наш шаблон вывода

pr(v, "String vector");

sort (v.begin () , v.end());

pr(v, "After sort"); '

//========= Изменяем порядок сортировки, на обратный

//========= тому, который принят по умолчанию

sort(v.begin(), v.end(), greater<string>()) ;

pr(v, "After predicate sort");

cout « "\nDistance from the 1st element to the end: ";

vector<string>::iterator p = v.begin ();

vector<string>::difference_type d;

d = distance(p, v.end());

//========= Отметьте, что end() возвращает адрес

//========= за концом последовательности

cout « d « endl;

cout « "\n\nAdvance to the half of that distanceXn";

advance (p, d/2);

cout « "Now current element is: " « *p « endl;

d = distance(v.begin (), p);

cout « "\nThe distance from the beginning: " « d « endl;

d = distance(p, v.begin ());

cout « "\nThe distance to the beginning: "

« d « endl;

}

Здесь мы демонстрируем, как можно с помощью бинарного предиката greater <Туре> изменить порядок сортировки элементов последовательности. Предикатом называется функция, область значений которой есть множество { false, true } или { 0, 1 }.


В нашем случае этот предикат пользуется результатом операции operator > (), определенной в классе string. Кроме того, мы показываем, как можно пользоваться шаблоном функций distance, который позволяет определить количество приращений типа dif ference_type между двумя позициями, адресуемыми итераторами. Другой шаблон функций — advance позволяет продвинуться вдоль контейнера на число позиций, задаваемое параметром, который может быть и отрицательным.

Предикаты и функциональные объекты

Предикатом, как определено в курсе математической логики, называется любая функция многих переменных, областью значений которой является множество {false, true} или {0, 1}. Покажем, как можно отсортировать по имени контейнер объектов класса Man, который мы определили в этом уроке выше. Алгоритм sort по умолчанию использует для сортировки бинарное отношение, задаваемое операцией operator< (). Так как в классе Man эта операция была определена в виде метода класса, то алгоритм справится с поставленной задачей. Однако если мы захотим изменить порядок и отсортировать последовательность объектов по возрасту, то нам придется воспользоваться другим отношением. Решить эту задачу можно двумя способами: