Контейнеры (Коллекции). Stl бибилиотеки. Линейные контейнеры array

Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.
Стандартная библиотека шаблонов до включения в стандарт C++ была сторонней разработкой, в начале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода/вывода (iostream), подраздел Си и др.).
Проект под названием STLPort, основанный на SGI STL, осуществляет постоянное обновление STL, iostream и строковых классов. Некоторые другие проекты также занимаются разработкой частных применений стандартной библиотеки для различных конструкторских задач. Каждый производитель компиляторов C++ обязательно поставляет какую-либо реализацию этой библиотеки, так как она является очень важной частью стандарта и широко используется.
Архитектура STL была разработана Александром Степановым и Менг Ли.
char data[] = "Hello, world!";
// Диапазон с 7-го элемента по 12-й содержит слово "world".
auto begin = data + 7; // Начало диапазона -- первый итератор в паре.
auto end = data + 12; // Конец диапазона -- второй итератор в паре.
assert(end - begin == 5); // Расстояние между итераторами == количеству элементов в диапазоне.
// Перечислим подряд все элементы диапазона.
while (begin != end)
cout.put(*begin++); // > world

1. Структура библиотеки

В библиотеке выделяют пять основных компонентов:

• 
  1. Контейнер (container) — хранение набора объектов в памяти.
  
• 
  2. Итератор (iterator) — обеспечение средств доступа к содержимому контейнера.
  
• 
  3. Алгоритм (algorithm) — определение вычислительной процедуры.
  
• 
  4. Адаптер (adaptor) — адаптация компонентов для обеспечения различного интерфейса.
  
• 
  5. Функциональный объект (functor) — сокрытие функции в объекте для использования другими компонентами.
  

Разделение позволяет уменьшить количество компонентов. Например, вместо написания отдельной функции поиска элемента для каждого типа контейнера обеспечивается единственная версия, которая работает с каждым из них, пока соблюдаются основные требования.
В зависимости от внутреннего устройства контейнера не все характерные для указателей операции могут быть выполнены эффективно на его итераторах. Например, при доступе к связному списку обращение по числовому индексу может потребовать значительного числа операций. Итераторы могут не поддерживать неэффективные операции. Чтобы выделить характерные виды итераторов, в Стандарте C++ определены “категории итераторов”. Принадлежность итератора той или иной категории определяется набором поддерживаемых им операций.

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