void advance (InputIterator& itr, Distance& n);

Вторая операция измеряет расстояние между итераторами first и second, возвращая полученное число через ссылку n:

void distance(InputIterator& first, InputIterator& second, Distance& n);

9.5. Контейнеры последовательностей

Стандартная библиотека С++ предоставляет три контейнера последова- тельностей – vector, list и deque. Первые два представляют собой классы, орга- низованные по типу массивов, а последний реализует связанный список. Класс vector является одним из наиболее популярных контейнерных классов в STL, динамически изменяющим свои размеры.

Использование контейнера vector наиболее эффективно при добавлении
элементов в конец контейнера. Для приложений, выполняющихРчастые вставки
		У
и удаления в конец и начало контейнера, более предпочтительным является
deque. Если требуется выполнять вставки и удаление элементовИв любое место
контейнера, то обычно используется list.
Кроме перечисленных выше компонент-функций, общих для всех STL-
контейнеров, контейнеры последовательностейГимеют несколько особых: front
	а
и back − для возврата ссылки на первый и последний элемент в контейнере,
push_back и pop_back – для встав и удБления последнего элемента контей-
нера.	ки
9.5.1. Контейнер посл доват льностей vector
Аналогично обычным массивам в С и С++, класс vector обеспечивает не-
прерывную область памя и	едля размещения данных. Следовательно, возможен
о
доступ к любому элемен у кон ейнера посредством индексации. В случае, если

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

	Контейнер vector поддерживает итераторы произвольного доступа, т.е.
		и
все операции итераторов (табл. 4) могут быть применены к итератору контейне-
ра vector. Все а горитмы STL могут работать с контейнером vector.
	л
	В приводимой ниже программе демонстрируется использование некото-
	б
рых компонент-функций класса vector.
и
Б	#include <iostream>
	using namespace std;

#include <vector> template<class T>

void PrintVector(const std::vector<T> &vect); int main()

{std::vector<int> v,vv; PrintVector(v);

203

v.push_back(2);

v.push_back(5);

v.push_back(7);

v.push_back(1);

v.push_back(9);

v[4]=3;

// изменить значение 5-го элемента на 3

v.at(3)=6;

// изменить значение 3-го элемента на 6

try{ v.at(5)=0;

//

}

catch(std::out_of_range e){ //доступ к элементу вне массива (вектора)

}

cout<<"\nИсключение : "<<e.what();

Р

PrintVector(v);

У

v.erase(v.begin() + 2); // удаление 3-го элемента (начальный индекс 0)

PrintVector(v);

Г

И

v.insert(v.begin() + 3,7);// добавление 7 после 3-го элемента вектора

PrintVector(v);

vv.push_back(6);

а

v.swap(vv);

// замена массивов v и vv

PrintVector(v);

к

Б

PrintVector(vv);

vv.erase(vv.begin()+1,vv.end()-2); //удаление со 2-го по n-2 элементов

PrintVector(vv);

vv.clear();

// чистка вс го в ктора

PrintVector(vv);

е

}

return 0;

т

и

template<class T>

void PrintVector(const оstd::vector<T> &vect)

{ std::vector<T>::const iterator pt;

б

if (vect.empty())

и

{ cout << endlл<< "Vector is empty." << endl;

return;

Б

}

cout<<"ВЕКТОР

:"

<<" Размер ="<<vect.size()

<<" вместимость ="<<vect.capacity()<<endl; cout<<"содержимое :"; for(pt=vect.begin();pt!=vect.end();pt++) cout<<*pt<<' ';

cout<<endl;

}

204

Инструкция std::vector<int> v,vv;

определяет два экземпляра класса v и vv для хранения int чисел. При этом соз- даются два пустых контейнера с нулевым числом элементов и нулевой вмести- мостью (числом элементов, которые могут быть сохранены в контейнере). Компонента-функция push_back(), имеющаяся во всех контейнерах последова- тельностей, используется для добавления элемента в контейнер v. Инструкции

v[4]=3;

v.at(3)=6;

[], возвращающей либо ссылку на значение в требуемой позицииР, либо кон- стантную ссылку на это значение, в зависимости от того, является ли контейнер

демонстрируют два способа индексирования контейнера vector (используются и

для контейнера deque). Первая инструкция реализуется перегрузкой операции

константным. Следующая функция at() выполняет тоУже, Иосуществляя дополни- тельно проверку на выход индекса из диапазонаГ. Функции size() и capacity() возвращают число элементов вектора (диапазон) и его вместимость. Вмести- мость удваивается каждый раз в том случаеБ, когда при попытке разместить оче- редной элемент в контейнере все выделенное пространство памяти занято.

При добавлении первого элемен размер стал равен 1, вместимость 1, второго – размер 2, вместимость 2, третьего − 3 и 4 соответственно, четвертого − 4 и 8 и т.д. В примере приведена внешняя функция просмотра вектора и его

размера и вместимости PrintVector(). Для прохода по вектору используется ите-
ратор pt:			та
			к
	std::vector<T>::const
			iterator pt;
	Этот итератор (const		iterator)едопускает считывание, но не модификацию
элементов контейнера vector. При проходе по вектору используются функции
begin() и end(), д ступные для всех контейнеров первого класса.
	Кроме переч сленныхтвыше в программе используются функции класса
vector: clear(), empty()оswap().
	Контейнер vector не должен быть пустым, иначе результаты функций
		и
front и back удут не определены.
		л
	9.5.2. Контейнер последовательностей list
	б
	Контейнерный класс list реализуется как двусвязный список, что позволя-
и
Б

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

Шаблон класса list предоставляет еще восемь функций-членов: splice, push_front, pop_front, remove, unique, merge, reverse и sort. Многие функции класса vector поддерживаются также и в классе list. Для работы с объектом (его компонентами) необходимо включать заголовочный файл <list>.

205

#include <iostream>
using namespace std;
#include <list>
template<class T>
void PrintList(const std::list<T> &lst);
int main()
{ std::list<int>	ls,ll;
std::list<int>::iterator itr;
int ms[]={2,5,3};									Р
int mm[]={2,15,23,1};
ls.push_back(2); ls.push_front(5);
ls.push_front(7); ls.push_back(9);
PrintList(ls);							У
ll.insert(ll.begin(),ms,ms+sizeof(ms)/sizeof(int));// добавление								И
PrintList(ll);						Г
ll.push_front(6);
ls.splice(ls.end(),ll);
PrintList(ls);					а
PrintList(ll);						Б
ls.sort();		// сортировка ls			к
PrintList(ls);
			еме
ll.insert(ll.begin(),mm,mm+sizeof(mm)/sizeof(int));
PrintList(ll);
ll.sort();		// сортировка ll
ls.merge(ll);		// перенос эл			н ов ll в ls
PrintList(ls);
ls.pop_front();		// удаление первого элемента списка
ls.pop_back();		и
		// удалениетпоследнего элемента списка
ls.reverse();		// реверсивныйо		переворот списка ls
PrintList(ls);
б		// удаление из списка ls одинаковых элементов
ls.unique();
и
PrintList(ls);л
ls.swap(ll);		// обмен содержимым списков ls и ll
Б
PrintList(ls);
PrintList(ll);
ls.push_front(2);
ls.assign(ll.begin(),ll.end());// замена ls содержимым ll
PrintList(ls);
PrintList(ll);
ls.remove(2);		// удаление из ls всех 2
PrintList(ls);
itr=ls.begin();
itr++;

206

	ls.erase(itr,ls.end());// удаление из ls элементов с itr до ls.end
	PrintList(ls);
	return 0;
	}
	template<class T>
	void PrintList(const std::list<T> &lst)
	{ std::list<T>::const_iterator pt;
	if (lst.empty())
	{ cout << endl << "List is empty." << endl;
	return;
	}
	cout<<" LIST размер = "<<lst.size()<<" содержимое = ";
	for(pt=lst.begin();pt!=lst.end();pt++)						У		Р
	cout<<*pt<<' ';					Г		И
	cout<<endl;
	}					Б
	Результат работы программы:
	LIST	размер = 4			содержимое = 7 5 2 9
	LIST	размер = 3			содержимое	= 2 5 3
	LIST	размер = 8			содержимое	= 7 5 2 9 6 2 5 3
	List is empty.				сод ржимоеа= 2 2 3 5 5 6 7 9
	LIST	размер = 8
	LIST	размер = 4			сод ржимоек	= 2 15 23 1
	LIST			т		= 1 2 2 2 3 5 5 6 7 9 15 23
		размер = 12 сод ржимое
	LIST	размер = 10 содержимое				= 15 9 7 6 5 5 3 2 2 2
	LIST		о		содержимое	= 15 9 7 6 5 3 2
		размер = 7
		и
	List is empty.
	LIST	размер = 7			содержимое	= 15 9 7 6 5 3 2
	л				содержимое	= 15 9 7 6 5 3 2
	LIST	размер = 7
	б	размер = 7			содержимое	= 15 9 7 6 5 3 2
	LIST
	LIST	размер = 6			содержимое	= 15 9 7 6 5 3
	LIST	размер = 1			содержимое	= 15
Б	Рассмотрим некоторые конструкции, использованные в программе.

иИспользуя функцию push_back (общую для всех контейнеров последова- тельностей) вставки чисел в конец ls и push_front (определенную для классов list

и deque), добавления значений в начало ls, создаем последовательность целых чисел. В инструкции

ll.insert(ll.begin(),ms,ms+sizeof(ms)/sizeof(int));

используется функция insert класса list, вставляющая в начало последовательно- сти ll элементы массива ms.

Далее в строке ls.splice(ls.end(),ll);

207