Дискретная математика / Практика / СПРАВОЧНИК ПО КОНТЕЙНЕРНЫМ КЛАССАМ

СПРАВОЧНИК ПО КОНТЕЙНЕРНЫМ КЛАССАМ

Эффективного использования памяти можно достичь, используя контейнерный классы, например, класс вектор. Предварительно определение контейнерного класса vector должно быть подключено к тексту программы.

Тип элементов вектора задаётся при описании переменной этого типа. Например,

vector <int> V ;

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

vector <int> V (n) ;

vector <int> V (n, c) ;

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

vector <int> V (a, a+n) ;

выделит динамическую память для вектора V и заполнит его n элементами массива a. Как и для других классов, для класса вектор определён конструктор копирования, так инструкция

vector <int> V ( Y ) ;

создаст вектор V, который инициализируется элементами вектора Y.

Приведём список функций-членов контейнерных классов, причём, если функция является общей для нескольких контейнерных классов, то при её описании используем термин контейнер для названия объекта, для которого она используется.

Альтернативой конструктору с инициализацией для присваивания значений вектору является метод assign:

assign (n, val) – присвоит элементам вектора n копий элемента val;

assign (itfirst, itlast) – присвоит элементам вектора последовательность элементов, задаваемую любым диапазоном подходящего типа.

Количество элементов контейнера можно определить с помощью функции-члена класса size(). Функция empty() выдаёт значение true, если контейнер пуст. Изменить размер вектора можно с помощью перегружаемой функции-члена resize, параметрами которой являются:

• size_n – новый размер контейнера (обязательный параметр);

• val – значение, которое присваивается всем новым элементам контейнера.

Если значение size_n превышает текущий размер контейнера, то в конец контейнера добавятся новые элементы, значения которых определяется по умолчанию или задаётся параметром val. Если значение size_n меньше текущего размера контейнера, то лишние элементы удаляются из его конца.

Обращение к i-му элементу вектора осуществляется также, как и к элементу массива по индексу, оператором [ ] (без проверки выхода индекса за границы вектора). Индексированный доступ с проверкой индекса выполняет функция at(i). Кроме того функции front() и back() осуществляют доступ к первому и последнему элементу контейнера.

Итераторы являются аналогами указателей для контейнерных классов, для контейнеров определены следующие итераторы:

begin() – указывает на первый элемент;

end() – указывает на элемент, следующий за последним;

rbegin() – указывает на первый элемент в обратной последовательности;

rend()– указывает на элемент, следующий за последним в обратной последовательности.

Переменная типа итератор вектора из целых элементов определяется в программе инструкцией vector <int> :: iterator pv; .

Вставить элемент в конец контейнера можно с помощью функции push_back(el), удалить последний элемент – функцией pop_back(). Функция insert позволяет вставить элемент или группу элементов в произвольное место контейнера, задаваемое итератором pos (вставка выполняется перед элементом, на который указывает итератор). Возможны следующие варианты данной перегружаемой функции:

insert (pos, val) – вставляет элемент val;

insert (pos, n, val) – вставляет n копий элемента val;

insert (pos, itfirst, itlast) – вставляет последовательность элементов, задаваемую любым диапазоном подходящего типа. Например, инструкции:

V.insert ( V.begin(), c) – вставит элемент c в начало вектора V;

V.insert ( V.end(), 3, c) – вставит 3 копии элемента c в конец вектора V;

V.insert (V.begin()+2, a, a+3) – вставит первые 3 элемента массива a перед 2-м элементом вектора V.

Удалить элементы из контейнера можно с помощью метода erase, существуют следующие варианты метода:

erase (pos) – удаление элемента, задаваемого итератором pos;

erase (itfirst, itlast) – удаление элементов, находящихся в интервале, задаваемым итераторами itfirst, itlast.

Метод clear() позволяет очистить контейнер.

Следует помнить, что при любом изменении контейнера происходит перераспределение динамической памяти и некоторые итераторы, запомненные ранее, становятся неопределёнными. Поэтому часто после таких процедур требуется повторное вычисление изменённых итераторов. Например, так как элементы класса вектор находятся в непрерывной области памяти, то при увеличении размера вектора для него выделяется новая область и все прежние итератора становятся неопределёнными (плата за возможность индексированного доступа). Однако метод reserve(n) позволяет зарезервировать область памяти заданного размера для потенциального расширения вектора, тогда пока размер вектора не превысит размер выделенной памяти, её перераспределение не выполняется.

Методы, используемые для списков (list) и очередей с двумя концами (deque):

push_front(el) – добавление элемента в начало контейнера;

pop_front() – удаление первого элемента контейнера.