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

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

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

	List	Vector	Deque
Удаление	Конкретный итератор	Конкретный итератор и все после него	При удалении первого и последнего элементов — начало и конца; При удалении остальных элементов — всех итераторов
Добавление	Конкретный итератор	Все итераторы	см. удаление

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 возвращает пару итераторов, задающую промежуток между первым и последним найденным элементами
Чтобы посчитать количество элементов с определенным ключом, достаточно в цикле пробежать от lower_bound до upper_bound и посчитать количество итераций.
Если ни одного элемента не найдено — lower_bound = upper_bound
Пример использования:


  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("Vasia", 100)); // добавление пары значений

или


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

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


m["Vasia"] = 1000;

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


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

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

d. `multimap< , >`

Multimap очень похожа на multiset.

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

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


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

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


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

Но в set нужно передавать класс или структуру.
Создадим структуру:


struct by_name {
  bool operator < () {
    ...
  }
}

Такая функция внутри структуры (класса) будет называться функтором или предикатом. Предикат — это функтор, который возвращает bool.
Теперь в set мы можем передать в качестве другого параметра структуру by_name, с помощью которой будет сортироваться Person:


set < Person, by_name > s;

NB! Оператор "<" должен быть строгим.

4. Итераторы

Категории итераторов:

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

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

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

4.1 Output iterator
Предназначены для последовательных операций вывода. Значение, на которое указывает итератор, записывается, и после этого итератор увеличивается.

4.2 Input iterator
Предназначены для последовательных операций ввода. Значение, на которое указывает итератор, считывается, и после этого итератор увеличивается.

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

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