Бегун.Рекомендую - партнеру
Здесь может быть ваша реклама
|

 Глава 11. Библиотека стандартных шаблонов

Глава 11. Библиотека стандартных шаблонов

До сравнительно недавнего времени в языке C++ не было других стандартных средств программирования, кроме старой библиотеки стандартных функций С, которая совершенно не использовала мощных нововведений, таких, как классы, шаблоны, inline-функции и исключения. Библиотека стандартных шаблонов (Standard Template Library), разработанная в HP Laboratories, явилась в свое время весьма удачным шагом в решении проблемы стандартной библиотеки ANSI C++, в которую она теперь и входит.

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

Введение в библиотеку стандартных шаблонов

Состав библиотеки стандартных шаблонов можно разбить на две категории: алгоритмы и структуры данных. Из последних можно выделить стандартные строки, поскольку они реализованы совершенно независимо от остальных элементов библиотеки. Строки мы будем обсуждать отдельно и подробнее, чем все остальное.

Состав библиотеки

Если более конкретно рассмотреть состав библиотеки стандартных шаблонов (исключив пока из рассмотрения строки), то в ней можно выделить следующие компоненты:

  • Итераторы, которые в некоторых отношениях подобны указателям. Это фундаментальное понятие STL; итераторы обеспечивают доступ к элементам данных контейнеров.
  • Контейнеры представляют собой структуры или наборы данных, такие, как списки, векторы, очереди, реализованные как шаблоны классов.
  • Уже упомянутые алгоритмы, представляющие собой шаблоны функций, оперирующих на данных контейнеров. Например, алгоритм может сортировать объекты, являющиеся элементами вектора или списка. Функции эти не обладают специфическими “знаниями” о типах и структурах, на которых они действуют.

Примечание

Последнее, кстати, означает, что STL, если рассматривать ее как целое, не является объектно-ориентированной, поскольку данные и методы (т. е. алгоритмы) между собой не связаны. Организовать на основе библиотеки адекватные задаче классы и является обязанностью программиста, если он хочет написать действительно объектно-ориентированную, иерархически организованную программу.

Вместе с STL в C++Builder предусмотрены различные дополнительные средства, например, класс комплексных чисел и средства обработки ошибок.

Заголовочные файлы

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

#include <algorithm>

Компилятор автоматически укорачивает имя до восьми символов, добавляет .h и читает файл algorith.h из каталога $(BCB)Include. На уровне исходного кода программы C++ получаются более мобильными, не привязанными к конкретной системе именования файлов.

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

Таблица 10.1. Контейнерные классы STL

Директива #include

Класс контейнера

<bitset>

bitset — множества как битовые наборы.

<deque>

deque — двусвязные очереди; имя является сокращением от “double-end queue”.

<iist>

list — списки.

<map>

map, multimap — карты; это структуры, подобные массиву, но в которых роль “индекса” могут играть не только целые числа, но любые упорядоченные типы.

<queue>

queue, priority queue — очереди, т. е. структуры, организованные по принципу “первым вошел, первым вышел”.

<set>

set, multiset — множества.

<stack>

stack — стеки, организованные по принципу “последним вошел, первым вышел”.

<vector>

vector, vector<bool> — векторы, во многом подобные обычным массивам.

 

Итераторы

Итераторы, как было замечено выше, являются центральным механизмом, обеспечивающим работу с данными контейнеров. Они являются аналогом указателей и делают возможным циклический перебор всех элементов контейнера. Существуют разные виды итераторов, поскольку различные алгоритмы по-разному обращаются к данным. Каждый класс контейнера может порождать итераторы, необходимые для работы адекватных ему алгоритмов.

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

Примечание

Следует упомянуть, что при вызове различных алгоритмов для диапазона, заданного парой итераторов, второй из них соответствует не последнему значению итератора в диапазоне, а следующему за ним.

Основными операциями над итераторами- являются, как и в случае указателей, разыменование и инкремент. Если итератор i после конечного ряда приращений может стать равным итератору j, то говорят, что итератор j достижим из i. Если к итератору, достигшему верхней границы диапазона, применить операцию инкремента, он примет запредельное значение.

Сделав такие предварительные замечания, мы перейдем теперь к конкретному изучению итераторов библиотеки стандартных шаблонов.

Типы итераторов

Существует пять основных форм итераторов:

  • Входной итератор обеспечивает доступ к контейнеру только для чтения в поступательном направлении (т. е. к итератору применима операция инкремента).
  • Выходной итератор обеспечивает доступ только для записи, также в поступательном направлении.
  • Поступательный итератор предоставляет доступ для чтения-записи в поступательном направлении.
  • Двунаправленный итератор допускает чтение и запись как в поступательном, так и реверсивном направлениях (к нему применимы как инкремент, так и декремент).
  • Итератор произвольного доступа предоставляет прямой доступ к данным для чтения-записи.

Итераторы, стоящие в этом списке ниже, выводятся из тех, что находятся выше. Это едва ли не единственный пример классовой иерархии в 8TL.

В следующей таблице показано, какими контейнерами стандартной библиотеки генерируются те ли иные итераторы.

Таблица 10.2. Итераторы, генерируемые стандартной библиотекой

Форма итератора

Контейнеры

входной итератор

istream iterator

выходной итератор

ostream iterator

двунаправленный итератор

List set и multiset map и multimap

итератор произвольного доступа

обычные указатели

vector deque

 

Указатели как итераторы

Чтобы продемонстрировать, как применяются итераторы, мы рассмотрим простейший вид итератора — обычный указатель. Следующая программа вызывает стандартный алгоритм find() для поиска значения в обычном массиве.

#include <algorithm>

#include <iostream>

using namespace std;

#define SIZE 50 int iArr[SIZE] ;

int main() {

iArr[30] = 33;

int *ip = find(iArr, iArr + SIZE, 33);

if (ip != iArr + SIZE)

cout<< "Value "<< *ip<< " found at position "<< (ip - iArr)<< endl;

else

cout << "Value not found."<< endl;

return 0;

}

Прежде всего обратите внимание, что программа, применяющая стандартную библиотеку C++, должна специфицировать директивой using namespace пространство имен std.

В примере объявляется “контейнер” — обычный массив длиной в 50 элементов, одному из его элементов присваивается значение 33 и вызывается алгоритм find () для поиска этого значения.

Алгоритму find () передаются три аргумента. Два из них — итераторы, задающие диапазон поиска. Первый из них в данном случае указывает на начальный элемент массива, второй имеет запредельное значение iArr + SIZE, т. е. смещен на один элемент за верхнюю границу массива. Третий аргумент задает искомое значение.

Если find () находит его в заданном диапазоне, алгоритм возвращает соответствующий ему итератор; если нет, возвращается запредельное значение.

Итераторы контейнеров

Итераторы, генерируемые классами контейнеров, используются точно таким же образом, как указатели в показанном выше примере, но для получения граничных значений итератора вь1зываются обычно функции вроде begin () или end () конкретного контейнерного объекта. Вот совершенно аналогичный предыдущему пример для контейнера-вектора:

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

#define SIZE 50 vector<int> iVect(SIZE);

int main() {

iVect[30] = 33;

vector<int>::iterator ii =

find (iVect. begin (), iVect.endO, 33);

if (ii != iVect.endO)

cout << "Value "<< *ii<< " found at position "

<< distance(iVect.begin(), ii) << endl;

else

cout << "Value not found." <<end1;

return 0;

Объявляемый в программе контейнер имеет тип vector<int>, а итератор — тип vector<int>: : iterator. Каждый стандартный контейнер объявляет свой собственный вложенный класс iterator.

Далее мы вкратце рассмотрим различные формы итераторов.

Входные, выходные и поступательные итераторы

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

К обеим этим формам итераторов можно применять, по меньшей мере, операцию неравенства (!=), разыменования (*) и инкремента (++).

Ниже показан пример копирования массива в вектор при посредстве выходного итератора и алгоритма copy (). Его последним параметром может быть любой выходной итератор. На самом деле тот же итератор здесь используется и как входной — в операторе вывода.

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

double dArr[10] =

{1.0, 1.1, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9};

vector<double> dVect(lO);

int main()

{

vector<double>::iterator oi = dVect.begin ();

copy(dArr, dArr + 10, oi);

while (oi != dVect.endO) {

cout << *oi << endl;

oi++;

} return 0;

}

Итераторы потоков

Собственно, тольковходные и тольковыходные итераторы имеют смысл в основном при работе с потоками ввода-вывода, которые могут быть допускать либо только извлечение, либо только передачу данных. Любые контейнеры стандартной библиотеки генерируют более сложные, итераторы, которые, естественно, могут применяться и в качестве простых входных или выходных. / Вы уже хорошо знакомы со стандартными потоками cin и cout, извлечение и передача данных из которых производится операциями >> и <<. Однако возможен другой метод работы с этими потоками, при котором входной или выходной объект iostream преобразуется в итератор. Затем его можно передавать как аргумент стандартным алгоритмам.

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

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

int main( ) {

vector<int> iVect(lO);

for (int i=0; i<10; i++) iVect[i] = i;

cout<< "The vector contents are: { ";

copy(iVect.begin (),

iVect.endf), ostream_iterator<int>(cout, " "));

cout << "}." << endl;

return 0;

}

Последний параметр алгоритма copy () конструирует выходной итератор типа ostream iterator<int>. Параметрами конструктора являются выходной потоки строка - разделитель значений.

Поступательный итератор допускает как чтение, так и запись в контейнер. Однако, как и в случае двух предыдущих, возможен только инкремент, но не декремент итератора. Поступательные итераторы могут использоваться, например, в алгоритме replace (), который определяется так:

template <class Forwardlterator, class T>

void replace(Forwardlterator first,

Forwardlterator last,

const T &old_value,

const T &new_value);

Этот алгоритм заменяет все значения old_value, содержащиеся в контейнере, на new_value.

Двунаправленные итераторы

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

template <class Bidirectioriallterator>

void reverse(Bidirectionallterator first,Bidirectionallterator.last);

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

Итераторы произвольного доступа

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

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

template <class RandomAccessIterator>

void random shuffle(RandomAccessIterator first, RandomAccessIterator last);

Итераторы вставки

Примечание

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

  • Начальные адаптеры, вставляющие объекты в начало контейнера, например, списка (при этом вставленные элементы данных оказываются расположенными в порядке, обратном исходному).
  • Конечные адаптеры, присоединяющие объекты в конец контейнера.
  • Адаптеры вставки, вставляющие данные перед произвольным элементом контейнера.

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

В типичном случае адаптер вставки применяется после поиска некоторого значения, как показано в следующем примере.

////////////////////////////////////////////////////////////////

// Inserter.срр: Демонстрация итераторов вставки. //

#include <algorithm>

#include <list>

#include <iostream>

#pragma hdrstop

#include <condefs.h>

using namespace.std;

int iArr[5] = (1, 2, 3, 4, 5);

//

// Функция вывода содержимого списка.

//

void Display(list<int> &1, const char *label)

(

cout << label<< ": { ";

copy (1 .begin (), 1.end(),

ostream_iterator<int>(cout, " "));

cout << "}" << endl;

}

int main(void) {

list<int> iLst; // Создание объекта списка.

// Копирование массива в список в обратном порядке:

copy(iArr, iArr + 5, front_inserter(iLst));

Display(iLst, "Before insertion");

// Поиск значения З:

list<int>::iterator i = find(iLst.begin(),

iLst.end(), 3) ;

// Вставка массива в список:

copy(iArr, iArr + 5, inserter(iLst, i));

Display(iLst, "After insertion ");

cin.ignore ();

return 0;

}

Рис. 11.1 показывает результат работы программы. Можно отметить различие между inserter (iLst, i-Lst. begin ()) и front inserter (iLst). Первый адаптер вставляет данные в контейнер в прямом, а второй — в обратном порядке.

C++Builder, программы, электронные книги, раскрутка, оптимизация

Рис. 11.1Демонстрация адаптеров

Функции итераторов

Имеются две функции, которые могут оказаться полезными при работе с итераторами. Это advance () и distance (.) .

Функция advance () выполняет инкремент или декремент итератора указанное число раз. Ей передается итератор и число, определяющее число повторений инкремента или декремента (при отрицательном аргументе). Допустим, вам требуется найти некоторый элемент списка и установить итератор на несколько позиций за ним. Вы можете написать:

list<int> :: iterator i = find (iLst .begin (), iLst.endO, 3);

advance(i, 2); // Сдвигает итератор на 2 позиции вперед.

С функцией distance () вы уже встречались в примере параграфа “Итераторы контейнеров”, где с ее помощью выяснялась позиция итератора по отношению к началу вектора. Эта функция определяет количество инкрементов, которые нужно выполнить для перехода от одного итератора к другому. Она перегружена:

template <class Forwardlterator> iterator_traits<Forward!terator>::

difference_type distance(Forwardlterator first, Forwardlterator last) ;

template <class Forwardlterator, class Distance>

void distance(Forwardlterator first,

Forwardlterator last. Distance &n) ;

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

int d = 0;

distance (iLst, i, d);

Функции и функциональные объекты

Некоторые алгоритмы стандартной библиотеки C++ требуют функций в качестве параметров. Простейший пример — алгоритм for each (), который вызывает переданную ему функцию для каждого элемента контейнера. В этом разделе мы рассмотрим вопросы, связанные с функциональными параметрами алгоритмов.

Функции и предикаты

Иногда нужно выполнить какое-то действие для каждого элемента контейнера. Упомянутый выше алгоритм for_each() позволяет сделать именно это. Функция, выполняющая необходимое действие для отдельного элемента, передается как третий аргумент алгоритма. Первые два задают диапазон. Вот пример:

void Square(int arg) { return arg * arg; }

int main() {

vector<int> iVect;

for_each(iVect.begin (), iVect.end(), Square);

}

Двухместные функции принимают два параметра. Часто они применяются к элементам различных контейнеров. Например, имеется два списка, и нужно что-то сделать с элементом первого списка в зависимости от значения соответствующего ему элемента во втором. Это делается с помощью алгоритма transform (), одна из форм которого имеет вид

template <class Inputlteratorl, class Inputlterator2,

class Outputlterator, class Binary0peration>_

Outputlterator transform(Inputlteratorl firsti,

Inputlteratorl lasti,

Inputlterator2 first2,

Outputlterator result,

BinaryOperation binary_func);

Первые два параметра задают диапазон первого контейнера. Параметр first2 указывает начало второго контейнера. Контейнер, куда будет записан результат, начинается с result. Последний параметр — указатель на двухместную функцию преобразования.

Особо можно выделить функции- предикаты. Предикат — это функция, возвращающая булево значение. Они используются с алгоритмами типа find_if () , который находит в указанном диапазоне значение, для которого предикат истинен:

template <class Inputlterator, class Predicate>

Inputlterator find if(Inputlterator first,

Inputlterator last,

Predicate pred);

Функциональные объекты

Функциональный объект — это представитель класса, в котором определена операция вызова (скобки). Существуют различные ситуации, когда желательно передавать алгоритмам не функции, а функциональные объекты. Иногда это позволяет применить готовый функциональный объект стандартной библиотеки вместо новой функции; иногда — улучшить производительность благодаря генерированию встроенного кода. Кроме того, операция вызова может иметь доступ к информации, которая хранится в объекте — функциональный объект, в отличие от функции, обладает “памятью”.

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

Функциональный объект

Операция

Арифметические

plus

сложение х + у

minus

.вычитание х - у

multiplies

умножение х * у

divides

деление х / у

modulus

остаток х % у

negate

смена .знака -х

Отношения

equal to

равенство ==

not equal to

неравенство !=

greater

больше >

less

меньше <

greater equal

больше или равно >=

less equal

меньше или равно <=

Логические

logical and

логическое И &&

logical or

логическое ИЛИ | |

logical not

логическое отрицание !

 

Например, вызов алгоритма

transform(vec.begin(), vec.endf), vec.begin(),

negate<int> ());

меняет знак всех элементов вектора vec.

Можно привести примеры более сложных функциональных объектов с “памятью”, которые хранят между вызовами информацию о своем текущем состоянии. Определяемые пользователем функциональные объекты часто производятся от шаблонов классов unary_function и binary_function.

Типичным примером функциональнь1х объектов, сохраняющих свое состояние, являются различные генераторы, как, например, генератор случайных чисел.

Вот программа, в которой реализуется совсем простой функциональный объект — генератор чисел Фибоначчи:

///////////////////////////////////////////////////

// FuncObj.cpp: Генератор чисел Фибоначчи.

//

#include <iostream>

#include <algorithm>

#include <vector>

#pragma hdrstop #include <condefs.h>

using namespace std;

class Fibo { // Класс функционального объекта.

int iCur, iNext;

public:

Fibo() { iNext = iCur =1; } // Инициализация состояния.

int operator ()() { // Операция вызова; возвращает

int temp = iCur; // следующий член ряда.

iCur = iNext; iNext = iCur + temp;

return temp;

} };

int main () {

//

// Сначала проверим вручную, как работает класс.

// Fibo fObj ;

cout << "Generated sequence of 16 numbers:" << endl;

for (int i=0; i<15; i++) cout << fObj () << ", ";

cout << f0bj() “ endl;

//

// Теперь генерируем вектор с помощью

// стандартного алгоритма.

//

vector<int> iVec(16);

generate (iVec .begin (), iVec.end(), Fibo());

cout << endl<< "Vector initialized by generate () algorithm:"<< endl;

copy (iVec .begin (), iVec.end(),ostream_iterator<int> (cout, " "));

return 0;

}

Программа выводит:

Generated sequence of 16 numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

Vector initialized by generate() algorithm:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

Объекты-связки

Связка создает из двухместного функционального объекта одноместный функциональный объект, фиксируя значение одного из аргументов. В библиотеке шаблонов имеется два объекта-связки, bindlst и bind2nd. Они предназначены для фиксации соответственно первого или второго аргумента.

Следующий фрагмент кода подсчитывает число элементов в списке со значениями, большими10:

int count = 0;

count_if (aList .begin ()., alist.end(),

bind2nd(greater<int>(), 10), count);

cout<< "Number of elements greater than 10 = " << count<< endl;

Здесь связка bind2nd применяется к функциональному объекту greater, задавая его второй аргумент равным 10 (если применить связку bindlst, то будут подсчитаны элементы, меньшие 10.

Негаторы

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

noti(bind2nd(greater<int>(), 10))

означает “не больше 10”. Конечно, такое отношение можно записать и без негатора (имеется функциональный объект less_equal), но все равно негаторы часто оказываются полезны.

Контейнеры

В стандартной библиотеке имеется десять шаблонов классов, реализующих различные структуры данных. Их перечень уже приводился в таблице 10.1. Каждый контейнер имеет свой тип iterator, через представители которого вы получаете доступ к данным. Благодаря тому, что контейнеры — это шаблоны, они обладают чрезвычайной общностью. В них можно хранить объекты, указатели на них и даже другие контейнеры, создавая, таким образом, многоуровневые структуры данных.

Есть некоторые основные принципы работы контейнеров, о которых всегда следует помнить. Среди них можно сформулировать следующие:

  • В За запись объекта в контейнер отвечает конструктор копии объекта. При копировании одного контейнера в другой может быть важна перегруженная операция присваивания.
  • Контейнеры сами автоматически выделяют и освобождают память по мере надобности.
  • Когда программа уничтожает контейнер, она первым делом вызывает деструкторы для всех содержащихся в нем объектов. (Это не касается случая, когда в контейнере хранятся не объекты, а указатели на них.)

Векторы

Вектор — это своего рода массив с “интеллектом”, помнящий свой размер и поддерживающий свою целостность. Они, среди прочих контейнеров, отличаются эффективностью доступа к элементам. К недостаткам следует отнести сложность вставки элементов в середину вектора, поскольку при этом приходится перемещать часть его содержимого.

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

Объявления векторов могут выглядеть примерно так:

#include <vector>

vector<int> vint;

vector<double> vdouble (100);

vector<string> vstr(10);

vector<MyClass> myvect(20);

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

vector<int> vint1(24, -1);

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

  • конструктор по умолчанию
  • конструктор копии
  • деструктор
  • операцию взятия адреса
  • операцию присваивания.

Примечание

На самом деле для простых классов, не содержащих указателей на какие-либо динамические объекты, годятся те функции-элементы, что компилятор генерирует сам, за исключением разве что конструктора по умолчанию. (Он генерируется автоматически, только если вы не определили вообще никаких конструкторов. Создаваемые таким конструктором объекты будут содержать “мусор”.) Советую вам обязательно объявлять, хотя бы пустой, конструктор по умолчанию для классов, которые будут размещаться в контейнерах.

Естественно, потребуются еще какие-то механизмы присваивания и извлечения значений элементов данных создаваемого объекта и т. п. Но это вопрос внешний по отношению к функционированию контейнера.

Если вы хотите выполнять поиск или сортировку, потребуются операции равенства (==) и “меньше” (<).

Скелет класса, пригодного для помещения в вектор, может иметь такой вид:

class Coord {

int x, у;

public:

Coord() : x(0), у(0) {}

void set(int _x, int y) { x = x; у = _y; }

void get(int &_x, int &_y) { _x = x, _y = y; ) };

Для доступа к данным вектора применяется индексация:

vstr[3] = "Third value: ";

vdouble[10] = 3.3333333333;

cout<< vstr[l]<< vdouble[10] << endl;

Можно конструировать вектор с помощью итераторов, например:

int iArr[16] ;

vector<int> iVectl(iArr, iArr + 16);

vector<int> iVect2(iVect!.begin(), iVect!.end());

(Для обычного массива, как мы уже говорили, итератором является простой указатель. Второй из векторов конструируется из первого спецификацией его начального и конечного итераторов.)

Действия над векторами

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

Размер и вместимость вектора можно получить с помощью его методов size() и capacity():

cout <<"Size: "<< vdouble.size ()<<"Capacity: " << vdouble .capacity () <<end1;

Есть еще функция max_size(), которая возвращает верхний предел размера и вместимости, определяемый обычно размером наибольшего доступного блока памяти.

Функция resize () позволяет изменить размер массива. Функция is_empty () возвращает true, если вектор пуст (размер равен 0). Вместимость вектора можно изменить его функцией reserve (). Заблаговременное резервирование позволяет избежать частых автоматических выделений памяти:

vdouble.reserve (1000);

Функция clear () удаляет все элементы вектора.

Функция assign () присваивает указанное значение первым n элементам:

vdouble.assign (100, 1.0);

Альтернативная форма функции позволяет присвоить элементам значения из диапазона другого контейнера:

void assign (Input-Iterator first, Inputlterator last);

Функции front() и back () возвращают значения соответственно первого и последнего элементов вектора.

Наиболее часто используемыми функциями векторов являются, вероятно, erase () и insert (). Они служат для удаления и вставки элементов. При удалении элемента (или нескольких элементов) из вектора все последующие сдвигаются к началу. Эти функции перегружены; мы приводим только две формы insert ():

iterator erase (iterator position) ;

iterator erase (iterator first, iterator last) ;

iterator insert(iterator pos, const T& x);

void insert(iterator pos,

Inputlterator first, Inputlterator last) ;

Эти функции позволяют соответственно удалить элемент, удалить диапазон, вставить элемент и вставить диапазон элементов из другого контейнера.

С помощью функций push_back () и pop_back () вектор можно использовать как стек. Первая из них вставляет элемент в конец вектора, вторая — удаляет конечный элемент (она не возвращает его значение).

Вот небольшая иллюстрация:

#include <iostream>

#include <vector>

#pragma hdrstop

#include <condefs.h>

using namespace std;

//

// Вспомогательная функция для вывода содержимого контейнера

//

template<class T> void Display(const Т &с) {

cout<< "( " ;

copy(с.begin (), c.end(),

ostream_iterator<T::value_type> (cout, " "));

cout << "} Size: " << c.size() << endl;

}

int main ()

(

int iarr[5] = (1, 2, 3, 4, 5);

vector<int> vintl(iarr, iarr + 5);

cout << "Initial vector : ";

Display(vinti);

vector<int>::iterator p =

find(vinti.begin (), vintl.end(), 3);

vinti.erase (p);

cout << "After erasing 3: ";

Display(vinti);

vinti.insert (p, iarr, iarr + 3);

cout << "After insertion: ";

Display(vinti);

cout << "Pop and push : ";

vinti.pop_back();

Display(vinti);

vinti.push back(33);

cout << " Display(vinti);

vinti.pop_back ();

return 0;

}

Программа выводит:

Initial vector : {12345} Size: 5

After erasing 3: {1245} Size: 4

After insertion: {1212345} Size: 7

Pop and push : {121234} Size: 6

{ 1 2 1 2 3 4 33 } Size: 7

Полный список функций-элементов вектора вы можете найти в оперативной справке C++Builder'a.

Списки

Списки — двусвязные линейные структуры данных, т. е. каждый элемент имеет два указателя для ссылки на два других элемента. Списки занимают ровно столько памяти, сколько необходимо для хранения наличных элементов. Вставка и удаление из списка очень эффективны. Слабым местом списка является доступ к элементам. Прямой доступ, как в векторах, невозможен. Для поиска нужного элемента приходится двигаться по списку, начиная с самого начала.

Создание списков

Существуют различные способы конструирования списков.

#include <list>

list<int>ilist;

list<double>dlist(20, 1.0);

list<MyType>mtlist(10) ;

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

int iarr[5] = {1, 2, 3, 4, 5};

list<int> linti(iarr, iarr + 5);

В списке можно хранить любой тип данных, при условии, что он поддерживает те функции-элементы (конструкторы и проч.), о которых говорилось выше при обсуждении векторов.

Действия над списками

Поскольку список занимает ровно столько памяти, сколько необходимо, для него не имеет смысла понятие вместимости. Поэтому у списков нет функций capacity () и reserve (). Невозможно и обращение к элементам по индексу.

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

Помимо известных вам уже методов push back() и pop back (), имеются функции push_front () и pop_front () для добавления или удаления элемента в начале списка.

Функция remove () удаляет из списка все элементы с указанным значением.

Функция unique () удаляет все повторяющиеся элементы (стоящие;

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

Функция reverse () обращает порядок элементов в списке.

Функция sort () (без аргумента) производит сортировку списка в соответствии с операцией “меньше”, т. е. в восходящем порядке. Можно задать в качестве аргумента функциональный объект, реализующий отношение, в соответствии с которым нужно сортировать список:

#intlude <functional> linti.sort(greater_equal<int>());

Примечание

Функция sort() сохраняет относительный порядок следования повторяющихся элементов. Такого рода сортировку называют стабильной.

Функцияmerge () выполняет слияние сортированного списка с другим сортированным списком. Элементы второго списка удаляются. Как и в случае sort (), можно задать второй аргумент — функциональный объект, определяющий отношение сортировки.

Примечание

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

Функцияsplice () является специальным вариантом вставки. Она удаляет вставляемый элемент или элементы списка, из которого производится вставка.

Описанные функции частично иллюстрирует следующая программа.

#include <iostream>

#include <list>

#pragma hdrstop

#include <condefs.h>

using namespace std;

//

// Операция передачи списка в поток.

//

template<class T>

ostream &operator“(ostream &os, const list<T> &c)

{

cout << "{ ";

copy (c. begin (), c.end(),

ostream_iterator<T> (os, " "));

os << "} Size: " “ c.size();

return os;

}

int main() {

int iarrl[5] = {5, 7, 3, 1, 9};

list<int> lintl(iarr1, iarr1 + 5);

cout<< "Initial list : "<< linti << endl;

linti.sort (); // Сортировка.

cout << "After sort : "<< lint1 << end1;

int iarr2[6] = {6, 2, 4, 8, 2, 6};

list<int> lint2(iarr2, iarr2 + 6);

cout << "Second list : " << lint2 << end1;

lint2.sort () ;

lint2.unique(); // Удаление повторов.

cout<< "Sorted unique: " << lint2 “ endl;

linti.merge(lint2); // Слияние.

cout <<"After merge : " << lint1 “ end1;

linti.reverse (); // Обращение порядка.

cout << "After reverse: "<< lint1 << end1;

return 0;

}

Initial list : {5731

 
MKPortal©2003-2008 mkportal.it
MultiBoard ©2007-2009 RusMKPortal