 |
Контейнер последовательностей 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.
|
|
|
