Предыдущий пост -
Следующий пост -

std::deque

Рубрика: Контейнеры, Дата: 18 May, 2013, Автор:

Рассмотрим std::deque – это двусторонняя очередь.

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

Начнем разбор как всегда с подключения заголовочных файлов.

#include <deque>
using std::deque;

Строки выше подключают очередь.

Инициализация deque (constructors)

Конструкторы такие же самые как и для списков.

	//пустая очередь
	deque<int> deq;
	//4 элемента со значением по 100
	deque<int> deq1(4,100);//4 по 100
	//инициализация через итераторы
	deque<int> deq2(deq1.begin(),deq1.end());//4 по 100
	//конструктор копирования
	deque<int> deq3(deq2);//4 по 100

	//инициализация через массив
	int mass[4]={3,4,5,1};
	deque<int> deq4(mass,mass+4);

	//выведем все очереди
	deque<int>::iterator it;

	cout <<"deq= ";
	for(it=deq.begin();it!=deq.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	cout <<"deq1= ";
	for(it=deq1.begin();it!=deq1.end();++it)
		cout <<*it<<' ';
	cout <<endl;
	cout <<"deq2= ";
	for(it=deq2.begin();it!=deq2.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	cout <<"deq3= ";
	for(it=deq3.begin();it!=deq3.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	cout <<"deq4= ";
	for(it=deq4.begin();it!=deq4.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	return 0;

deque::operator=

Это просто оператор присваивания, можно одной очереди присвоить другую.

	deque<int> deq;
	deque<int> deq1(4,100);

	//выведем размеры
	cout <<"deq.size()= "<<deq.size()<<endl;//0
	cout <<"deq1.size()= "<<deq1.size()<<endl;//4

	//теперь воспользуемся operator=
	deq=deq1;//4 по 100

	//выведем размеры
	cout <<"deq.size()= "<<deq.size()<<endl;//4
	cout <<"deq1.size()= "<<deq1.size()<<endl;//4

	return 0;

Рассмотрим итераторы.

В очереди имеются как прямые так и обратные (реверсивные) итераторы. В общем щас посмотрим как они работают. Для начала рассмотрим не константные прямые и обратные итераторы.

	deque<int> deq;
	for(int i=0;i<10;i++)//1 2 3 4 5 6 7 8 9
		deq.push_back(i);

	//выведем с помощью прямого итератора
	deque<int>::iterator it;
	//1 2 3 4 5 6 7 8 9
	for(it=deq.begin();it!=deq.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	//выведем с помощью реверсивного итератора

	deque<int>::reverse_iterator r_it;
	//9 8 7 6 5 4 3 2 1
	for(r_it=deq.rbegin();r_it!=deq.rend();++r_it)
		cout <<*r_it<<' ';
	cout <<endl;

	return 0;

Рассмотрим константные итераторы.

	deque<int> deq;
	for(int i=0;i<10;i++)
		deq.push_back(i);

	//вывод с помощью константного прямого итератора
	deque<int>::const_iterator c_it;
	for(c_it=deq.begin();c_it!=deq.end();++c_it)
		cout <<*c_it<<' ';
	cout <<endl;

	//вывод с помощью константного реверсивного итератора
	deque<int>::const_reverse_iterator c_r_it;
	for(c_r_it=deq.rbegin();c_r_it!=deq.rend();++c_r_it)
		cout <<*c_r_it<<' ';
	cout <<endl;

	return 0;

Теперь разберем функции емкости очереди (capacity)

deque::size()

Эта функция возвращает размер очереди.

	deque<int> deq(4);//4 по 0
	deque<int> deq1(10,5);//10 по 5
	deque<int> deq2(7,10);//7 по 10
	
	//выведем размеры
	cout <<"deq.size()= "<<deq.size()<<endl;//4
	cout <<"deq1.size()= "<<deq1.size()<<endl;//10
	cout <<"deq2.size()= "<<deq2.size()<<endl;//7

deque::max_size()

Возвращает максимально возможный размер очереди (количество элементов)

	deque<int> deq(4);//4 по 0
	
	//выведем размеры
	cout <<"deq.max_size()= "<<deq.max_size()<<endl;//большое число
	
	return 0;

deque::resize()

Эта функция изменяет размер очереди.

	deque<int> deq(4);//4 по 0
	
	//выведем размеры
	cout <<"deq.size()= "<<deq.size()<<endl;//4
	deq.resize(2);
	cout <<"deq.size()= "<<deq.size()<<endl;//2
	deq.resize(10);
	cout <<"deq.size()= "<<deq.size()<<endl;//10
	
	return 0;

deque::empty()

Если очередь пустая то возвращает true, если нет то false.

	deque<int> deq(4);//4 по 0
	
	if(deq.empty())
		cout <<"empty"<<endl;
	else
		cout <<"not empty"<<endl;//not empty
	
	return 0;

deque::shrink_to_fit

Это функция из стандарта 2011, пока мы ее пропустим.

Я от сделал пример, но не ясно что происходит, вроде ничего не изменяется.

	deque<int> deq(4);//4 по 0
	
	cout <<"deq.size()= "<<deq.size()<<endl;//4
	deq.resize(10);
	cout <<"deq.size()= "<<deq.size()<<endl;//4
	deq.shrink_to_fit();
	cout <<"deq.size()= "<<deq.size()<<endl;//10
	
	return 0;

Элементы доступа (element assecc)

deque::operator[]

Очередь походу поддерживает оператор произвольного доступа (без проверки диапазона). Щас протестируем.

	deque<int> deq(10); //10 по 0
	//присваиваем переменной тип size_type
	//и значение deq.size()
	deque<int>::size_type sz=deq.size();

	//инициализируем элементами
	for(int i=0;i<sz;i++)
		deq[i]=i;
	
	//выводим очередь
	for(int i=0;i<sz;i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	return 0;

deque::at()

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

//test deque
#include <iostream>
using std::cout;
using std::endl;
#include <deque>
using std::deque;
#include <stdexcept>
using std::out_of_range;

int main()
{
	deque<int> deq(10); //10 по 0
	//присваиваем переменной тип size_type
	//и значение deq.size()
	deque<int>::size_type sz=deq.size();

	//инициализируем элементами
	for(int i=0;i<sz;i++)
		deq.at(i)=i;
	
	//выводим очередь
	try
	{
		for(int i=0;i<sz+1;i++)
			cout <<deq.at(i)<<' ';
		cout <<endl;
	}
	catch(out_of_range& e)
	{
		cout <<"out_of_range"<<endl;
	}

	return 0;
}

deque::front() и deque::back()

Соответственно доступ к первому и последнему элементу очереди.

	deque<int> deq(10); //10 по 0
	//присваиваем переменной тип size_type
	//и значение deq.size()
	deque<int>::size_type sz=deq.size();

	//инициализируем элементами
	for(int i=0;i<sz;i++)
		deq.at(i)=i;
	
	cout <<"deq.front()= "<<deq.front()<<endl;//0
	cout <<"deq.back()= "<<deq.back()<<endl;//9

	return 0;

Модификаторы (modifiers)

deque::assign()

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

	deque<int> deq; //пустая очередь
	deque<int> deq1(4,300);//4 по 300
	
	//простое назначение
	deq.assign(10,100);//10 элементов по 100
	//выведем очередь
	//100 100 100 100 100 100 100 100 100 100
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	//назначение через указатели
	deq.assign(deq1.begin(),deq1.end());//4 по 300
	//выведем очередь
	//300 300 300 300
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	//попробуем назначит через указатель на массив
	int mass[4]={3,4,5,6};
	deq.assign(mass,mass+4);
	//выведем очередь
	//3 4 5 6
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	return 0;

deque::push_back() и deque::front()

Это функции соответсвтенно добавляют элементы в очередь в начало и в конец. Ща спосмотрим примерчик.

	deque<int> deq(4,300);//4 по 300
	
	//добавляем в конец очереди элемент 10
	deq.push_back(10);
	//добавляем в начало очереди элемент 1000
	deq.push_front(1000);

	//вывод на печать
	//1000 300 300 300 10
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	return 0;

deque::pop_back() и deque::pop_front()

Эти методы удаляют элементы из очереди, соответственно из конца и начала.

	deque<int> deq(3);//3 по 0
	deq[0]=2;
	deq[1]=4;
	deq[2]=5;
	//выведем элементы
	//2 4 5
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	//удалим 2 из начала и 5 из конца
	deq.pop_back();//удаление последнего элемента из очереди
	deq.pop_front();//удаление первого элемента из очереди

	//вывод результатов
	//4
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	return 0;

deque::insert()

Эта функция вставляет элементы в очередь, на место када указывает указатель. Щас попробуем протестировать.

//test deque
#include <iostream>
using std::cout;
using std::endl;
#include <deque>
using std::deque;
#include <vector>
using std::vector;

int main()
{
	deque<int> deq(3,300);//3 по 300
	deque<int>::iterator it;
	
	it=deq.begin();
	advance(it,2);
	cout <<"*it= "<<*it<<endl;
	//вставляем после it 10, перед третим 300
	//300 10 300 300
	
	//если it не присвоить, то его заново нужно инициализировать
	it=deq.insert(it,10);
	
	//вывод результатов
	//300 300 10 300
	//it указывает на элемент который вставили элемент
	cout <<"*it= "<<*it<<endl;
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	//вставим несколько элементов после первого элемента списка
	it=deq.begin();
	++it;
	deq.insert(it,2,11);//2 по 11 на место после элемента it
	//вывод результатов
	//300 11 11 300 10 300
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	//добавим элементы из вектора
	vector<int> vec(2,50);
	it=deq.begin();
	advance(it,2);
	deq.insert(it,vec.begin(),vec.end());
	//вывод очереди
	//300 11 50 50 11 300 10 300
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;
	
	return 0;	
}

deque::erase()

erase – переводится как стереть, удаляет элементы из очереди.

	deque<int> deq;
	deque<int>::iterator it;

	for(int i=0;i<10;i++)
		deq.push_back(i);
	//выведем очередь
	//0 1 2 3 4 5 6 7 8 9
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	//удалим третий элемент 2
	it=deq.begin();
	advance(it,2);
	deq.erase(it);
	//выведем очередь
	//0 1 3 4 5 6 7 8 9
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;

	//удалим 4 первых элемента
	deq.erase(deq.begin(),deq.begin()+4);
	//выведем очередь
	//5 6 7 8 9
	for(int i=0;i<deq.size();i++)
		cout <<deq[i]<<' ';
	cout <<endl;
	
	return 0;

deque::swap()

Эта функция меняет очереди местами.

	deque<int> deq(5,500);//5 по 500
	deque<int> deq1(3,400);//3 по 400

	cout <<"deq.size()= "<<deq.size()<<endl;//5
	cout <<"deq1.size()= "<<deq1.size()<<endl;//3
	
	//делаем обмен
	deq.swap(deq1);
	cout <<"deq.size()= "<<deq.size()<<endl;//5
	cout <<"deq1.size()= "<<deq1.size()<<endl;//3

	return 0;

deque::clear()

Очищает очередь, то есть удаляет все элементы из него.

	deque<int> deq(5,500);//5 по 500
	cout <<"deq.size()= "<<deq.size()<<endl;//5
	deq.clear();
	cout <<"deq.size()= "<<deq.size()<<endl;//0

	return 0;

deque::emplace(), deque::emplace_front(), deque::emplace_back()

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

Allocator

deque::get_allocator()

Это функция наподобие new() выделяет память.

	deque<int> deq;//пустая очередь
	int* p;
	
	//выделяем память
	p=deq.get_allocator().allocate(5);
	//добавляем значения
	for(int i=0;i<5;i++)
		deq.get_allocator().construct(&p[i],i);

	//выведем значение ячейки на которую указывает p
	for(int i=0;i<5;i++)
		cout <<p[i]<<' ';
	cout <<endl;

	//освободим память
	for(int i=0;i<5;i++)
		deq.get_allocator().destroy(&p[i]);
	deq.get_allocator().deallocate(p,5);

	return 0;

Функции которые не есть членами класса deque

Операторы сравнения (relational operators)

	deque<int> deq(3,300);//3 по 300
	deque<int> deq1(2,200);//2 по 200

	if(deq==deq1) cout <<"deq==deq1"<<endl;
	else cout <<"deq!=deq1"<<endl;//deq!=deq1

	if(deq!=deq1) cout <<"deq!=deq1"<<endl;//deq!=deq1
	else cout <<"deq==deq1"<<endl;

	if(deq>deq1) cout <<"deq>deq1"<<endl;//deq>deq1
	else cout <<"deq<deq1"<<endl;

	if(deq<deq1) cout <<"deq<deq1"<<endl;
	else cout <<"deq>deq1"<<endl;//deq>deq1

	if(deq>=deq1) cout <<"deq>=deq1"<<endl;//deq>=deq1
	else cout <<"deq<=deq1"<<endl;

	if(deq<=deq1) cout <<"deq<=deq1"<<endl;
	else cout <<"deq>=deq1"<<endl;//deq>deq1

	return 0;

utility::swap()

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

	deque<int> deq(3,300);//3 по 300
	deque<int> deq1(2,200);//2 по 200

	cout <<"deq.size()= "<<deq.size()<<endl;//3
	cout <<"deq1.size()= "<<deq1.size()<<endl;//2
	swap(deq,deq1);
	cout <<"deq.size()= "<<deq.size()<<endl;//2
	cout <<"deq1.size()= "<<deq1.size()<<endl;//3

На этом пожалуй с двусторонней очередью мы покончим. Начнем рассматривать std::stack.

rss