A C++ template function for doing multi-indexing a sequence

Question

The idea behind the below code is that I can index a sequence with a sequence of indices and get a std::vector of the indexed elements:

multi_index.hpp

#ifndef NET_CODERODDE_UTIL_MULTI_INDEX_HPP
#define NET_CODERODDE_UTIL_MULTI_INDEX_HPP

#include <algorithm>
#include <exception>
#include <iostream>
#include <iterator>
#include <sstream>

namespace net::coderodde::util {

    template<typename IteratorIndex>
    using index_type =
    typename std::iterator_traits<IteratorIndex>::value_type;

    template<typename IteratorElem>
    using element_count_type =
    typename std::iterator_traits<IteratorElem>::difference_type;

    template<typename IteratorElem>
    using element_type =
    typename std::iterator_traits<IteratorElem>::value_type;

    ////  ///////////////////////////////////////////////
     // Throws an exception if the index is negative. //
    ///////////////////////////////////////////////  ////
    template<typename index_type>
    static void throw_index_negative(index_type index)
    {
        std::stringstream ss;
        ss << "index(" << index << ") < 0";
        throw std::runtime_error{ss.str()};
    }

    ////  ////////////////////////////////////////////////
     // Throws an exception if the index is too large. //
    ////////////////////////////////////////////////  ////
    template<typename index_type,
             typename element_count_type>
    static void throw_index_too_large(index_type index,
                                      element_count_type size)
    {
        std::stringstream ss;
        ss << "index(" << index << ") >= elem_count(" << size << ")";
        throw std::runtime_error{ss.str()};
    }

    template<typename IteratorElem,
             typename IteratorIndex>
    static void check_indices(IteratorElem elem_begin,
                              IteratorElem elem_end,
                              IteratorIndex index_begin,
                              IteratorIndex index_end)
    {
        // Find the length of the element sequence:
        typename std::iterator_traits<IteratorElem>
                    ::difference_type elem_count = std::distance(elem_begin,
                                                                 elem_end);

        using IndexType =
        typename std::iterator_traits<IteratorIndex>::value_type;

        // Check that each index does not refer outside the element sequence:
        std::for_each(index_begin, index_end, [elem_count](IndexType index) {
            if (index < 0) { throw_index_negative(index); }
            if (index >= elem_count) { throw_index_too_large(index,
                                                             elem_count);}
        });
    }

    template<typename IteratorElem,
             typename IteratorIndex>
    std::vector<typename std::iterator_traits<IteratorElem>::value_type>
    multi_index(IteratorElem elem_begin,
                IteratorElem elem_end,
                IteratorIndex index_begin,
                IteratorIndex index_end)
    {
        check_indices(elem_begin,
                      elem_end,
                      index_begin,
                      index_end);

        using ElementType =
        typename std::iterator_traits<IteratorElem>::value_type;

        using IndexType =
        typename std::iterator_traits<IteratorIndex>::value_type;

        std::vector<ElementType> result;

        std::for_each(index_begin,
                      index_end,
                      [elem_begin, &result](IndexType index) {
            auto it = elem_begin;
            std::advance(it, index);
            result.push_back(*it);
        });

        return result;
    }
}

#endif // NET_CODERODDE_UTIL_MULTI_INDEX_HPP

main.cpp

#include "multi_index.hpp"
#include <exception>
#include <iostream>
#include <list>
#include <vector>

using net::coderodde::util::multi_index;

static std::vector<char> get_alphabet() {
    std::vector<char> alphabet;

    for (char ch = 'a'; ch <= 'z'; ch++)
    {
        alphabet.push_back(ch);
    }

    for (char ch = 'A'; ch <= 'Z'; ch++)
    {
        alphabet.push_back(ch);
    }

    alphabet.push_back(',');
    alphabet.push_back(' ');
    alphabet.push_back('!');
    alphabet.push_back('\n');

    return alphabet;
}

int main(int argc, const char * argv[]) {
    std::vector<char> alphabet = get_alphabet();
    std::list<int> char_indices =
        { 33, 4, 11, 11, 14, 52, 53, 48, 14, 17, 11, 3, 54, 55 };
    std::vector<char> result = multi_index(alphabet.cbegin(),
                                           alphabet.cend(),
                                           char_indices.cbegin(),
                                           char_indices.cend());

    std::ostream_iterator<char> out_iterator(std::cout);
    std::copy(result.cbegin(), result.cend(), out_iterator);

    try {
        char_indices = { 0, 1, 2, -1, 3 };
        multi_index(alphabet.cbegin(),
                    alphabet.cend(),
                    char_indices.cbegin(),
                    char_indices.cend());
    } catch (std::runtime_error& err) {
        std::cout << err.what() << "\n";
    }

    try {
        char_indices = { 0, 1, 2, 56, 3 };
        multi_index(alphabet.cbegin(),
                    alphabet.cend(),
                    char_indices.cbegin(),
                    char_indices.cend());
    } catch (std::runtime_error& err) {
        std::cout << err.what() << "\n";
    }

    return 0;
}

Outputs:

Hello, World!
index(-1) < 0
index(56) >= elem_count(56)

Critique request

Please tell me anything that comes to mind. Also, I would like to hear about using move semantics: is there anything I could move instead of copying?

Answer 1

Overall good, covers most of the usual usage cases.

Ideology

Although the code certainly values some principles of standard library, I believe it is much easier used with libraries like POCO (which quite a lot of people believe is better), which have their own view of C++. There is a great idea struggling to come out, or at least illusion of it's existence. It is really hard to tell which one it is, though.

---

Code

Naming

What the code essentially performs is selective copying, so I would use selective_copy or indexwise_copy. Some people might get confused, but hopefully IDE popup with argument types will resolve it.

More fluent interface

std::list<int> char_indices =
    { 33, 4, 11, 11, 14, 52, 53, 48, 14, 17, 11, 3, 54, 55 };
std::vector<char> result = multi_index(alphabet.cbegin(),
                                       alphabet.cend(),
                                       char_indices.cbegin(),
                                       char_indices.cend());

The example usage clearly shows that function needs std::initializer_list<std::size_t> overload.

auto

I believe the function declaration could use auto:

template<typename IteratorElem,
         typename IteratorIndex>
auto multi_index(IteratorElem elem_begin,
                 IteratorElem elem_end,
                 IteratorIndex index_begin,
                 IteratorIndex index_end)

Most C++ programmers will by default assume std::vector. Pedantic people will just go through the code to discover correctness of their assumptions. No surprises.

And in elem_count:

auto elem_count = std::distance(elem_begin, elem_end);

Hide helpers

I would hide the throw_xxx functions into namespace detail or similar.

Minor things

        auto it = elem_begin;
        std::advance(it, index);

Can be written as std::next(it, index);.

I believe std::transform would be a better fit for the copying loop, but this is very subjective.

Alternative approach

Another point of view, the one that emphasizes objects more than actions, would reveal different solution: indirection_iterator.

template <typename ForwardIterator>
class indirection_iterator
{
    std::vector<ForwardIterator> iterators;
public:
    //stuff to conform RandomAccessIterator
    //propagate dereference into underlying iterators
    // use decltype(auto) to propagate proxies, like from vector<bool>

private:
    //constructors
};

template <typename ForwardIterator>
std::pair<indirection_iterator<ForwardIterator>,
          indirection_iterator<ForwardIterator>>
create_indirection_range(/*...*/) //takes the same things as `selective_copy`

Design decisions:

• Private constructors

  There is no valid iterator which will be usable by creating only one iterator. The only cases are usages like doxxx_n algorithms. Having the second one is free anyway, and in C++17 people can just:

  auto [first, last] = create_indirection_range(...);
  

• Random access iterator

  It doesn't seem like there is a reason to impose different behavior. Don't use ContiguousIterator though, as the iterator is not aware of layout of objects in memory.

Overview of alternative solution

It looks like it solves many problems. One can now sort lists, forward lists, and whatnot. One can even write functions like this:

using indirection_range = ...; //the pair above

indirection_range all_except(Range range, Iterator to_leave_out);

Now one can leave out an element or many of them, and then sort the rest as if the range was contiguous.

But it is not a panacea. It looks like an iterator, it even compiles, and this is one of the fundamental problems: it pretends to be an iterator. Actual iterators are cheap to copy. In fact, most of the time it is a pointer. indirection_iterator violates this assumption. Any divide and conquer algorithms will pass iterators down the recursion chain, as a result somewhat degrading the efficiency of algorithms.

Throwing away other minor problems, `indirection_iterator might have its niche usages, but I don't think it is the-day-to-day iterator to use.

To date, I believed that there is C++ way of doing things. But now I just think that it is yet another point of view, and not something absolute, like a fact. Unfortunately, IMO, people are very bad at communicating and learning facts, as human language and any medium through which it is delivered usually causes some bias in human's perception.

Answer 2

I think you can simplify your code a bit, which is always a good thing.

You can generate the alphabet in a cleaner way by using the appropriate standard algorithm:

#include <vector>
#include <algorithm>
int main() {
    std::vector<char> alphabet;
    auto alpha = 'a';
    std::generate_n(std::back_inserter(alphabet), 26, [&alpha]() { return alpha++; });
}

A dedicated function to apply the indices on the vector is a bit of overkill also, and the for range is cleaner than for_each when you iterate over the whole sequence:

for (auto idx : indices) result.push_back(alphabet[idx]);

You can't really use the generic approach because your algorithm would be extremely inefficient with anything else than a random access iterator -so it's better to simply use the subscript operator.

As to check_indices I think you can leverage the any_of algorithm:

auto out_of_bound = std::any_of(std::begin(char_indices), std::end(char_indices),
                               [&alphabet](auto&& idx) {
                                     return idx < 0 || idx >= alphabet.size();
                                                       });

It's also good to know that you can get away without throwing exceptions. There's this new std::optional now to take into account the impossiblity of returning any sensible value. The caller can then decide how to act upon the failure. So for example:

std::optional<std::vector<char>> multi_index(/* insert args here*/);

and then

auto msg = multi_index(f1, l1, f2, l2);
if (msg.has_value()) display(*msg);
else std::cout << "please provide correct indices";