Главная станица
Курс лекций
Лабораторный практикум
Экзаменационные вопросы
Литература
Заочнику
Рабочая программа

 

Стандартная библиотека шаблонов (STL).

 

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

STL строится на основе шаблонов классов, и поэтому входящие в нее алгоритмы и структуры применимы почти ко всем типам данных.

Ядро библиотеки образуют три элемента: контейнеры, алгоритмы и итераторы.

Контейнеры (containers) - это объекты, предназначенные для хранения других элементов. Например, вектор, линейный список, множество.

Ассоциативные контейнеры (associative containers) позволяют с помощью ключей получить быстрый доступ к хранящимся в них значениям.

В каждом классе-контейнере определен набор функций для работы с ними. Например, список содержит функции для вставки, удаления и слияния элементов.

Алгоритмы (algorithms) выполняют операции над содержимым контейнера. Существуют алгоритмы для инициализации, сортировки, поиска, замены содержимого контейнеров. Многие алгоритмы предназначены для работы с последовательностью (sequence), которая представляет собой линейный список элементов внутри контейнера.

Итераторы (iterators) - это объекты, которые по отношению к контейнеру играют роль указателей. Они позволяют получить доступ к содержимому контейнера примерно так же, как указатели используются для доступа к элементам массива.

С итераторами можно работать так же, как с указателями. К ним можно применить операции *, инкремента, декремента. Типом итератора объявляется тип iterator, который определен в различных контейнерах. Существует пять типов итераторов:

  1. Итераторы ввода (input iterator) поддерживают операции равенства, разыменования и инкремента.

==, !=, *i, ++i, i++, *i++

Специальным случаем итератора ввода является istream_iterator.

  1. Итераторы вывода (output iterator) поддерживают операции разыменования, допустимые только с левой стороны присваивания, и инкремента.

++i, i++, *i = t, *i++ = t

Специальным случаем итератора вывода является ostream_iterator.

  1. Однонаправленные итераторы (forward iterator) поддерживают все операции итераторов ввода/вывода и, кроме того, позволяют без ограничения применять присваивание.

==, !=, =, *i, ++i, i++, *i

  1. Двунаправленные итераторы (bidirectional iterator) обладают всеми свойствами forward-итераторов, а также имеют дополнительную операцию декремента (--i, i--, *i--), что позволяет им проходить контейнер в обоих направлениях.

  2. Итераторы произвольного доступа (random access iterator) обладают всеми свойствами bidirectional-итераторов, а также поддерживают операции сравнения и адресной арифметики, то есть непосредственный доступ по индексу.

i += n, i + n, i -= n, i - n, i1 - i2, i[n], i1 < i2, i1 <= i2, i1 > i2, i1 >= i2

 

В STL также поддерживаются обратные итераторы (reverse iterators). Обратными итераторами могут быть либо двунаправленные итераторы, либо итераторы произвольного доступа, но проходящие последовательность в обратном направлении.

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

У каждого контейнера имеется определенный для него распределитель памяти (allocator), который управляет процессом выделения памяти для контейнера.

По умолчанию распределителем памяти является объект класса allocator. Можно определить собственный распределитель.

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

Определен специальный тип бинарного предиката для сравнения двух элементов. Он называется функцией сравнения (comparison function). Функция возвращает истину, если первый элемент меньше второго. Типом функции является тип Comp .

Особую роль в STL играют объекты-функции.

Объекты-функции - это экземпляры класса, в котором определена операция "круглые скобки" (). В ряде случаев удобно заменить функцию на объект-функцию. Когда объект-функция используется в качестве функции, то для ее вызова используется operator().

class less
{
public:
  bool operator()(int x, int y)
  {
    return x < y;
   }
};

В STL определены два типа контейнеров: последовательности и ассоциативные.

Ключевая идея для стандартных контейнеров заключается в том, что когда это представляется разумным, они должны быть логически взаимозаменяемыми. Пользователь может выбирать между ними, основываясь на соображениях эффективности и потребности в специализированных операциях. Например, если часто требуется поиск по ключу, можно воспользоваться map (ассоциативным массивом). С другой стороны, если преобладают операции, характерные для списков, можно воспользоваться контейнером list. Если добавление и удаление элементов часто производится в концы контейнера, следует подумать об использовании очереди queue, очереди с двумя концами deque, стека stack. По умолчанию пользователь должен использовать vector ; он реализован, чтобы хорошо работать для самого широкого диапазона задач.

Идея обращения с различными видами контейнеров и, в общем случае, со всеми видами источников информации - унифицированным способом ведет к понятию обобщенного программирования. Для поддержки этой идеи STL содержит множество обобщенных алгоритмов. Такие алгоритмы избавляют программиста от необходимости знать подробности отдельных контейнеров.

В STL определены следующие классы-контейнеры (в угловых скобках указаны заголовочные файлы, где определены эти классы):

  • bitset - множество битов <bitset.h>

  • vector - динамический массив <vector.h>

  • list - линейный список <list.h>

  • deque - двусторонняя очередь <deque.h>

  • stack - стек <stack.h>

  • queue - очередь <queue.h>

  • priority_queue - очередь с приоритетом <queue.h>

  • map - ассоциативный список для хранения пар ключ/значение, где с каждым ключом связано одно значение <map.h>

  • multimap - с каждым ключом связано два или более значений <map.h>

  • set - множество <set.h>

  • multiset - множество, в котором каждый элемент не обязательно уникален <set.h>

 

Типы:

  • value_type - тип элемента

  • allocator_type - тип распределителя памяти

  • size_type - тип индексов, счетчика элементов и т.д.

  • iterator - ведет себя как value_type *

  • reverse_iterator просматривает контейнер в обратном порядке

  • reference - ведет себя как value_type &

  • key_type - тип ключа (только для ассоциативных контейнеров)

  • key_compare - тип критерия сравнения (только для ассоциативных контейнеров)

  • mapped_type - тип отображенного значения

 

Итераторы:

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

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

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

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

 

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

  • front() - ссылка на первый элемент

  • back() - ссылка на последний элемент

  • operator [](i) - доступ по индексу без проверки

  • at(i) - доступ по индексу с проверкой

 

Включение элементов:

  • insert(p, x) - добавление х перед элементом, на который указывает р

  • insert(p, n, x) - добавление n копий х перед р

  • insert(p, first, last) - добавление элементов из [first:last] перед р

  • push_back(x) - добавление х в конец

  • push_front(x) - добавление нового первого элемента (только для списков и очередей с двумя концами)

 

Удаление элементов:

  • pop_back() - удаление последнего элемента

  • pop_front() - удаление первого элемента (только для списков и очередей с двумя концами)

  • erase(p) - удаление элемента в позиции р

  • erase(first, last) - удаление элементов из [first:last]

  • clear() - удаление всех элементов

 

Другие операции:

  • size() - число элементов

  • empty() - контейнер пуст

  • capacity() - память, выделенная под вектор (только для векторов)

  • reserve(n) - выделяет память для контейнера под n элементов

  • resize(n) - изменяет размер контейнера (только для векторов, списков и очередей с двумя концами)

  • swap(x) - обмен местами двух контейнеров

  • ==, !=, < операции сравнения

 

Операции присваивания:

  • operator =(x) - контейнеру присваиваются элементы контейнера х

  • assign(n, x) - присваивание контейнеру n копий элементов х (не для ассоциативных контейнеров)

  • assign(first, last) - присваивание элементов из диапазона [first:last]

 

Ассоциативные операции:

  • operator [](k) - доступ к элементу с ключом k

  • find(k) - находит элемент с ключом k

  • lower_bound(k) - находит первый элемент с ключом k

  • upper_bound(k) - находит первый элемент с ключом, большим k

  • equal_range(k) - находит lower_bound (нижнюю границу) и upper_bound (верхнюю границу) элементов с ключом k

 

Вектор vector в STL определен как динамический массив с доступом к его элементам по индексу.

template <class T, class Allocator = allocator<T> > class std::vector
{
// ...
};

где T - тип предназначенных для хранения данных. Allocator задает распределитель памяти, который по умолчанию является стандартным.

В классе vector определены следующие конструкторы:

explicit vector(const Allocator &a = Allocator());

explicit vector(size_type число, const T &значение = T(),
                const Allocator &a = Allocator());

vector(const vector<T, Allocator> &объект);

template<class InIter> vector(InIter начало, InIter конец,
                              const Allocator &a = Allocator());

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

vector<int> a;
vector<double> x(5);
vector<char> c(5, '*');
vector<int> b(a); // b = a

Для любого объекта, который будет храниться в векторе, должен быть определен конструктор по умолчанию. Кроме того, для объекта должны быть определены операторы < и == .


Для класса вектор определены следующие операторы сравнения:

==, <, <=, !=, >, >=.

Кроме этого, для класса vector определяется оператор индекса [].

  • Новые элементы могут включаться с помощью функций insert(), push_back(), resize(), assign().

  • Существующие элементы могут удаляться с помощью функций erase(), pop_back(), resize(), clear()

  • Доступ к отдельным элементам осуществляется с помощью итераторов begin(), end(), rbegin(), rend().

  • Манипулирование контейнером, сортировка, поиск в нем и тому подобное возможно с помощью глобальных функций файла - заголовка <algorithm.h>.

 

#include <iostream.h>
#include <vector.h>

using namespace std;

int main(void)
{
  vector<int> v;
  for(int i = 0; i < 10; i++)
  {
    v.push_back(i);
  }
  cout << "size = " << v.size() << "\n";
  for (int i = 0; i < 10; i++)
  {
    cout << v[i] << " ";
  }
  cout << endl;
  for (int i = 0; i < 10; i++)
  {
    v[i] = v[i] + v[i];
  }
  for (int i = 0; i < v.size(); i++)
  {
    cout << v[i] << " ";
  }
  cout << endl;
  return 0;
}

 Доступ к вектору через итератор

#include <iostream.h>
#include <vector.h>

using namespace std;

int main(void)
{
  vector<int> v;
  for (int i = 0; i < 10; i++)
  {
    v.push_back(i);
  }
  cout << "size = " << v.size() << "\n";
  vector<int>::iterator p = v.begin();
  while (p != v.end())
  {
    cout << *p << " ";
    p++;
  }
  return 0;
}

 Вставка и удаление элементов

#include <iostream.h>
#include <vector.h>

using namespace std;

int main(void)
{
  vector<int> v(5, 1);
  // вывод
  for (int i = 0; i < 5; i++)
  {
    cout << v[i] << " ";
  }
  cout << endl;
  vector<int>::iterator p = v.begin();
  p += 2;
  // вставить 10 элементов со значением 9
  v.insert(p, 10, 9);
  //вывод
  p = v.begin();
  while (p != v.end())
  {
    cout << *p << " ";
    p++;
  }
  // удалить вставленные элементы
  p = v.begin();
  p += 2;
  v.erase (p, p + 10);
  // вывод
  p = v.begin();
  while (p != v.end())
  {
    cout << *p << " ";
    p++;
  }
  return 0;
}

 Вектор содержит объекты пользовательского класса

#include <iostream.h>
#include <vector.h>
#include "student.h"

using namespace std;

int main(void)
{
  vector<STUDENT> v(3);
  v[0] = STUDENT("Иванов", 45.9);
  v[1] = STUDENT("Петров", 30.4);
  v[0] = STUDENT("Сидоров", 55.6);
  // вывод
  for (int i = 0; i < 3; i++)
  {
    cout << v[i] << " ";
  }
  cout << endl;
  return 0;
}

Ассоциативный массив содержит пары значений. Зная одно значение, называемое ключом (key), мы можем получить доступ к другому, называемому отображенным значением (mapped value).

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

V &operator [](const K &) возвращает ссылку на V, соответствующий K .

Ассоциативные контейнеры - это обобщение понятия ассоциативного массива.

Ассоциативный контейнер map - это последовательность пар (ключ, значение), которая обеспечивает быстрое получение значения по ключу. Контейнер map предоставляет двунаправленные итераторы.

Ассоциативный контейнер map требует, чтобы для типов ключа существовала операция < . Он хранит свои элементы отсортированными по ключу так, что перебор происходит по порядку.

Спецификация шаблона для класса map:

template<class Key, class T, class Comp = less<Key>,
         class Allocator = allocator<pair> >
class std::map;

В классе map определены следующие конструкторы:

explicit map(const Comp &c = Comp(), const Allocator &a = Allocator());

map(const map<Key, T, Comp, Allocator> &ob);

template<class InIter> map(InIter first, InIter last, const Comp &c = Comp(),
                           const Allocator &a = Allocator());

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

Определена операция присваивания:

map &operator =(const map &);

Определены следующие операции: ==, <, <=, !=, >, >= .

В map хранятся пары ключ/значение в виде объектов типа pair .

Создавать пары ключ/значение можно не только с помощью конструкторов класса pair, но и с помощью функции make_pair, которая создает объекты типа pair , используя типы данных в качестве параметров.

Типичная операция для ассоциативного контейнера - это ассоциативный поиск при помощи операции индексации ([]).

mapped_type &operator [](const key_type &K);

Множества set можно рассматривать как ассоциативные массивы, в которых значения не играют роли, так что мы отслеживаем только ключи.

template<classT, class Cmp = less<T>, class Allocator = allocator<T> >
class std::set
{
  //...
};

Множество, как и ассоциативный массив, требует, чтобы для типа T существовала операция "меньше" (< ). Оно хранит свои элементы отсортированными, так что перебор происходит по порядку.

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

Алгоритмы определены в заголовочном файле <algorithm.h> .

Ниже приведены имена некоторых наиболее часто используемых функций-алгоритмов STL.

  1. Немодифицирующие операции.
    for_earch() - выполняет операции для каждого элемента последовательности
    find() - находит первое вхождение значения в последовательность
    find_if() - находит первое соответствие предикату в последовательности
    count() - подсчитывает количество вхождений значения в последовательность
    count_if() - подсчитывает количество выполнений предиката в последовательности
    search() - находит первое вхождение последовательности как подпоследовательности
    search_n() - находит n-е вхождение значения в последовательность

  2. Модифицирующие операции.
    copy() - копирует последовательность, начиная с первого элемента
    swap() - меняет местами два элемента
    replace() - заменяет элементы с указанным значением
    replace_if() - заменяет элементы при выполнении предиката
    replace_copy() - копирует последовательность, заменяя элементы с указанным значением
    replace_copy_if() - копирует последовательность, заменяя элементы при выполнении предиката
    fill() - заменяет все элементы данным значением
    remove() - удаляет элементы с данным значением
    remove_if() - удаляет элементы при выполнении предиката
    remove_copy() - копирует последовательность, удаляя элементы с указанным значением
    remove_copy_if() - копирует последовательность, удаляя элементы при выполнении предиката
    reverse() - меняет порядок следования элементов на обратный
    random_shuffle() - перемещает элементы согласно случайному равномерному распределению ("тасует" последовательность)
    transform() - выполняет заданную операцию над каждым элементом последовательности
    unique() - удаляет равные соседние элементы
    unique_copy() - копирует последовательность, удаляя равные соседние элементы

  3. Сортировка.
    sort() - сортирует последовательность с хорошей средней эффективностью
    partial_sort() - сортирует часть последовательности
    stable_sort() - сортирует последовательность, сохраняя порядок следования равных элементов
    lower_bound() - находит первое вхождение значения в отсортированной последовательности
    upper_bound() - находит первый элемент, больший чем заданное значение
    binary_search() - определяет, есть ли данный элемент в отсортированной последовательности
    merge() - сливает две отсортированные последовательности

  4. Работа с множествами.
    includes() - проверка на вхождение
    set_union() - объединение множеств
    set_intersection() - пересечение множеств
    set_difference() - разность множеств

  5. Минимумы и максимумы.
    min() - меньшее из двух
    max() - большее из двух
    min_element() - наименьшее значение в последовательности
    max_element() - наибольшее значение в последовательности

  6. Перестановки.
    next_permutation() - следующая перестановка в лексикографическом порядке
    prev_permutation() - предыдущая перестановка в лексикографическом порядке

 

 

 
 
Hosted by uCoz