Какие категории итераторов в STL ты знаешь?

В C++ STL итераторы классифицируются по возможностям доступа. От самой ограниченной категории к самой мощной:

1. InputIterator — позволяет только читать элементы в одном направлении (forward). Пример: std::istream_iterator. Его можно инкрементировать и разыменовать для чтения.
2. OutputIterator — позволяет только записывать элементы в одном направлении. Пример: std::ostream_iterator или std::inserter.
3. ForwardIterator — объединяет возможности Input и Output итераторов, поддерживает многопроходные алгоритмы. Пример: итератор std::forward_list.
4. BidirectionalIterator — расширяет ForwardIterator, добавляя возможность двигаться назад (operator--). Пример: итераторы std::list, std::set, std::map.
5. RandomAccessIterator — наиболее мощный. Поддерживает арифметику указателей: прыжок на N элементов (it + n), вычисление расстояния, сравнение (<, >). Пример: итераторы std::vector, std::deque, std::array.

Почему это важно: Алгоритмы STL предъявляют требования к итераторам. Например, std::sort требует RandomAccessIterator, поэтому std::list нельзя отсортировать с помощью std::sort, для него есть метод list::sort().

Пример разницы:

std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> lst = {1, 2, 3, 4, 5};

// Random Access - работает
auto vec_it = vec.begin() + 2;

// Bidirectional - так нельзя, нужно использовать std::advance
// auto lst_it = lst.begin() + 2; // Ошибка компиляции
auto lst_it = lst.begin();
std::advance(lst_it, 2); // OK, но за O(N) времени