C++ std::deque (контейнер з двома кінцями)

Шаблонний клас std::deque призначений для утримування послідовності елементів певного типу. Deque розшифровується як double-ended queue, тобто черга з двома кінцями. Що дозволяє в даному контейнері додавати і видаляти елементи послідовності з двох сторін - початку послідовності і її кінця.

template < class T, class Alloc = allocator<T> > class deque ;

Параметр шаблону T вказує на тип елементів, послідовність яких даний контейнер буде утримувати. Параметр Alloc призначений для вказування об'єкту, який відповідає за виділення нових примірників елементів. Постачальники бібліотеки STL реалізовують std::deque різними способами, зазвичай у формі динамічного масиву. Але в будь-якому випадку, контейнер дозволяє перебирати елементи своєї послідовності через ітератори вільного доступу (random access iterators), разом з автоматичним управлінням пам'яті при вставці і видаленні нових елементів. Клас deque надає функціональність подібну до класу std::vector, проте з ефективною вставкою елементів не тільки у кінець послідовності, а й на початок. Але на відміну від вектора, дека не гарантує збереження усіх її елементів в одному масиві пам'яті, тобто отримання доступу до елементів деки, використовуючи операції з вказівниками, може спричинити невизначену поведінку (undefined behavior).

Нутрощі класу

explicit deque (const allocator_type& alloc = allocator_type());

/* конструктор з заповненням */
explicit deque (size_type n, 
                const value_type& val = value_type(),
                const allocator_type& alloc = allocator_type()) ;

/* конструктор з копіюванням 
** проміжку послідовності */
template <class InputIterator>
  deque (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type()) ;

/* конструктор копіювання */
deque (const deque& x) ;

Конструктори класу. параметр alloc призначений для вказування об'єкту, який відповідає за виділення нових елементів послідовності. Параметр n призначений для вказування кількості новийх елементів конструктору заповнення, які будуть вставлятися в контейнер з значенням val. Параметри first i last призначені для вказування ітераторів, які виділяють проміжок елементів [first, last) одного контейнеру, що будуть копіюватися в новостворений об'єкт класу deque. Параметр x конструктору копіювання призначений для вказування об'єкта з якого будуть копіюватися послідовність елементів при створені даного.

/* копіювання */
template <class InputIterator>
  void assign (InputIterator first, InputIterator last);

/* заповнення */
void assign (size_type n, const value_type& val) ;

Даний метод призначений для присвоєння об'єкту проміжку значень [first, last), або заповнення елементом з значенням val, n разів. Після виклику даного методу, в контейнері будуть розміщуватись тільки вказані елементи.

      reference at (size_type n) ;
const_reference at (size_type n) const ;

Позволяє отримати посилання (reference) до елемента послідовності за індексом n. Метод перевіряє адекватність параметру відносно розміру поточного контейнера, і, в разі не відповідності, метод генерує виключення out_of_range.

      reference back() ;
const_reference back() const ;

Повертає посилання (reference) на останній елемент послідовності. Виклик даного методу на пустому контейнері спричиняє невизначену поведінку.

      iterator begin () ;
const_iterator begin () const ;

Повертає ітератор, який вказує на перший елемент послідовності. Виклик даного методу на пустій послідовності, спричиняє отримання ітератора, який не можна розйменовувати.

const_iterator cbegin () const noexcept ;

Повертає константний ітератор на перший елемент послідовнсості. Якщо контейнер пустий ітератор не повинен розйменовуватися.

const_iterator cend () const noexcept ;

Повертає константний ітератор, що вказує на неіснуючий елемент, який стоїть за останнім елементом послідовності контейнера. Він не повинен розйменовуватися.

void clear() ;

Очищає поточний контейнер, знищуючи усі його елементи.

bool empty() const ;

Метод повертає значення true, якщо примірник контейнера пустий.

      iterator end () ;
const_iterator end () const ;

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

iterator erase (iterator position) ;
iterator erase (iterator first, iterator last) ;

Видаляє елементи з послідовності. position вказує на один елемент, який необхідно видалити. Ітератори first і last спирчиняють вилалення проміжку елементів [first, last).

      reference front () ;
const_reference front () const ;

Повертає посилання (reference) на перший елемент послідовності. Виклик даного методу з пустого контейнера спричиняє невизначену поведінку.

allocator_type get_allocator () const ;

Повертає копію об'єкта, який відповідальний за створення нових примірників елементів контейнера.

/* множина елементів з одного значення */
iterator insert (iterator position, const value_type& val) ;

/* множина елементів в позицію */
    void insert (iterator position, size_type n, const value_type& val) ;

/* послідовність елементів */
template <class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last) ;

Вставляє алементи в послідовнсть. position вказує на позицію, перед якою повинна виконуватись вставка нових елементів. val значення, яке будуть мати нові елементи контейнера. Параметр методу n призначений для вказування кількості елементів, які необхідно вставляти у послідовнсть. Параметри-ітератори first i last призначені для обмеження послідовності іншого контейнера (також іншого класу), значення яких буде копіюватися у поточний контейнер.

size_type max_size () const ;

Повертає максимальне число елементів, які об'єкт може утримати.

deque& operator = (const deque& x) ;

Оператор присвоєння. Присвоює новий всіст з контейнера x поточному.

      reference operator [] (size_type n) ;
const_reference operator [] (size_type n) const ;

Оператор доступу до елементів. Параметр n вказує на індекс елемента, який необхідно отримати. Повертає посилання на елемент (reference). Даний оператор не перевіряє власні межі, як це робить метод at(), тому отримання доступу до елементу поза межами контейнера викликає невизначену поведінку.

void pop_back () ;

Видаляє останній елемент, зменшуючи його розмір на одиницю.

void pop_front () ;

Видаляє перший елемент контейнера, зменшуючи його розмір на одиницю.

void push_back (const value_type& val) ;

Додавання елементу з значенням val у кінець послідовностію.

void push_front (const value_type& val) ;

Вставляє елемент з значенням val у початок послідовності.

      reverse_iterator rbegin () ;
const_reverse_iterator rbegin () const ;

Повертає ітератор зворотнього перебору, який вказує на останній елемент послідовності. Кожен інкремент даного ітератора спричиняє його приближення до першого елементу, а декремент, приближує ітератор на останній елемент.

      reverse_iterator rend () ;
const_reverse_iterator rend () const ;

Повертає ітератор зворотнього перебору, який вказує на неіснуючий елемент, що стоїть перед першим елементом послідовності.

void resize (size_type n, value_type val = value_type()) ;

Змінює розмір контейнеру, встановлюючи розмір у n елементів. Якщо кількість елементів менша чим параметр n, контейнер збільшується за рахунок вставки у кінець послідовності нових елементів з значенням val. Якщо контейнер містить більше елементів ніж це вказано за допомогою параметра n - видаляються елементи з кінця послідовності, поки їх кількість не буде дорівнювати n.

size_type size () const ;

Метод повертає кількість елементів в контейнері.

void swap (deque& x) ;

Виконує обмін внутрішніми вказівниками між двома деками, в результаті чого усі елементи деки x переходять у власність контейнеру, з якого викликається метод, і його елементи переходять до x. Усі ітератори і вказівники залишаються валідними.

Приклад

Розглянемо приклад використання контейнеру.

#include <deque> /* клас деки */
#include <iostream> /* об'єкт cout */
using namespace std ; /* друкуємо усе без std */

/* головна функція програми */
int main (int argc, char** argv)
{
  /* створюємо піддослідну деку */
  deque<int> iElems ;
  
  /* змінюємо розмір деки,
  ** вставляючи новий один елемент з значенням 0,
  ** використовуючи метод assign */
  iElems.assign (1, 0) ;
  
  /* заповнюємо послідовність за допомогою методів
  ** push_back i push_front */
  for (unsigned int iter=1; iter<5; ++iter)
  {
    /* додаємо елемент в кінець черги */
    iElems.push_back  ( iter) ;
    /* додаємо елемент на початок послідовності */
    iElems.push_front (-iter) ;
  }
  
  /* виводимо результат заповнення на екран, 
  ** використовуючи ітератори класу deque 
  ** за одно виводимо і адреси комірок пам'яті які відповідають 
  ** за утримування елементів типу int */
  for (deque<int>::iterator iter=iElems.begin(); iter<iElems.end(); ++iter)
  {
    cout << "address: " << &(*iter) << " ; value: " << *iter << endl ; 
  }
  
  cout << "sizeof(int): " << sizeof (int) << endl ;
  
  return 0 ;
}

Вивід програми:

Як бачимо з зображення, адреси комірок пам'яті не розміщені послідовно: одна область відповідає за перший елемент (-4) до п'ятого (0), і інша вміщує послідовність усіх інших елементів. Тобто, якщо б ми виконували перебір елементів деки за допомогою вказівників на тип int, тоді можливо ми б "зловили" сигнал SIGSEGV (segmentation fault), або програма продовжила виводити у термінал випадкові дані, які знаходяться за масивом.