Standart template library (STL). Продолжение.

1. Инвалидация итераторов.

Инвалидацией итератора (от англ. invalid) называется процесс, при котором итератор перестает указывать туда, куда он должен указывать, т.е. итератор становится невалидным.
В разных контейнерах инвалидация происходит в разные моменты:
• List: при удалении элемента происходит инвалидация итераторов, указывающих на этот элемент.
• Vector: при удалении — инвалидация итератора удаляемого элемента и всех после него; при добавлении — инвалидация всех итераторов (т.к. может произойти переаллокация внутреннего буфера). Если при добавлении элемента в конец capacity > size, то инвалидации не происходит.
• Deque: при удалении первого и последнего элементов — инвалидация только соответствующих итераторов; при добавлении или удалении элементов в середине — инвалидация всех итераторов.

	List	Vector	Deque
Удаление	Соответствующий итератор	Соответствующий итератор и все после него	При удалении первого и последнего элементов — только соответствующие итераторы; при удалении в середине — всех итераторов
Добавление	Конкретный итератор	Все итераторы (если про capacity и size ничего не известно)	см. удаление

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

a. `SET<>` упорядоченное множество

Добавление элементов в контейнер осуществляется с помощью операции insert:


 set < int > s;
 s.insert(20);

Операция insert возвращает pair, первым элементом которой является итератор на только что добавленный элемент, либо на элемент с таким же значением (если он уже был добавлен в set). Вторым элементом этой пары является параметр bool, который имеет значение true в случае, если новый элемент был добавлен, и false — если элемент с таким значением уже существовал.
Внутри set организован как сбалансированное дерево (АВЛ-дерево или красно-черное дерево). Соответственно операции insert (вставка) и find (поиск) выполняются за O(logn).
Операцию find можно использовать для проверки наличия элемента в контейнере следующим образом:


if (s.find(10) == s.end()) {...} //т.е. в случае, если элемент не найден find возвращает итератор на конец контейнера

Итератор set-а не позволяет изменять значение, на которое он указывает. Чтобы поменять какой-то элемент, необходимо сперва удалить его с помощью erase, а потом добавить нужный элемент с помощью insert.
В качестве параметра в set может быть использован только тип, для которого определена операция "<":


 set < int > s; //Для int определен оператор "<"

Определить оператор "<" можно самостоятельно, но это позволит упорядочивать только одним способом. Как обойти это ограничение см. ниже.

b. `multiset<>` мультимножество

Предназначено для хранения объектов,которые могут повторяться.
Multiset очень похоже на set, за исключением операции find: она возвращает итератор на первый (их может быть несколько) найденный объект, если соответствующий элемент найден, и multiset::end — если элемента нет в контейнере.
В связи с тем, что в multiset несколько элементов могут совпадать, для этого контейнера определены несколько дополнительных функций:
• lower_bound возвращает итератор на первый найденный элемент
• upper_bound возвращает итератор на следующий за последним
• equal_range возвращает пару итераторов, задающую промежуток между первым и последним найденным элементами
Чтобы посчитать количество элементов с определенным ключом можно воспользоваться функцией count. Если бы такой функции не было, то достаточно в цикле пробежать от lower_bound до upper_bound и посчитать количество итераций.
Если ни одного элемента не найдено, то lower_bound == upper_bound.
Также можно воспользоваться операцией std::distance, о которой рассказано ниже.
Пример использования:


  multiset < int > myMultiset;
  multiset < int >::iterator it, itLow, itUp;

  for (int i = 1; i < 8; i++) {
	mymultiset.insert(i * 10); // 10 20 30 40 50 60 70
  }
  itLow = myMultiset.lower_bound (30);  
  itUp= myMultiset.upper_bound (40);            

  mymultiset.erase(itLow,itUp);   // стираем все в промежутке от 30 до 40

c. `map< , >`

Организовано как дерево, которое хранит пары ключ-значений.
Добавление осуществляется следующим образом:


std::map < std::string, size_t > m;
m.insert(std::pair<std::string, int>("Vasia", 100)); // добавление значения 100
с ключом "Vasia"

или


m.insert(std::make_pair("Vasia", 100)); // make_pair сам выводит типы по введенным данным

Изменение элемента осуществляется за O(logn):


m["Vasia"] = 1000;

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


it = m.find("Vasia");
it -> first; // первое значение элемента, "Vasia"
it -> second;  //второе значение, 1000

В map значение ключа изменить нельзя, так как по первому элементу строится дерево, и поменять ее можно, только удалив элемент и добавив нужный (с помощью erase-insert). Вторую же часть можно менять, т.к. она не влияет на упорядочение в дереве.

d. `multimap< , >`

Multimap аналогичен multiset, но хранит пары ключ-значения. Отличием от map является то, что он позволяет хранить несколько значений с один ключом.

3.Предикаты и функторы

Пусть у нас есть структура:


struct Person {
   std::string Name;
   std::string University;
   int Age;
}

Допустим, мы хотим уметь сортировать объекты типа Person не только по имени (Name), но и по возрасту (Age).
Как уже было сказано раньше, для этого нам нужно переопределить оператор "<". Если мы поступим таким образом, то это позволит нам сортировать объекты Person только одним способом.


bool operator < (Person const& a, Person const& b) {
  ... //наш вариант сортировки
  return a.name < b.name; // например
}

Так как мы хотим сортировать несколькими способами, то мы воспользуемся другой техникой — предикатами.
Предикат — это структура, с переопределенным operator (), который возращает bool.
Создадим такую структуру:


struct by_name {
  bool operator ()(const Person& p1, const Person& p2) {
    return p1.name < p2.name;
  }
}

Этот предикат задаёт упорядочение объектов типа Person по имени.
В общем случае (когда operator () возвращает не bool) такая структура называется функтором.
Теперь в set в качестве шаблонного параметра мы можем передать структуру by_name, с помощью которой будет сортироваться Person:


set < Person, by_name > s;

Аналогично можно определить структуру by_age, которая будет сортировать объекты типа Person по возрасту, и структуру by_university, которая, соответственно, будет сортировать объекты по университету.
NB! Оператор "<", заданные предикатом, должен быть строгим, т.е. одновременно не должно выполняться следующее: a < b и b < a, если a != b.

4. Итераторы

Итераторы в стандартной библиотеке делятся на несколько категорий:

1. Random-access iterator
Имеют ту же функциональность, что и обычные указатели. Это наиболее полные в плане функциональности итераторы. Есть арифметика итераторов.

2. Bidirectional iterator
Специально разработанные итераторы, предназначенные для последовательного доступа в обоих направлениях: вперед и назад. Только операторы ++ и --.

3. Forward iterator
Предназначены для последовательного доступа от начала к концу. Только оператор ++.

4.1 Output iterator
Предназначены для последовательных операций вывода. К значению, на которое указывает итератор, можно обращаться только на запись.

4.2 Input iterator
Предназначены для последовательных операций ввода. К значению, на которое указывает итератор, можно обращаться только на чтение.

Что еще полезно знать об итераторах:

• iter_swap()
По двум итераторам меняет местами значения, на которые они указывают. Аналогична функции std::swap() для двух значений, но принимает итераторы на эти значения. Функция находится в <algorithm>
• std::distance(p, q)
Вычисляет расстояние между двумя итераторами.
Для итераторов типа Random-access используется арифметика итераторов. Для остальных категорий итераторов используются operator++ и operator==
• iterator_traits
Это template class позволяющий получить информацию об итераторе: категорию, тип итерируемых значений и т.д. iterator_traits имеет следующие поля:
::value_type — тип элемента, на который может указывать итератор данного типа,
::pointer, reference — тип указателя/ссылки,
::category — собственно категория итератора.

Конспект выполнен Ухорской Натальей. 7 апреля 2010г.