7
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ I was thrown off by your comment blocks for a second, thought there was an indenting issue. Then I noticed the Z patterns. Nice! \$\endgroup\$ – Cris Luengo Jan 11 '18 at 21:08
  • \$\begingroup\$ @Cris Luengo I should have removed them altogether. \$\endgroup\$ – coderodde Jan 11 '18 at 21:15
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – Blasco Jan 12 '18 at 16:14
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – coderodde Jan 17 '18 at 19:13
  • \$\begingroup\$ @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. \$\endgroup\$ – Incomputable Jan 17 '18 at 19:16
  • \$\begingroup\$ Yes, basically, call obj1.methodFoo(...) and then obj2.methodFoo(...);, both with same arguments. \$\endgroup\$ – coderodde Jan 17 '18 at 19:19
  • \$\begingroup\$ @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. \$\endgroup\$ – Incomputable Jan 17 '18 at 19:21
3
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.