45. Последовательные контейнеры: vector, list, deque.

Класс векторов STL — это класс шаблона контейнеров последовательностей для хранения элементов заданного типа в линейном порядке и быстрого произвольного доступа к любому элементу. Он является наиболее подходящим типом контейнера для последовательности, когда на первом месте стоит производительность произвольного доступа.

Синтаксис

template <class Type, class Allocator = allocator<Type>>  
class vector

Примеры

template<
    class T,
    class Allocator = std::allocator<T>
> class vector;

std::vector — последовательный контейнер, инкапсулирующий массивы переменного размера.

namespace pmr {
    template <class T>
    using vector = std::vector<T, std::polymorphic_allocator<T>>;
}

std::pmr::vector псевдоним шаблона, использующего polymorphic allocator

Элементы хранятся непрерывно, а значит доступны не только через итераторы, но и через смещения, добавляемые к указателям на элементы (data() (std::vector::data - Возвращает указатель на базовый массив, выступающей в качестве элемента хранения. Указатель таков, что диапазон [data(); data() + size()) всегда действительный, даже если контейнер пуст. ) или же, для непустых массивов, — &vect[0]). Это означает, что указатель на элемент вектора может передаваться в любую функцию, ожидающую указатель на элемент массива.

Хранилище вектора обрабатывается автоматически, расширяясь и сужаясь по мере необходимости. Векторы обычно занимают больше места, чем статические массивы, поскольку некоторое количество памяти выделяется про запас на обработку будущего роста. Таким образом, память для вектора требуется выделять не при каждой вставке элемента, а только после исчерпания резервов. Общий объём выделенной памяти можно получить с помощью функции capacity(). Резервная память может быть возвращена системе через вызов shrink_to_fit().

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

Сложность (эффективность) обычных операций над векторами следующая:

• Произвольный доступ — постоянная O(1)

• Вставка и удаление элементов в конце — амортизированная постоянная O(1)

• Вставка и удаление элементов — линейная по расстоянию до конца вектора O(n)

Пример

#include <iostream>
#include <vector>

int main ( ) {
    // Создание вектора, содержащего целые числа
    std::vector<int> v = {7, 5, 16, 8};

    // Добавление ещё двух целых чисел в вектор
    v.push_back(25);
    v.push_back(13);

    // Проход по вектору с выводом значений
    for ( int n : v ) {
        std::cout << n << '\n';
    }
}

Прочая инфа здесь - http://ru.cppreference.com/w/cpp/container/vector https://msdn.microsoft.com/ru-ru/library/9xd04bzs.aspx

Класс списка STL — это класс шаблона контейнеров последовательностей для хранения элементов заданного типа в линейном порядке и быстрого произвольного доступа к любому элементу. Он является наиболее подходящим типом контейнера для последовательности, когда на первом месте стоит производительность произвольного доступа.

Синтаксис

template <class Type, class Allocator= allocator<Type>>  
class list

Список представляет собой контейнер, который поддерживает быструю вставку и удаление элементов из любой позиции в контейнере. Быстрый произвольный доступ не поддерживается. Он реализован в виде двусвязного списка. В отличие от std::forward_list(Forward list - контейнер, предоставляющий механизм вставки и удаления элементов из контейнера. Быстрый произвольный доступ не поддерживается. Реализован в виде однонаправленного списка и не имеет никаких накладных расходов по сравнению с аналогичной реализацией в C.) этот контейнер обеспечивает возможность двунаправленного итерирования, являясь при этом менее эффективным в отношении используемой памяти.

Пример

/ list_clear.cpp  
// compile with: /EHsc  
#include <list>  
#include <iostream>  

int main() {  
   using namespace std;  
   list <int> c1;  

   c1.push_back( 10 );  
   c1.push_back( 20 );  
   c1.push_back( 30 );  

   cout << "The size of the list is initially " << c1.size( ) << endl;  
   c1.clear( );  
   cout << "The size of list after clearing is " << c1.size( ) << endl;  
}

Прочая инфа здесь - http://ru.cppreference.com/w/cpp/container/list https://msdn.microsoft.com/ru-ru/library/802d66bt.aspx

Класс deque

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

Синтаксис

template <class Type,   
    class Allocator =allocator<Type>>  
class deque

std::deque (двусторонняя очередь) представляет собой последовательный индексированный контейнер, который позволяет быстро вставлять и удалять элементы с начала и с конца. Кроме того, вставка и удаление с обоих концов двусторонней очереди оставляет действительными указатели и ссылки на остальные элементы.

В отличие от std::vector, элементы дека не хранятся непрерывно: обычно реализован с помощью набора выделенных массивов фиксированного размера.

Хранилище дека обрабатывается автоматически, расширяясь и сужаясь по мере необходимости. Расширение дека дешевле, чем расширение std::vector, потому что оно не требует копирования существующих элементов в новый участок памяти.

Сложность (производительность) стандартных операций над двусторонней очередью следующая:

• Произвольный доступ - постоянная O(1)
• Вставка и удаление элементов с начала и с конца - амортизированная постоянная O(1)
• Вставка и удаление элементов - линейная O(n)

Пример

// deque_assign.cpp  
// compile with: /EHsc  
#include <deque>  
#include <iostream>  
#include <initializer_list>  

int main()  
{  
    using namespace std;  
    deque <int> c1, c2;  
    deque <int>::const_iterator cIter;  

    c1.push_back(10);  
    c1.push_back(20);  
    c1.push_back(30);  
    c2.push_back(40);  
    c2.push_back(50);  
    c2.push_back(60);  

    deque<int> d1{ 1, 2, 3, 4 };  
    initializer_list<int> iList{ 5, 6, 7, 8 };  
    d1.assign(iList);  

    cout << "d1 = ";  
    for (int i : d1)  
        cout << i;  
    cout << endl;  

    cout << "c1 =";  
    for (int i : c1)  
        cout << i;  
    cout << endl;  

    c1.assign(++c2.begin(), c2.end());  
    cout << "c1 =";  
    for (int i : c1)  
        cout << i;  
    cout << endl;  

    c1.assign(7, 4);  
    cout << "c1 =";  
    for (int i : c1)  
        cout << i;  
    cout << endl;  

}

Прочая инфа здесь - http://ru.cppreference.com/w/cpp/container/deque https://msdn.microsoft.com/ru-ru/library/22a9t119.aspx