Могу ли я преобразовать обратный итератор в прямой итератор?

Question

У меня есть класс с именем Action, который по сути является оберткой вокруг объекта Move объектов.

Поскольку мне нужно пройти через очередь Moves как вперед, так и назад, у меня есть прямой итератор и reverse_iterator в качестве переменных-членов класса. Причина этого в том, что мне нужно знать, когда я прошел один конец «конца» deque, когда я иду вперед или назад.

Класс выглядит так:

class Action
{
public:
    SetMoves(std::deque<Move> & dmoves) { _moves = dmoves; }
    void Advance();
    bool Finished() 
    {
        if( bForward )
            return (currentfwd==_moves.end());
        else
            return (currentbck==_moves.rend());
    }
private:
    std::deque<Move> _moves;
    std::deque<Move>::const_iterator currentfwd;
    std::deque<Move>::const_reverse_iterator currentbck;
    bool bForward;
};

Функция Advance выглядит следующим образом:

void Action::Advance
{
    if( bForward)
        currentfwd++;
    else
        currentbck++;
}

Моя проблема в том, что я хочу иметь возможность извлекать итератор для текущего объекта Move без необходимости запрашивать, иду ли я вперед или назад. Это означает, что одна функция возвращает один тип итератора, но у меня есть два типа.

Должен ли я забыть вернуть итератор и вместо этого вернуть константную ссылку на объект Move?

С наилучшими пожеланиями,

BeeBand

Answer 1

Обратные итераторы имеют член base(), который возвращает соответствующий прямой итератор.Помните, что этот не итератор, который ссылается на тот же объект - он фактически ссылается на следующий объект в последовательности.Это так, что rbegin() соответствует end() и rend() соответствует begin().

Так что если вы хотите вернуть итератор, вы должны сделать что-то вроде

std::deque<Move>::const_iterator Current() const
{
    if (forward)
        return currentfwd;
    else
        return (currentbck+1).base();
}

Я бы предпочел вернуть ссылку и инкапсулировать все детали итерации внутри класса.

Answer 2

Это точно проблема, которая побудила начать разработку STL. Существуют реальные причины:

1. Не хранить итераторы вместе с контейнерами
2. Использование алгоритмов, принимающих произвольные итераторы
3. Наличие алгоритмов для оценки всего диапазона вместо одного элемента за раз

Я подозреваю, что то, что вы видите сейчас, является более или менее вершиной айсберга реальных проблем. Мой совет - сделать шаг назад, и вместо того, чтобы спрашивать о том, как работать с деталями дизайна в его нынешнем виде, задайте несколько более общий вопрос о том, чего вы пытаетесь достичь, и как лучше всего это сделать. конечный результат.

Для тех, кому важен вопрос в названии, ответ - «да». В частности, reverse_iterator имеет элемент base() для этого. Хотя квалификации несколько проблематичны.

Чтобы продемонстрировать проблему, рассмотрите код следующим образом:

#include <iostream>
#include <vector>
#include <iterator>

int main() { 
    int i[] = { 1, 2, 3, 4};
    std::vector<int> numbers(i, i+4);

    std::cout << *numbers.rbegin() << "\n";
    std::cout << *numbers.rbegin().base() << "\n";
    std::cout << *(numbers.rbegin()+1).base() << "\n";

    std::cout << *numbers.rend() << "\n";
    std::cout << *numbers.rend().base() << "\n";
    std::cout << *(numbers.rend()+1).base() << "\n";
}

Выполнение этого в данный конкретный момент на моей конкретной машине дает следующий вывод:

4
0
4
-1879048016
1
-1879048016

Резюме: с rbegin() мы должны добавить один перед преобразованием в прямой итератор, чтобы получить действительный итератор - но с rend() мы должны не добавить один до преобразование для получения действительного итератора.

Пока вы используете X.rbegin() и X.rend() в качестве параметров универсального алгоритма, это нормально, но опыт показывает, что преобразование в прямые итераторы часто приводит к проблемам.

В конце, однако, для основной части вопроса (в отличие от заголовка) ответ в значительной степени такой же, как приведенный выше: проблема заключается в попытке создать объект, который объединяет коллекцию с парой итераторов в эту коллекцию. Исправьте эту проблему, и весь бизнес с прямыми и обратными итераторами станет спорным.

Answer 3

Поскольку <a href="http://www.sgi.com/tech/stl/Deque.html" rel="noreferrer">std::deque</a> является контейнером произвольного доступа (аналогично std::vector), вам гораздо лучше использовать один целочисленный индекс в деке для обоих обходов.

Answer 4

Мне кажется, что на самом деле у вас два разных поведения в одном классе.

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

Лично я за выставление обоих итераторов (т. Е. Форвард begin, end, rbegin and rend).

Вы также можете вернуть простой объект Iterator:

template <class T>
class Iterator
{
public:
  typedef typename T::reference_type reference_type;

  Iterator(T it, T end) : m_it(it), m_end(end) {}

  operator bool() const { return m_it != m_end; }

  reference_type operator*() const { return *m_it; }

  Iterator& operator++() { ++m_it; return *this; }

private:
  T m_it;
  T m_end;
};

template <class T>
Iterator<T> make_iterator(T it, T end) { return Iterator<T>(it,end); }

Затем вы можете просто вернуть этот простой объект:

class Action
{
public:
  Action(std::deque<Move> const& d): m_deque(d) {} // const& please

  typedef Iterator< std::deque<Move>::iterator > forward_iterator_type;
  typedef Iterator< std::deque<Move>::reverse_iterator > backward_iterator_type;

  forward_iterator_type forward_iterator()
  {
    return make_iterator(m_deque.begin(), m_deque.end());
  }

  backward_iterator_type backward_iterator()
  {
    return make_iterator(m_deque.rbegin(), m_deque.rend());
  }


private:
  std::deque<Move> m_deque;
};

Или, если вы хотите динамически выбирать между прямым и обратным обходом, вы можете сделать Iterator чистым виртуальным интерфейсом, имеющим как прямой, так и обратный обход.

Но на самом деле, я не вижу смысла хранить ОБА вперед и назад, если окажется, что вы будете использовать только один: /

Answer 5

Может быть, вам следует пересмотреть свой выбор контейнера.

Обычно вам не нужно использовать обратные итераторы, чтобы вернуться назад,

currentfwd--

будет идти в обратном направлении, хотя все может не работать (что, я полагаю, вы пытались) с dequeue.

Что вы действительно должны сделать, это смоделировать свой класс здесь как декоратор dequeue и реализовать свои собственные итераторы Action. Это было бы то, что я бы сделал в любом случае.