Последовательные контейнеры
имеют разную внутреннюю организацию и почти одинаковый программный интерфейс.
Организация вектора
По стандарту библиотеки вектор представлен непрерывным участком памяти:
|
|
|
Организация двусторонней очереди
Очередь должна занимать непрерывную область памяти и прирастать порциями с обеих сторон.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Организация списка
Элементы списка располагаются в памяти произвольным образом.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Во всех контейнерах определены методы для получения сведений о размере контейнера:
|
size() |
Число элементов |
|
мax_size() |
Максимальный размер контейнера (порядка миллиарда эл-ов) |
|
empty() |
Булевская функция, показывает, пуст ли контейнер. |
Последовательные контейнеры поддерживают наборы операций:
|
Операция |
Метод(функция-член) |
vector |
deque |
list |
|
Вставка в начало |
push_front |
– |
+ |
+ |
|
Удаление из начала |
pop_ front |
– |
+ |
+ |
|
Вставка в конец |
push_back |
+ |
+ |
+ |
|
Удаление из конца |
pop_ back |
+ |
+ |
+ |
|
Вст. в произв. место |
insert |
O(n) |
O(n) |
+ |
|
Удал. из произв. места |
erase |
O(n) |
O(n) |
+ |
|
Доступ к элементу |
[ ] , at |
+ |
+ |
– |
O(n) – линейное время выполнения операции.
Контейнер веКтор
Параметр шаблона – тип хранимых элементов.
=создание пустого контейнера:vector <char> v1;
= создание контейнера, заполненного одним значением:
vector <char> v2 (10); // заполнен символами ‘\0’
vector <char> v3 (10, ‘a’); // заполнен символами ‘a’
= создание контейнера, заполненного элементами уже существующего контейнера:
vector <char> v4 (v3); // либо v4 =v3;
=создание контейнера, заполненного частью элементов уже существующего контейнера:
char S[ ]=”abcd”;
vector <char> v5 (S,S+3); // “abc”
//здесь параметрами конструктора служат указатели на первый элемент и место в памяти сразу за последним элементом.
= аналогичный пример заполнения контейнера вектор из массива:
int arr[] = { 100, 110, 120, 130 }; //an array of ints
vector<int> v(arr, arr+4); // initialize vector to array
= вывести на экран размер вектора:
cout<< v.size()<<endl;
= вывести на экран содержимое вектора:
for (int i=0; i< v.size();i++) cout<<v[i]<<” “;
Итератор – аналог указателя на элемент. Он используется для просмотра контейнера в прямом и обратном направлении. Поле типа iterator есть в любом контейнерном классе. Итератор должен уметь ссылаться на элемент контейнера и реализовывать операцию перехода к его следующему элементу. При промощи итератора можно просматривать контейнеры, не заботясь о фактических типах данных, используемых для доступа к данным. Итераторы бывают однонаправленные (прямой и обратный),двунаправленные и произвольного доступа. Для вектора итератор однонаправленный. Для итераторов разных категорий определены следующие операции:
для однонаправленных – *I , ++I, I++, ==, !=;
для двунаправленных – еще и –I, I––;
для произвольного доступа – еще и I+n,I-n,I<J,I>J, +=,-=;
Для просмотра элементов контейнера определены методы:
|
iterator begin() |
указывает на первый элемент |
|
iterator end() |
указывает на элемент, следующий за последним |
|
reverse_ iterator rbegin() |
указывает на первый элемент в обратной последовательности |
|
reverse_ iterator rend() |
указывает на элемент, следующий за последним, в обратной последовательности |
= вывод злементов вектора при помощи итератора:
for (vector <char>:: iterator i=v.begin() ; i!=v.end() ; i++)
cout<< *i<<” “;
Сравнение с граничным значением выполнять с помощью операции ‘!= ‘ !
Итераторы контейнеров vector и deque относятся к категории прямого доступа. Итераторы контейнера list относятся к категории двунаправленных.
Итератор вектора -прямого доступа, для него определена операция индексации:
vector <char> v=”abcd”;
vector<char>:: iterator M=v.begin();
M[0]; // первый элемент
M[1]; // второй элемент
M = v.end();
M[-1];// последний элемент
cout<< M[0]<< M[1]<< M[2]<< M[-1]<<’+’<<endl;
ПРИМЕР
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;