Как реализовать итератор для двусвязного списка?

Question

У меня есть собственный класс списков с двойными связями, и я хочу реализовать для него итератор, чтобы я мог использовать такие функции, как std :: sort и те, которые представлены ниже. Что с этим можно сделать?

Например, теперь у меня есть реализация, но это плохо. Следующая строка

std::cout << list.end() - list.begin() << std::endl;

выводит

-179191768

, где list - это мой список списков с 10 элементами в нем.

Функция, которую я хочу работать:

template <typename I, typename C>
void quickSort(I begin, I end, C cmp) {
    if (begin >= end) throw new exception_incorrectSelection;
    I i = begin, j = end;
    T pivot = *(i + (j - i) / 2);
    while (i <= j) {
        while (cmp(*i, pivot)) ++i;
        while (cmp(pivot, *j)) --j;
        if (i <= j) {
            std::iter_swap(i, j);
            ++i;
            --j;
        }
    }
    if (j > begin) quickSort(begin, j, cmp);
    if (i < end) quickSort(i, end, cmp);
}

При проверке исключений происходит сбой по причине, изложенной ранее.

Answer 1

Итераторы бывают разных категорий. Для двусвязного списка вы обычно применяете двунаправленный итератор. Двунаправленный итератор не будет поддерживать std::sort, но будет поддерживать многие (большинство?) Других алгоритмов, таких как find, find_if, accumulate и т. Д.

Вы может написать итератор для двусвязного списка, который поддерживает концепцию RandomAccessIterator (например, поддерживает iterator + int и iterator - int), но остается открытым вопрос, действительно ли вы этого хотите - обычно вы ожидаете произвольного доступаитератор, обеспечивающий сложение и вычитание с постоянным временем, но со связанным списком они будут иметь линейное время. Таким образом, даже если вы поддерживаете концепцию с точки зрения операций, которые она должна поддерживать, вы нарушаете требования к сложности:

Концепция RandomAccessIterator добавляет поддержку постоянное время повышение с + =, +, - = и -, а также вычисление расстояния в постоянное время с -. Итераторы произвольного доступа также поддерживают нотацию массива посредством подписки.

[выделение добавлено]

Так что, хотя вы можете заставить его работать с std::sort, если хотите, это, вероятно, не очень хорошая идея сделать это.

Это оставляет два варианта: идти вперед и в любом случае создавать один и тот же интерфейс и жить с фактом, что операции произвольного доступа будут иметь линейную сложность, или переписать вашалгоритм работы с тем, что могут обеспечить двунаправленные итераторы. Это будет выглядеть примерно так:

template <typename I, typename C>
void quickSort(I begin, I end, C cmp) {
    if (begin >= end) throw new exception_incorrectSelection;
    I i = begin, j = end;
    T pivot = *(i + std::distance(i, j) / 2); // <--
    while (i <= j) {
        while (cmp(*i, pivot)) ++i;
        while (cmp(pivot, *j)) --j;
        if (i <= j) {
            std::iter_swap(i, j);
            ++i;
            --j;
        }
    }
    if (j > begin) quickSort(begin, j, cmp);
    if (i < end) quickSort(i, end, cmp);
}

По крайней мере, как обычно реализовано, std::distance будет делать что-то вроде этого:

template <class Iter>
size_t distance(Iter a, Iter b) { 
    size_t ret = 0;

    while (a != b) {
       ++a;
       ++ret;
    }
    return ret;
}

... так, пока ваш итератор поддерживает++ и !=, обычно этого будет достаточно для работы с std::distance.