Инструменты пользователя

Инструменты сайта


examination:oop:question52

Контейнеры: назначение, классификация, основные операции.

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

Контейнеры библиотеки STL можно разделить на четыре категории: последовательные, ассоциативные, контейнеры-адаптеры и псевдоконтейнеры.

Контейнер - Описание

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

vector C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за . Добавление-удаление элемента в конец vector занимает амортизированное время, та же операция в начале или середине vector — . Стандартная быстрая сортировка за . Поиск элемента перебором занимает . Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.

list Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из-за большего времени доступа к элементу. Доступ по индексу за . В любом месте контейнера вставка и удаление производятся очень быстро — за .

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

Ассоциативные контейнеры

set Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.

multiset То же что и set, но позволяет хранить повторяющиеся элементы.

map Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.

multimap То же что и map, но позволяет хранить несколько одинаковых ключей.

Контейнеры-адаптеры

stack Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца. queue Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.

priority_queue Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.

Псевдоконтейнеры

bitset Служит для хранения битовых масок. Похож на vector<bool> фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.

basic_string Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности. Элементы должны быть POD'ами. Определена конкатенация с помощью +.

valarray Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Определены операции над двумя valarray и над valarray и скаляром (поэлементные). Эти операции возможно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками SIMD.

Ниже приведен краткий перечень доступных методов с описанием

Метод - Описание

Конструкторы

vector::vector Конструктор по умолчанию. Не принимает аргументов, создает новый экземпляр вектора

vector::vector(const vector& c) Конструктор копии по умолчанию. Создает копию вектора c O(n) (выполняется за линейное время, пропорциональное размеру вектора c)

vector::vector(size_type n, const T& val = T()) Создает вектор с n объектами. Если val объявлена, то каждый из этих объектов будет инициализирован ее значением; в противном случае объекты получат значение конструктора по умолчанию типа T.

vector::vector(input_iterator start, input_iterator end) Cоздает вектор из элементов, лежащих между start и end

Деструктор

vector::~vector Уничтожает вектор и его элементы

Операторы

vector::operator= Копирует значение одного вектора в другой.

vector::operator== Сравнение двух векторов

Доступ к элементам

vector::at Доступ к элементу с проверкой выхода за границу

vector::operator[] Доступ к определенному элементу

vector::front Доступ к первому элементу

vector::back Доступ к последнему элементу

Итераторы

vector::begin Возвращает итератор на первый элемент вектора

vector::end Возвращает итератор на место после последнего элемента вектора

vector::rbegin Возвращает reverse_iterator на конец текущего вектора.

vector::rend Возвращает reverse_iterator на начало вектора.

Работа с размером вектора

vector::empty Возвращает true, если вектор пуст

vector::size Возвращает количество элементов в вектора

vector::max_size Возвращает максимально возможное количество элементов в векторе

vector::reserve Устанавливает минимально возможное количество элементов в векторе

vector::capacity Возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места.

vector::shrink_to_fit Уменьшает количество используемой памяти за счет освобождения неиспользованной (C++11)

Модификаторы

vector::clear Удаляет все элементы вектора

vector::insert Вставка элементов в вектор Вставка в конец, при условии, что память не будет перераспределяться — O(1), в произвольное место — O(n)

vector::erase Удаляем указанные элементы вектора (один или несколько)

vector::push_back Вставка элемента в конец вектора

vector::pop_back Удалить последний элемент вектора

vector::resize Изменяет размер вектора на заданную величину

vector::swap Обменять содержимое двух векторов

В дополнение к функциям прямого доступа к элементам, описанными выше, элементы вектора можно получить посредством итераторов.

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

Вектор использует наиболее функционально богатый тип итераторов — RandomAccessIterator (итератор произвольного доступа), который позволяет обходить контейнер в любом порядке, а также изменять содержимое вектора в процессе обхода. Однако, при изменении вектора итератор может стать недействительным.

Пример подсчета суммы элементов вектора при помощи итераторов:

vector<int> the_vector;
    vector<int>::iterator the_iterator;
 
    for (int i=0; i < 10; i++) {
        the_vector.push_back(i);
    }
    int total = 0;
    the_iterator = the_vector.begin();
    while (the_iterator != the_vector.end()) {
      total += *the_iterator; /* Обратите внимание, что доступ к элементу можно получить посредством разыменования итератора */
      ++the_iterator;
    }
    cout << "Итого=" << total << endl;

Результат: Итого=45

Следующий пример демонстрирует различные техники с участием вектора и алгоритмов стандартной библиотеки C++, в частности, перемешивание, сортировка, нахождение наибольшего элемента, а также удаление из вектора с использованием идиомы erase-remove.

#include <iostream>
#include <vector>
#include <algorithm>  // sort, max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater, bind2nd
 
// Используется для удобства. В реальных программах используйте с осторожностью
using namespace std;
 
int main() {
  int arr[4] = {1, 2, 3, 4};
  // Инициализирование вектора с использованием массива
  vector<int> numbers(arr, arr+4);
  // Добавляем числа в вектор
  numbers.push_back(5);
  numbers.push_back(6);
  numbers.push_back(7);
  numbers.push_back(8);
  // Теперь вектор выглядит так: {1, 2, 3, 4, 5, 6, 7, 8}
 
  // Произвольно перемешиваем элементы
  random_shuffle(numbers.begin(), numbers.end());
 
  // Получаем максимальный элемент, сложность O(n)
  vector<int>::const_iterator largest = max_element( numbers.begin(), numbers.end() );
 
  cout << "Наибольший элемент " << *largest << endl;
  cout << "Индекс этого элемента " << largest - numbers.begin() << endl;
 
  // Сортируем элементы, сложность O(n log n)
  sort(numbers.begin(), numbers.end());
 
  // Находим позицию цифры 5 в векторе, сложность O(log n)  
  vector<int>::const_iterator five = lower_bound(numbers.begin(), numbers.end(), 5);  
 
  cout << "Цифра 5 расположена под индексом " << five - numbers.begin() << endl;
 
  // Удаляем все элементы больше 4-х 
  numbers.erase(remove_if(numbers.begin(), numbers.end(), 
    bind2nd(greater<int>(), 4)), numbers.end() );
 
  // Печатаем оставшиеся
  for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << ' ';
  }
 
  return 0;
} 

Вывод будет содержать:

Наибольший элемент 8

Индекс этого элемента 6 (зависит от реализации)

Цифра 5 расположена под индексом 4

1 2 3 4

examination/oop/question52.txt · Последние изменения: 2014/01/15 08:22 (внешнее изменение)