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

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;
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?

• I was thrown off by your comment blocks for a second, thought there was an indenting issue. Then I noticed the Z patterns. Nice! – Cris Luengo Jan 11 '18 at 21:08
• @Cris Luengo I should have removed them altogether. – coderodde Jan 11 '18 at 21:15
• A small notice about consistency. You define first "using index_type" and then "using IndexType" is there a reason for that? Sorry if I'm missing something – Blasco Jan 12 '18 at 16:14

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.

## 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;


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.

• A question: is there is any chance that in C++17 people can write (obj1, obj2).methodFoo(...);, where obj1 and obj2 are of the same type supporting method methodFoo? – coderodde Jan 17 '18 at 19:13
• @coderodde, what behavior should it have? Return a tuple? I'm not sure I understand the question. I guess you want to call a function of N objects which share the same interface? From the look of it I'd say no, but something similar is easy to write. – Incomputable Jan 17 '18 at 19:16
• Yes, basically, call obj1.methodFoo(...) and then obj2.methodFoo(...);, both with same arguments. – coderodde Jan 17 '18 at 19:19
• @coderodde, if you'll need input arguments too, then it will be a little tricky. The only possible syntax I can think of is call(member_f, pack(objects...), arguments...);, Also calling pack outside will probably cause undefined behavior, as it must support temporaries too. More concrete example would be better. There is a C++ questions and answers chat room on SO, there we could have more interactive conversation and not flood the comments. – Incomputable Jan 17 '18 at 19:21

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";

• Instead of generate, you can use iota – Incomputable Jan 12 '18 at 4:44
• @Incomputable Yes, better stil – papagaga Jan 12 '18 at 5:39
• Can you use if (msg)`? That should work no? – Aluan Haddad Jan 12 '18 at 10:51
• @Haddad Just a personal preference, I like to see at first glance it isn't a pointer. – papagaga Jan 12 '18 at 11:20
• Damn, nice code! so much cool stuff – Blasco Jan 12 '18 at 16:00