Большинство компьютеров предназначено для обработки информации. В качестве данных могут выступать самые разные виды характеристик реального мира: досье на работников, информация об имеющихся па складе запасах, текстовый документ, результат научных экспериментов и т. д. Что бы данные собой ни представляли, их надо каким-либо способом хранить в памяти (на жестком диске, в текстовом или бинарном формате, в оперативной памяти и т.д.). Термин структура данных говорит о том, как хранится информация в памяти компьютера. Структура данных (data structure) — это способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию. Простейшая структура данных, которая поддерживается всеми языками программирования – массив. В C/ С++ есть статические массивы (их не меняется в процессе работы) и динамические массивы. Динамический массив располагается в динамической памяти, и его размерность может определяться и меняться в процессе работы программы. Его главным достоинством является то, что можно получить быстрый доступ к содержимому массива по индексу. Однако, для многих задач массив не является оптимальной структурой данных. Например, для тех задач, которые требуют большого количества вставок и удалений элементов. Поэтому существуют и другие структуры данных. В частности списки допускают быструю вставку и удаление элементов. Существуют еще графы, деревья, стеки, очереди, хеш-таблицы, словари, пирамиды и много других структур данных. Ни одна структура данных не является универсальной и не может подходить для всех целей, поэтому важно знать преимущества и ограничения, присущие некоторым из них.

Однако все структуры данных не реализованы как массивы с использованием «чистых» конструкций языка. В тоже время приходится их использовать довольно часто. Поэтому их реализация обеспечивается дополнительно в так называемых библиотеках поддержки. Они разрабатываются самими программистами, но с таким расчетом, чтобы сделать их универсальными для большинства задач.

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

Алгоритм (algorithm) — это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующих входные величины в выходные. Существует в программировании множество типовых задач, которые приходится решать в большинстве приложений, к какой бы сфере деятельности они не относились. Это такие задачи, как сортировка, поиск по определенному критерию, копирование, кратчайший маршрут в графе и т.д. Поэтому имеет смысл разработать алгоритмы так, чтобы их можно было использовать многократно и в различных приложениях. Для этого они реализованы в отдельных библиотеках.

Наиболее распространенной библиотекой, в которой содержатся как структуры данных, так и алгоритмы, обрабатывающие данные структуры является стандартная библиотека шаблонов (Standard Template Library, STL). Она включена в стандарт ANSI/ISO и поставляется с компилятором С++.

По своей сути STL – это сложный набор шаблонных классов и шаблонных функций, реализующих часто используемые структуры данных и алгоритмы. Эта библиотека включает поддержку векторов, списков, ассоциативных массивов, очередей, стеков. Кроме того, она предоставляет множество алгоритмов, таких как сортировка, поиск, слияние, оперирующих с этими структурами данных. Поскольку STL состоит из шаблонных классов и шаблонных функций, структуры данных и алгоритмы могут применяться почти к любым типам данных.

STL организована на основе трех фундаментальных элементов: контейнеры, обобщенные алгоритмы и итераторы.

Контейнеры

Контейнеры в STL представляют собой объекты (шаблонные классы), которые служат для хранения других объектов и организуют эти данные в структуры. В STL имеется две категории контейнеров: контейнеры последовательностей и отсортированные ассоциативные контейнеры.

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

vector<T>. Обеспечивает произвольный доступ к последовательности переменной длины (произвольный доступ означает, что время, требуемое для достижения i-го элемента, представляет собой константу, т.е. оно не зависит от конкретного значения i), с амортизированным константным временем вставки и удаления в конце последовательности.

deque<T>. Также обеспечивает произвольный доступ к последовательности переменной длины, с амортизированным константным временем вставки и удаления с обоих концов последовательности.

list<T>. Обеспечивает линейное время доступа к последовательности переменной длины (O(N) , где N – текущая длина), но с константным временем вставки и удаления в любом месте последовательности.

Обычный массив T a[N] также рассматривается как контейнер. Все выше перечисленные контейнеры организуют набор объектов типа T в строго линейную последовательность.

Ассоциативный контейнер – это уже несколько иная организация данных. Данные располагаются не последовательно, доступ к ним осуществляется посредством ключей. Ключи – это просто номера строк, они обычно используются для выстраивания хранящихся элементов в определенном порядке и модифицируются контейнерами автоматически. Примером может служить обычный орфографический словарь, где слова сортируются по алфавиту. Вы просто вводите нужное слово (значение ключа), например «арбуз», а контейнер конвертирует его в адрес этого элемента в памяти. Если известен ключ, доступ к данным осуществляется очень просто. В STL имеется два типа ассоциативных контейнеров: множества и отображения. И те и другие ассоциативный контейнеры хранят данные в виде дерева, что позволяет осуществлять быструю вставку, удаление и поиск данных.

set<Key>. Поддерживает уникальные ключи (содержит не более одного значения каждого ключа) и обеспечивает быструю выборку искомого ключа.

multiset<Кеу>. Поддерживает дублированные ключи (возможно наличие нескольких копий одного и того же значения ключа) и обеспечивает быструю выборку искомого ключа.

map<Key,Т>. Поддерживает уникальные ключи (типаKey) и обеспечивает быструю выборку другого типаT на основе ключа.

multimap<Key,Т>. Поддерживает дублированные ключи (типа Key) и обеспечивает быструю выборку другого типа T на основе ключа.

Примером отсортированного ассоциативного контейнера может служить map<string,unsigned int>, который может использоваться для хранения имен и телефонных номеров. По данному имени такое отображение обеспечивает быструю выборку телефонного номера.