Последовательные контейнеры. Деки

   
На этом шаге мы рассмотрим работу с деками.

   
Термин "дек" (deque) происходит от сокращения фразы "double-ended queue"
(двусторонняя очередь). Дек представляет собой динамический массив, реализованный таким образом,
что может расти в обоих направлениях. Таким образом, операции вставки элементов в конец и в начало коллекции
выполняются очень быстро, а вставка в середину занимает больше времени, потому что требует перемещения
элементов.

   
В следующем примере мы объявляем дек для вещественных чисел, вставляем в начало контейнера элементы от
1.1 до 6.6, а затем выводим значения элементов дека.

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iostream>
#include <deque>
#include <conio.h> //необходимо для getch()
#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;
std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main(int argc, char* argv[])
{
  deque<float> coll; // Дек с вещественными элементами
  // Вставка в начало элементов со значениями от 1.1 до 6.6
  for (int i=1; i<=6; ++i) {
    coll.push_front(i*1.1);  // Вставка в начало дека
  }  
  // Вывод элементов, разделенных пробелами
  cout << ToRus("Элементы дека: ");
  for (int i=0; i<coll.size(); ++i) {
    cout << coll[i] << ' ';
  }
  cout << endl;

  getch();
  return 0;
}
//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

   
Следующая директива включает заголовочный файл для работы с деками:

  #indude <deque>

   
Показанное ниже объявление создает пустую коллекцию вещественных чисел:

  deque<float> coll;

   
Функция push_front() предназначена для вставки элементов:

  coll.push_front(i*1.1);

   
Функция push_front() вставляет элементы в начало коллекции. Обратите внимание: при таком способе вставки
элементы хранятся в контейнере в обратном порядке, потому что каждый новый элемент вставляется перед элементами,
вставленными ранее. Следовательно, программа выведет следующий результат:


Рис.1. Результат работы приложения

   
Элементы также могут вставляться в конец дека функцией push_back(). Функция push_front() не
поддерживается векторами, поскольку в этом типе контейнера она будет выполняться слишком долго (при вставке
элемента в начало вектора придется переместить все существующие элементы). Обычно контейнеры STL содержат
только функции, обеспечивающие "хорошую" эффективность (то есть выполняемые с постоянной или
логарифмической сложностью). Это сделано для того, чтобы предотвратить случайные вызовы неэффективных функций.

   
На следующем шаге мы рассмотрим списки.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий