Последовательности типа vector
Последовательности типа vector
Для их использования необходимо подключить файл заголовков <vector> и сделать доступным (видимым) стандартное (std) пространство имен:
#include <vector> using namespace std;
Обратите внимание на отсутствие расширения .h в директиве подключения файла заголовков. Дело в том, что STL используется на множестве различных платформ с применением разных компиляторов. Файлы заголовков в разных условиях имеют разные расширения. Они могут иметь расширение Н, НРР или НХХ. Для того чтобы одинаково запутать всех разработчиков, было решено вовсе не использовать расширение для файлов заголовков библиотеки STL. Пространство имен std позволяет избежать конфликта имен. Если вы назовете какой-то свой класс тем же именем, что и класс из STL (например, string), то обращение вида std: : string однозначно определит принадлежность класса стандартной библиотеке. Директива using позволяет не указывать (многократно) операцию разрешения области видимости std: :, поэтому можно расслабиться и не писать std: : string, a писать просто — string.
Вектор является шаблоном класса, который настраивается с помощью двух параметров:
vector<class T, allocator<class T> >
Объект, который управляет динамическим выделением и освобождением памяти типа т, называется allocator. Для большинства типов контейнеров он обычно объявляется по умолчанию в конструкторе. Для «хитрых» данных, например требующих памяти в глобальном heap, видимо, можно изобрести индивидуальный распределитель памяти. Но в большинстве случаев работает вариант по умолчанию. Кроме того, с типом vector обычно связаны.4 типа сущностей:
- Pointer — ведет себя как указатель на тип т;
- const pointer — не позволяет изменить данные типа т, на которые он указывает;
- reference — ссылки на данные типа т;
- const reference— не позволяет изменить данные типа т, на которые она ссылается.
Обычно эти сущности являются тем, чем и должны являться, но это не гарантируется. Они могут быть более сложными объектами.
Итак, 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 эта операция была определена в виде метода класса, то алгоритм справится с поставленной задачей. Однако если мы захотим изменить порядок и отсортировать последовательность объектов по возрасту, то нам придется воспользоваться другим отношением. Решить эту задачу можно двумя способами:
- использовать свою собственную функцию-предикат, которая определяет порядок следования объектов;
- использовать конструкцию, называемую функциональным объектом.
Первый способ реализуется путем создания глобальной функции, на вход которой поступают два сравниваемых объекта, а на выходе должен быть результат их сравнения, например типа bool. Второй способ реализуется созданием функционального объекта (function object или functor), являющегося структурой, в которой определена операция operator (). Этот термин, однако, используется для обозначения не только описанного объекта, но и для любого другого, который можно вызвать так, как вызывают функцию. Собственно, кроме описанного случая, роль функционального объекта может выполнять обычная функция и указатель на функцию.
Покажем, как создать предикат. В описание класса Man следует добавить объявление внешней функции в качестве friend-объекта, так как в ее теле будут анализироваться private-данные класса Man. Добавьте в класс Man такое описание:
//======== Предикат, задающий отношение порядка
friend bool LessAge (Mans a, Man& b);
Затем вставьте коды этой функции после объявления класса, но до тела функции main:
bool LessAge (Man& a, Man& b)
{
//======== Сравниваем по возрасту
return a.m_Age < b.m_Age;
}
Теперь можно создать контейнер объектов класса Man и убедиться в возможности его сортировки двумя способами. В момент создания контейнер может быть инициализирован элементами обычного массива. Ниже мы показываем, как это сделать:
void main ()
{
//======== Массив объектов класса Man
Man ar[] =
{
Man("Mary Poppins",36),
Man("Joe Doe",30),
Man("Joy Amore",18),
Man("Zoran Todorovitch",27)
};
uint size = sizeof(ar)/sizeof(Man);
//======== Создаем контейнер на основе массива
vector<Man> men(ar, ar+size); pr(men,"Man Vector");
//======== Реверсируем обычный массив
reverse(ar, ar+size);
cout « "\n\tAfter reversing the array\n\n";
for (uint i=0; i<size; i++)
cout « i+1 « ". " « ar[i] « '\n';
//======== Сортиуем по умолчанию
sort (men.begin (), men.endO);
pr(men,"After default sort");
//======== Используем предикат
sort (men .begin () , men.endO, LessAge);
pr(men,"After predicate LessAge sort");
cout « "\n\n";
}
Алгоритм переворота последовательности (reverse) может работать как с контейнером, так и с обычным массивом. Для успешной работы ему надо задать диапазон адресов (range). Обратите внимание на то, что в качестве конца последовательности этому алгоритму, как и многим другим в STL, надо подать во втором параметре адрес ar+size, выходящий за пределы массива. Как объяснить тот факт, что шаблон функции reverse, требуя в качестве параметров переменные типа iterator, тем не менее работает, когда ему подают обычный указатель типа Man*? В документации вы можете найти такое объяснение. Указатель — это итератор, но итератор — это не указатель. Итератор — это обобщение (generalization) указателя.
Результат работы программы выглядит так:
Man Vector # Sequence:
1. Mary Poppins, Age: 36
2. Joe Doe, Age: 30
3. Joy Amore, Age: 18
4. Zoran Todorovitch, Age: 27
After reversing the array
1. Zoran Todorovitch, Age: 27
2. Joy Amore, Age: 18
3. Joe Doe, Age: 30
4. Mary Poppins, Age: 36
After default sort # Sequence:
1. Joe Doe, Age: 30
2. Joy Amore, Age: 18
3. Mary Poppins, Age: 36 /
4. Zoran Todorovitch, Age: 27
After predicate LessAge sort # Sequence:
1. Joy Amore, Age: 18
2. Zoran Todorovitch, Age: 27
3. Joe Doe, Age: 30
4. Mary Poppins, Age: 36
Здесь мы убрали сообщения, которые выводит деструктор класса Man. Они носят чисто учебный характер. В частности, они позволяют обозначить те моменты из жизни объектов класса Man, когда они уничтожаются, то есть когда система вызывает для них деструктор.
Сейчас мы намерены создать функциональный объект и использовать его для выбора режима сортировки по имени или по возрасту. Текущий выбор удобно хранить в static-переменной класса Man. Такие переменные, как вы знаете, являются общими для всех объектов класса. Изменяя их значение, можно управлять общими установками, касающимися всех объектов класса. Мы будем управлять текущим режимом сортировки. Для удобства чтения кода введем глобальное определение типа SORTBY - перечисление режимов сортировки:
enum SORTBY { NAME, AGE }; // Режимы сортировки
Декларацию static-переменной следует вставить в public-секцию класса Man:
static SORTBY m_Sort; // Текущий режим сортировки
Определение static-переменной, согласно законам ООП, должно быть глобальным:
//======= Определение и инициализация
SORTBY Man::m_Sort = NAME;
Сам функциональный объект должен быть объявлен как внешняя глобальная friend-конструкция. Вставьте следующее объявление внутрь класса Man:
//======= Функциональный объект имеет доступ к данным
friend struct ManLess;
Затем объявите сам функциональный объект, который, надо признать, имеет несколько непривычный вид:
//======== Функциональный объект
struct ManLess
{
bool operator()(Man& a, Man& b)
{
return a.m_Sort==NAME ? (a.m_Name < b.m_Name)
: (a.m_Age < b.m_Age);
}
};
Как вы видите, он имеет вид структуры (возможен и класс), в которой определена единственная операция operator (). В нем мы анализируем текущее значение флага сортировки и в зависимости от него возвращаем результат сравнения двух объектов, поступивших в качестве параметров, по тому или иному полю. Использование функционального объекта иллюстрируется следующим кодом, который вы можете вставить в конец существующей функции main:
//========= Используем функциональный объект
Man::m_Sort = NAME;
//========= Сортируем по имени
sort (men .begin (), men.end(), ManLess ());
pr(men,"After function object name sort");
Man::m_Sort = AGE;
//========= Сортируем по возрасту
sort (men. begin (), men.end(), ManLess ());
pr(men,"After function object age sort");
Аналогично предикату greater<Type>, который мы уже использовали, в STL определен предикат less<Type>, который обеспечивает упорядочивание контейнера, задаваемое операцией operator< (). Но, если вы вставите в функцию main такой код:
//========= Используем стандартный предикат
sort(men.begin(), men.end(),less<Man>() ) ;
pr(men,"After less<Man> sort");
то получите сообщение об ошибке, так как он будет искать реализацию operator< () в виде внешней функции с двумя сравниваемыми параметрами. Напомню, что мы уже реализовали эту операцию, но в виде метода класса с одним параметром. Для решения проблемы вы можете, не убирая старой версии, вставить новую. Декларируйте в классе Man внешнюю friend-функцию:
//========= Нужна для предиката less<Man>()
friend bool operator< (const Man& a, const Man& b);
Затем дайте внешнее тело этой функции. Отношение порядка здесь намеренно изменено по сравнению с предыдущей реализацией operators (). Как оказалось, обе версии будут работать в различных ситуациях. Первая — при сортировке по умолчанию, а вторая — при сортировке предикатом less<Man> .
bool operator<(const Man& a, const Man& b)
{
//======== Сравниваем по возрасту
return a.m_Age < b.m_Age;
}
Проверьте результат, запустив приложение. Проследите, чтобы в main был при этом код с вызовом алгоритма сортировки с тремя Параметрами:
sort(men.begin (), men.end(),less<Man>());
Здесь же уместно добавить, что в STL есть шаблоны, которые называются negators (отрицатели). Шаблон not2, например, позволяет инвертировать результат бинарной операции. Вставьте в конец функции main следующий фрагмент:
//========= Используем отрицатель бинарной операции
sort(men.begin (), men.endf), not2 (less<Man>()));
pr(men,"After not2(less<Man>) sort");
и убедитесь в том, что последовательность отсортирована теперь по убыванию возраста.
