Парная итерация по вектору

Question

Сводка вопроса

Учитывая std::vector<T>, как я могу создать представление , которое предоставляет интерфейс std::vector<std::pair<T, T>>, где каждая пара состоит из двух последовательных элементов в базовомвектор?

Подробности

Цель состоит в том, чтобы создать несколько абстракций контейнера в одном хранилище, которое является std::vector<T>.Тип T является своего рода различимым объединением, как Boost Variant .Требование к памяти дано, в противном случае я бы просто использовал std::vector<std::pair<T, T>>.Виды хранилища, которые я хотел бы поддержать, - это наборы (уникальные элементы) и таблицы (ассоциативный массив, уникальные ключи).В то время как первое является простым, обеспечивая заданное свойство уникальности, второму требуется обработка ключей и значений.

Для поддержки семантики ассоциативных массивов над std::vector<T>, в настоящее время я думаю, что лучшим способом было бысоздайте представление вида std::vector<std::pair<T, T>>, и это представление позволит мне использовать алгоритмы STL для поддержания требуемых свойств.Это звучит как хорошая стратегия?Есть ли другие идеи?

Связанные

Если бы у меня был итератор i , который проходит через каждый четный элемент, и итератор j , который проходит через каждыйВспоминается нечетный элемент, * Boost zip iterator , который позволяет выполнять итерацию в парах (i, j) .Но мой вариант использования немного отличается тем, что у меня нет двух отдельных контейнеров.

Answer 1

Кажется, что Boost's iterator_facade действительно то, что я хочу.Вот игрушечный пример (с неровными краями):

#include <algorithm>
#include <iostream>
#include <vector>
#include <boost/iterator/iterator_facade.hpp>

template <typename Value>
class pair_iterator
  : public boost::iterator_facade<
        pair_iterator<Value>
      , Value
      , boost::random_access_traversal_tag
      , std::pair<Value&, Value&>
      , typename std::vector<Value>::difference_type
    >
{
public:
    typedef std::vector<Value> vector_type;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::iterator iterator;

    pair_iterator()
        : i_(0)
    {
    }

    explicit pair_iterator(iterator i)
      : i_(i)
    {
    }

private:
    friend class boost::iterator_core_access;

    bool equal(pair_iterator<Value> const& other) const
    {
        return i_ == other.i_;
    }

    void increment()
    {
        ++i_;
        ++i_;
    }

    std::pair<Value&, Value&> dereference() const
    {
        return { std::ref(*i_), std::ref(*(i_ + 1)) };
    }

    void advance(difference_type n)
    {
        i_ += n << 1;
    }

    difference_type distance_to(pair_iterator<Value> const& other) const
    {
        return other.i_ - i_;
    }

    iterator i_;
};

int main()
{
    typedef pair_iterator<int> int_map_iterator;
    std::vector<int> v{2, 20, 3, 30, 5, 50, 7, 70};
    int_map_iterator first(v.begin());
    int_map_iterator last(v.end());

    std::for_each(first + 1, last,
                  [](std::pair<int&, int&> p)
                  {
                      std::cout
                          << p.first << " -> "
                          << p.second << std::endl;
                  });

    return 0;
}

Вывод:

3 -> 30
5 -> 50
7 -> 70

Проблемы

• Преобразование из iterator в const_iterator еще не рассматривался в этом примере.
• Итератор работает только тогда, когда нижележащий вектор имеет четный размер и нуждается в более консервативной реализации dereference().

Answer 2

Первое, что нужно отметить, это то, что вы не сможете выставить std::pair<T const, T>& в качестве средства для изменения объектов.Что может быть достаточно близко, тем не менее, это std::pair<T const, T&>, так как вы сможете изменить только вторую часть.

С этим путем, кажется, вам нужно

1. Тип итератора, который пропускает все остальные значения и используется для перебора ключей (элементов с четными индексами) и значений (элементов с нечетными индексами).
2. Что-то вроде «итератора zip», который принимает два итератораи выставляет std::pair<T const, T&> полученный от них.