Что такое bidirectional_iterator?

Что такое bidirectional_iterator?

Определение

Bidirectional_iterator (двунаправленный итератор) — итератор STL, позволяющий перемещаться в обе стороны: вперёд (++) и назад (--). Это более мощный итератор, чем forward_iterator, но менее мощный, чем random_access_iterator.

Иерархия итераторов

Input Iterator
    ↓
Forward Iterator
    ↓
Bidirectional Iterator
    ↓
Random Access Iterator

Каждый уровень добавляет возможности предыдущему.

Возможности bidirectional_iterator

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> mylist = {10, 20, 30, 40, 50};
    
    auto it = mylist.begin();
    
    // Вперёд (increment)
    ++it;  // Указывает на 20
    ++it;  // Указывает на 30
    
    // Назад (decrement)
    --it;  // Указывает на 20
    --it;  // Указывает на 10
    
    cout << *it << endl;  // Выводит 10
    
    return 0;
}

Операции bidirectional_iterator

list<int>::iterator it = mylist.begin();

// ПОДДЕРЖИВАЕМЫЕ:
++it;           // Инкремент (вперёд)
it++;           // Постинкремент
--it;           // Декремент (назад)
it--;           // Постдекремент
*it;            // Разыменование
it->member;     // Доступ к члену
it1 == it2;     // Сравнение
it1 != it2;     // Неравенство

// НЕ ПОДДЕРЖИВАЕМЫЕ (только для random_access):
it + 5;         // ОШИБКА!
it[0];          // ОШИБКА!
it1 < it2;      // ОШИБКА! Только == и !=

Где используются?

Контейнеры с bidirectional_iterator:

#include <list>
#include <set>
#include <map>

// std::list
list<int> mylist = {1, 2, 3, 4, 5};
auto it = mylist.begin();  // bidirectional

// std::set
set<int> myset = {1, 2, 3, 4, 5};
auto it = myset.begin();  // bidirectional

// std::map
map<string, int> mymap = {{"a", 1}, {"b", 2}};
auto it = mymap.begin();  // bidirectional

// std::vector — random_access_iterator (сильнее!)
vector<int> myvec = {1, 2, 3};
auto it = myvec.begin();  // Поддерживает it + 5, it[0]

Пример: обход в обе стороны

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> mylist = {10, 20, 30, 40, 50};
    
    // Обход ВПЕРЁД
    cout << "Вперёд: ";
    for (auto it = mylist.begin(); it != mylist.end(); ++it) {
        cout << *it << " ";
    }
    cout << "\\n";  // 10 20 30 40 50
    
    // Обход НАЗАД
    cout << "Назад: ";
    for (auto it = mylist.rbegin(); it != mylist.rend(); ++it) {
        cout << *it << " ";
    }
    cout << "\\n";  // 50 40 30 20 10
    
    // Двусторонний поиск
    auto it = mylist.begin();
    while (it != mylist.end()) {
        if (*it == 30) {
            cout << "Нашёл 30\\n";
            --it;  // Двигаемся НАЗАД
            cout << "Предыдущий: " << *it << "\\n";  // 20
            break;
        }
        ++it;
    }
    
    return 0;
}

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

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> mylist = {10, 20, 30, 40, 50};
    
    // Удалить элемент 30
    for (auto it = mylist.begin(); it != mylist.end(); ) {
        if (*it == 30) {
            it = mylist.erase(it);  // erase возвращает следующий
        } else {
            ++it;
        }
    }
    
    // Остаток: 10 20 40 50
}

Сравнение итераторов

Почему не везде random_access_iterator?

Bidirectional нужен для:

• std::list — linked list, нет случайного доступа
• std::set — tree structure
• std::map — tree structure

Random Access для:

• std::vector — память подряд
• std::array — фиксированный размер
• std::deque — индексирование O(1)

Алгоритмы STL

#include <algorithm>

list<int> mylist = {1, 2, 3, 4, 5};

// std::reverse требует bidirectional_iterator
reverse(mylist.begin(), mylist.end());  // OK

// std::sort требует random_access_iterator
// sort(mylist.begin(), mylist.end());  // ОШИБКА на list!

vector<int> myvec = {5, 3, 1, 4, 2};
sort(myvec.begin(), myvec.end());  // OK