Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Контейнер последовательностей deque




Класс deque объединяет многие возможности классов vector и list. Этот класс представляет собой двунаправленную очередь. В классе deque реализован механизм эффективного индексного доступа (подобно тому, как и в классе vector).

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

Класс deque имеет базовые функции, аналогичные классу vector, при этом в класс deque добавлены компоненты-функции push_front и pop_front.

#include <iostream>

using std::cout;

using std::endl;

#include <deque>

#include <algorithm>

template<class T>

void PrintDeque(const std::deque<T> &dq);

 

#define SIZE 6

main()

{ std::deque<float> d,dd(3,1.5);

PrintDeque(dd);

d.push_back(2);

d.push_front(5);

d.push_back(7);

d.push_front(9);

d[4]=3; // изменить значение 5-го элемента на 3

d.at(3)=6;

try{ d.at(5)=0;

}

catch(std::out_of_range e){

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

}

PrintDeque(d);

d.erase(d.begin() + 2); // удаление 3-го элемента

PrintDeque(d);

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

PrintDeque(d);

d.insert(d.end()-1,2,1.6);

PrintDeque(d);

d.insert(d.end(),dd.begin(),dd.end());

PrintDeque(d);

std::sort(d.begin(),d.end());

PrintDeque(d);

d.swap(dd); // замена массивов v и vv

PrintDeque(d);

PrintDeque(dd);

dd.erase(dd.begin(),dd.end()); //удаление всех элементов dd

PrintDeque(dd);

d.clear(); // чистка всего вектора

PrintDeque(d);

return 0;

}

template<class T>

void PrintDeque(const std::deque<T> &dq)

{ std::deque<T>::const_iterator pt;

if (dq.empty())

{ cout << "Deque is empty " << endl;

return;

}

cout<<"DEQUE:"

<<" размер = "<<dq.size()<<endl;

cout<<" содержимое = ";

for(pt=dq.begin();pt!=dq.end();pt++)

cout<<*pt<<' ';

cout<<endl;

}

Результат работы программы:

DEQUE: размер = 3 содержимое =1.5 1.5 1.5

Исключение: invalid deque<T> subscript

DEQUE: размер = 4 содержимое =9 5 2 6

DEQUE: размер = 3 содержимое =9 5 6

DEQUE: размер = 4 содержимое =9 5 6 7

DEQUE: размер = 6 содержимое =9 5 6 1.6 1.6 7

DEQUE: размер = 9 содержимое =9 5 6 1.6 1.6 7 1.5 1.5 1.5

DEQUE: размер = 9 содержимое =1.5 1.5 1.5 1.6 1.6 5 6 7 9

DEQUE: размер = 3 содержимое =1.5 1.5 1.5

DEQUE: размер = 9 содержимое =1.5 1.5 1.5 1.6 1.6 5 6 7 9

Deque is empty

Deque is empty

В приведенном примере использованы все ранее рассмотренные функции классов vector и list, также являющиеся компонентами класса deque. В программе были использованы все три версии функции insert:

iterator insert(iterator it, const T& x = T());

void insert(iterator it, size_type n, const T& x);

void insert(iterator it, const_iterator first, const_iterator last);

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

 

Ассоциативные контейнеры

Ассоциативные контейнеры предназначены для обеспечения прямого доступа посредством использования ключей. В STL имеется четыре ассоциативных контейнерных класса: multiset, set, multimap и map. Во всех контейнерах ключи отсортированы. Классы multiset и set манипулируют множествами значений, одновременно являющихся ключами. При этом multiset допускает одинаковые ключи, а set нет. Классы multimap и map манипулируют множествами значений, ассоциируемых с ключами. При этом multimap допускает хранение одинаковых ключей с ассоциированными значениями, а map нет.

Ассоциативный контейнер multiset

Ассоциативный контейнер multiset обеспечивает быстрое сохранение и выборку ключей. Упорядочение элементов контейнера определяется компараторным объектом-функцией less<тип>, при этом отсортированные ключи должны поддерживать сравнение с помощью operator<, иначе (для пользовательских типов) необходимо перегружать операцию сравнения.

Класс multiset поддерживает двунаправленные итераторы (но не итераторы произвольного доступа).

#include <iostream>

using std::cout;

using std::endl;

#include <set>

#include <algorithm>

typedef std::multiset<int,std::less<int> > intMSET;

#define size 10

main()

{ int mas[]={2,4,1,6,19,17,1,7,17,14};

intMSET mset;

std::ostream_iterator<int> out(cout," ");

intMSET::const_iterator res;

cout<<"элемент 8 содержится в multiset " << mset.count(8)<<" раз\n";

mset.insert(8); //

mset.insert(8);

cout<<"содержимое multiset:";

std::copy(mset.begin(),mset.end(),out);

res=mset.find(6);

cout<<'\n';

if(res!=mset.end())

cout<<"найдено значение 6\n";

else cout<<"не найдено значение 6\n";

mset.insert(mas,mas+sizeof(mas)/sizeof(int)); //

cout<<"содержимое multiset:";

std::copy(mset.begin(),mset.end(),out);

cout<<"\nнижняя граница числа 17 " << *(mset.lower_bound(17));

cout<<"\nверхняя граница числа 17 " << *(mset.upper_bound(17));

std::pair<intMSET::const_iterator, intMSET::const_iterator> pr;

pr=mset.equal_range(17);

cout<<"\nнижняя граница числа 17 " << *(pr.first);

cout<<"\nверхняя граница числа 17 " << *(pr.second);

return 0;

}

Результат работы программы:

элемент 8 содержится в multiset 0 раз

содержимое multiset: 8 8

не найдено значение 6

содержимое multiset: 1 1 2 4 6 7 8 8 14 17 17 19

нижняя граница числа 17 17

верхняя граница числа 17 19

нижняя граница числа 17 17

верхняя граница числа 17 19

В приведенной программе использованы следующие компоненты контейнерного класса multiset:

mset.count(8) – функция, доступная во всех ассоциативных контейнерах, возвращает число вхождений значения 8 в multiset. Затем в программе использованы две из трех версий функции insert:

mset.insert(8);

mset.insert(mas,mas+sizeof(mas)/sizeof(int));

первая из двух функций insert вставляет значение 8 во множество, а вторая - числа из интервала.

Далее используются функции lower_bound(17) и upper_bound(17) (доступные во всех ассоциативных контейнерах) для определения позиции первого вхождения числа 17 во множество и позиции элемента после последнего вхождения. Обе функции возвращают iterator или const_iterator соответствующих позиций, или итератор, возвращаемый функцией end.

В строке

std::pair<intMSET::const_iterator, intMSET::const_iterator> pr;

создается объект класса pair. Объекты класса pair используются для связывания пар значений. Объект pr используется для сохранения в нем значения pair, возвращаемого функцией equal_range и содержащего результаты lower_bound() и upper_bound(). Тип pair содержит две открытые компоненты с именами first и second. Для доступа к lower_bound() и upper_bound используются pr.first и pr.second.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...