Объединить два вектора STL с чередующимся шаблоном

Question

У меня есть два вектора STL A и B, и мне нужно объединить их в третий, где элементы должны быть упорядочены таким образом, чтобы каждый n-й элемент в выходном векторе имел вектор B. Мой текущий код выглядит как-товот так:

std::vector<int> a(10, 4);
std::vector<int> b(10, 8);
std::vector<int> c;
static const std::size_t STEP(3);

std::vector<int>::const_iterator bIt = b.begin();
for(std::vector<int>::const_iterator aIt = a.begin();
    aIt != a.end(); ++aIt)
{
    c.push_back(*aIt);
    if((c.size() + 1) % STEP == 0)
    {
        c.push_back(*bIt);
        ++bIt; //assume b is large enough
    }
}

Вектор c теперь выглядит следующим образом: 4 4 8 4 4 8 ...

Это отлично работает, но мне любопытно, если нет болееэлегантное решение.Есть ли способ использовать алгоритм STL вместо моих рукописных циклов?

Answer 1

Должен признать, мне очень нравится решение Potatoswatter ... довольно.

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

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

Представление - это интерфейс адаптера для одного или нескольких контейнеров. На самом деле он ничего не содержит (это важная часть). Однако он предоставляет интерфейс, аналогичный интерфейсу контейнера, так что вы можете кодировать с обычными идиомами.

Прекрасное в представлениях - это то, что их часто можно составлять.

Например, один очень простой вид:

/// Only allow to see a range of the container:
/// std::vector<int> v(40, 3); // { 3, 3, 3, ... }
/// auto rv = make_range_view(v, 4, 5);
/// rv exposes the elements in the range [4,9)
/// in debug mode, asserts that the range is sufficiently large
template <typename Container>
class range_view
{
};

Для вашего вопроса вы бы предпочли создать interleave_view:

/// Allow to interleave elements of 2 containers each at its own pace
/// std::vector<int> v(40, 3);
/// std::set<int> s = /**/;
/// 
/// auto iv = make_interleave_view(v, 3, s, 1);
/// Takes 3 elements from v, then 1 from s, then 3 from v, etc...
template <typename C1, typename C2>
class interleave_view
{
};

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

Конечно, это может стать немного более утомительным, если контейнеры не предлагают эффективный элемент "size" (list нет, это O (n)).

Однако общий принцип заключается в том, что представление дает вам больше контроля (и позволяет больше проверок) и безопаснее в использовании, поскольку вы точно контролируете создание итераторов.

Обратите внимание, что в C ++ 0x interleave_view обычно содержит неограниченное число последовательностей.

Answer 2

Это слишком специализированный, чтобы быть покрытым <algorithm>. Чтобы избежать цикла, потребуется специальный итератор.

template< typename I1, typename I2 >
struct interleave_iterator
    : std::iterator< forward_iterator_tag, typename I1::value_type > {
    using typename I1::value_type;

    I1 i1;
    I2 i2;
    size_t cnt, stride;

    interleave_iterator( I1 in1, I2 in2, size_t in_stride=0, size_t in_off=0 )
        : i1( in1 ), i2( in2 ), cnt( in_off ), stride( in_stride ) {}

    value_type &operator*() const { return cnt? * i1 : * i2; }
    interleave_iterator &operator++() {
        if ( ++ cnt == stride ) {
            cnt = 0;
            ++ i2;
        } else ++ i1;
        return *this;
    }
    value_type *operator->() const
        { return cnt? i1.operator->() : i2.operator->(); }

    interleave_iterator &operator++(int)
        { interleave_iterator r = *this; ++ *this; return r; }

    friend bool operator==
        ( interleave_iterator const &lhs, interleave_iterator const &rhs )
        { return lhs.i1 == rhs.i1 && lhs.i2 == rhs.i2; }
    friend bool operator!=
        ( interleave_iterator const &lhs, interleave_iterator const &rhs )
        { return ! ( lhs == rhs ); }
};

Я думаю, немного излишне.