Языки программирования

доступ к элементам, как у vector
эффективную вставку и удаление с

обоих концов за постоянное время
Распределение памяти выполняется автоматически.

осуществляется через массив указателей.
При добавлении в начало или конец

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

Закрашенная область блоков - занятые элементы
Не закрашенная – свободные элементы

равными value
explicit deque(size_type n,
const T& value = T());
С

заполнением значениями из другого контейнера с использованием диапазона итераторов [first, last)
explicit deque(InputIter first,
InputIter last);
Конструктор копирования
deque(const deque& x);

доступа к элементам [], метод доступа at
Методы получения итераторов begin,

end, rbegin, rend
Метод вставки insert, метод добавления в конец push_back, удаления из конца pop_back, добавления в начало push_front, удаления из начала pop_front
Метод удаления erase, очистки clear
Метод получения количества элементов size, изменения количества resize

< 5; i++)
{
d.push_back(i * i);
d.push_front(i * i * i);
}
for (deque::iterator

i = d.begin(); i != d.end(); i++)
cout << *i << " ";

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

итераторов:
++, -- выполняются за постоянное время
+k, -k – за время, пропорциональное k

back();
Методы добавления и удаления в начало и конец
void push_front(const& T

value);
void pop_front();
void push_back(const& T value);
void pop_back();
Получение и изменение размера
size_type size();
void resize(size_type sz);

const T&

value);
void insert(iterator pos,int n,
const T& value);
void insert(iterator pos,
InputIter first,
InputIter last);
iterator erase(iterator pos);
iterator erase(iterator first,
iterator last);
void swap(list& x);
void clear();

перемещения элементов из одного списка в другой без перераспределения памяти,

только за счет изменения указателей
Перенос всех элементов x перед pos
void splice(iterator pos, list& x);
Перенос одного элемента из x, на который указывает i в позицию перед pos
void splice(iterator pos, list& x,
iterator i);
Перенос всех элементов x из диапазона [first, last)
void splice(iterator pos, list& x,
iterator first,
iterator last);

все вхождения)
void remove(const& T value);
По условию, задаваемому предикатом
void remove_if(Predicate pred);
Методы

упорядочивания элементов
По возрастанию (для T должна быть определена операция <)
void sort();
С помощью функционального объекта сравнения (см. примеры для priority_queue)
void sort(Compare comp);

списке
При наличии операции ==, определенной для T
void unique();
С помощью бинарного

предиката, возвращающего значение типа bool (истина  два элемента равны)
void unique(BinaryPredicate pred);
Метод слияния упорядоченных списков
void merge(list& x, Compare comp);
Метод изменения порядка элементов на обратный
void reverse();

operator

l.begin(); i != l.end(); i++)
out << *i << " ";
cout << endl;
return out;
}
…….
list l;
for (int i = 0; i < 20; i++)
l.push_back(rand() % 10);
cout << "Random list : " << l;
l.remove(0);
cout << "After remove(0) : " << l;
l.sort();
cout << "After sort : " << l;
l.unique();
cout << "After unique : " << l;

одного из существующих контейнеров (vector, deque, list).
По умолчанию –

deque.

>
class stack {
protected:
Container c;
public:
explicit stack(const Container& _c = Container()) {

c = _c; }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
T& top() { return c.back(); }
void push(const T& x) { c.push_back(x); }
void pop() { c.pop(); }
};

10; i++)
st.push(i);
cout

endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}

одного из существующих контейнеров (deque, list).
По умолчанию – deque.
vector

не подходит, т.к. нет операции удаления из начала.

>
class queue{
protected:
Container c;
public:
explicit queue(const Container& _c = Container()) { c

= _c; }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
T& front() { return c.front(); }
T& back() { return c.back(); }
void push(const T& x) { c.push_back(x); }
void pop() { c.pop(); }
};

10; i++)
q.push(i);
cout

endl;
cout << "last element = " << q.back() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}

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

умолчанию порядок определяется операцией < - из очереди выбирается максимальный элемент.
priority_queue – адаптер контейнера с произвольным доступом к элементам, например, vector или deque (по умолчанию – vector).

= vector, class Compare = less >
class priority_queue{
protected:
Container c;
Compare comp;
public:
explicit

priority_queue(const Compare& _comp = Compare(), const Container& _c = Container());
priority_queue(InputIter first, InputIter last, const Compare& _comp = Compare(), const Container& _c = Container());
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
T& top() { return c.front(); }
void push(const T& x);
void pop();
};

на меньше. Можно задать стандартные значения:
less - сравнение на меньше
greater

- сравнение на больше
less_equal<тип> - сравнение на меньше или равно
greater_equal<тип> - сравнение на больше или равно
Данные стандартные функциональные объекты определены в заголовочном файле

функциональный объект less, который требует, чтобы у типа T была

реализована операция <.
При необходимости можно реализовать собственный функциональный объект сравнения, в нем должна быть определена операция () с двумя параметрами (сравниваемыми объектами) результат сравнения (тип bool) истина  первый параметр меньше второго

- сравнение прямоугольников по площади (I)
class Rectangle
{
public:
double A, B;
Rectangle(double _A

= 0.0, double _B = 0.0) : A(_A), B(_B) {}
double getArea() const { return A * B; };
bool operator < (const Rectangle& x) const {
return getArea() < x.getArea();
}
};

- сравнение прямоугольников по площади (II)
priority_queue q;
q.push(Rectangle(1.0, 1.0));
q.push(Rectangle(3.0, 10.0));
q.push(Rectangle(2.0, 5.0));
q.push(Rectangle(10.0,

10.0));
while (!q.empty())
{
cout << q.top().A << " " << q.top().B << endl;
q.pop();
}

класса Rectangle идет выше
class RectangleCompare {
public:
bool operator() (const Rectangle& x,

const Rectangle& y)
{
return x.getArea() < y.getArea();
}
};
……
priority_queue,RectangleCompare> q;
…… //далее идет использование q