Mediumитераторы
Что такое итераторы и какие бывают категории?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Итератор — обобщение указателя для обхода контейнеров и последовательностей. Категории определяют доступные операции; алгоритмы STL требуют определённую категорию.
std::vector<int> v;
auto it = v.begin();
++it; it += 3; int x = it[0]; // random access — vector
std::list<int> l;
auto lit = l.begin();
++lit; --lit; // bidirectional (нет +=, нет [])
// std::sort(l.begin(), l.end()); — ОШИБКА, нужен random access- Input/Output — однопроходное чтение/запись (
istream_iterator); - Forward — многопроходное вперёд (
forward_list); - Bidirectional — Forward +
--(list, map); - Random Access — + арифметика
it+n,it[n],it1 < it2(vector, deque, array); - Contiguous (C++20) — Random + память непрерывна (vector, array).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.