Fancy indexing in C++ using boost::range

Question

I'd like to use boost::range to pull off something similar to the "fancy indexing" available in NumPy and Matlab. Specifically, I would like to select certain elements of one indexable container using elements of another container as the indices. For example, one can do the following in Python:

>>> squares = numpy.arange(10)**2  # Step 1 - setup squares
>>> indices = numpy.array([1,3,4]) # Step 2 - setup indices
>>> squares[indices]               # Step 3 - fancy indexing
array([ 1, 9, 16])

In C++, using boost::range, I think the above code would look something like this:

#include "sampled.hpp"
#include <boost/assign/std/vector.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/counting_range.hpp>
#include <iostream>
#include <vector>

using namespace boost;
using namespace boost::adaptors;
using namespace boost::assign;
using namespace boost::lambda;
using namespace std;

int main(int argc, char** argv)
{
    // Step 1 - setup squares
    vector<int> squares;
    push_back(
        squares,
        counting_range(1,11) | transformed(ret<int>(_1 * _1))
    );

    // Step 2 - setup indices
    vector<size_t> indices;
    indices += 1,3,4;

    // Step 3 - fancy indexing
    for_each(
        squares | sampled(indices),
        cout << _1 << constant(" ")
    );

    return 0;
}

Since the name "indexed" is already used by an existing range adaptor (boost::adaptor::indexed), I called the yet-unimplemented indexing adaptor "sampled" in the above code.

Does anyone know if such an adaptor already exists in boost somewhere, or have an implementation they'd be willing to share? I've started trying to implement it myself by first writing a "sampled_iterator" (using iterator_adaptor) and then a "sampled_range" (using iterator_range) but I'm finding it quite tricky.

Arbe

+1, interesting question and problem statement. I’ve never yet worked with this part of Boost but this will likely change in the future. A reasonably efficient implementation of this feature is certainly interesting to a wider range of people, so if you get it working, be sure to publish it. ;-) – Zalea

Answer 1

OK, so I managed to get something working using boost::permutation_iterator as the basis for the range adaptor. Since permutation_iterator is used, I called the range adaptor "permuted" rather than "sampled" as it is referred to in question's code excerpt. So the C++ version of the numpy code looks like this:

// Step 3
for_each(
    squares | permuted(indices),
    cout << _1 << constant(" ")
);

Here's the code for "permuted":

#pragma once

#include <boost/range/adaptor/argument_fwd.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/iterator/permutation_iterator.hpp>

template <class IndexContainer, class ElementRange>
class permuted_range :
    public boost::iterator_range<
        boost::permutation_iterator<
            typename boost::range_iterator<ElementRange>::type,
            typename IndexContainer::iterator> >
{
private:
    typedef boost::iterator_range<
        boost::permutation_iterator<
        typename boost::range_iterator<ElementRange>::type,
        typename IndexContainer::iterator> > base;

public:
    permuted_range(IndexContainer& i, ElementRange& r) :
        base(
            boost::make_permutation_iterator(boost::begin(r), i.begin()),
            boost::make_permutation_iterator(boost::begin(r), i.end()))
    { }
};

template <class IndexContainer>
struct permuted_holder : boost::range_detail::holder<IndexContainer>
{
    permuted_holder(IndexContainer i) :
        boost::range_detail::holder<IndexContainer>(i)
    { }
};

template <class ElementRange, class IndexContainer>
inline permuted_range<IndexContainer, ElementRange> operator| (
    ElementRange& r,
    permuted_holder<IndexContainer> i)
{
    return permuted_range<IndexContainer, ElementRange>(i.val, r);
}

template <class ElementRange, class IndexContainer>
inline permuted_range<IndexContainer, const ElementRange> operator| (
    const ElementRange& r,
    permuted_holder<IndexContainer> i)
{
    return permuted_range<IndexContainer, const ElementRange>(i.val, r);
}

static boost::range_detail::forwarder<permuted_holder> permuted =
    boost::range_detail::forwarder<permuted_holder>();

I imagine there are some improvements that could be made. And permutation_iterator seems like a reasonably efficient basis for this, but perhaps there are better alternatives. Any thoughts?

Arbe