random_iterator in C++

Question

This is a small utility that permutes a C++ standard container without modifying the container being iterated:

random_iterator.hpp

#ifndef RANDOM_ITERATOR_HPP
#define RANDOM_ITERATOR_HPP

#include <initializer_list>
#include <random>
#include <vector>

namespace net {
namespace coderodde {
namespace utilities {

template<typename T>
class random_iterator {
private:
    std::vector<T> vec;

public:

    template<typename Iterable>
    explicit random_iterator(Iterable iterable)
    {
        for (auto& x : iterable)
        {
            vec.push_back(x);
        }

        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(vec.begin(), vec.end(), g);
    }

    template<typename Iterable>
    explicit random_iterator(Iterable iterable, std::random_device& rd)
    {
        for (auto& x : iterable)
        {
            vec.push_back(x);
        }

        std::mt19937 g(rd());
        std::shuffle(vec.begin(), vec.end(), g);
    }

    explicit random_iterator(std::initializer_list<T>& lst)
    {
        for (auto& x : lst)
        {
            vec.push_back(x);
        }

        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(vec.begin(), vec.end(), g);
    }

    explicit random_iterator(std::initializer_list<T>& lst,
                             std::random_device& rd)
    {
        for (auto& x : lst)
        {
            vec.push_back(x);
        }

        std::mt19937 g(rd());
        std::shuffle(vec.begin(), vec.end(), g);
    }

    typename std::vector<T>::iterator begin()
    {
        return vec.begin();
    }

    typename std::vector<T>::iterator end()
    {
        return vec.end();
    }

    typename std::vector<T>::const_iterator begin() const
    {
        return vec.cbegin();
    }

    typename std::vector<T>::const_iterator end() const
    {
        return vec.cend();
    }
};

} // End of net::coderodde::utilities
} // End of net::coderodde
} // End of net
#endif // RANDOM_ITERATOR_HPP

main.cpp

#include "random_iterator.hpp"
#include <iostream>
#include <set>
#include <vector>

using namespace std;
using net::coderodde::utilities::random_iterator;

int main(int argc, const char * argv[]) {
    vector<int> v1 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    for (auto& x : random_iterator<int>(v1))
        cout << x << " ";

    cout << "\n";

    set<int> s1 {1, 2, 3, 4, 5};

    for (auto& x : random_iterator<int>(s1))
        cout << x << " ";

    cout << "\n";
}

Critique request

I would like to know, how a professional C++ programmer would implement this.

Answer 1

Naming

First of, what you have created is not an iterator so naming it as such is misleading. I would recommend a name but I actually think that you should redesign your class and the name I would recommend wouldn't be fit for the redesigned class so I'll wait with that until the end.

Design

In C++ as opposed to Java, when you assign an object you get a copy of the object which can be slow and it occupies extra memory for the copy.

I believe that there are two ways that you can improve this design:

1. Design a proper iterator that fulfills the contract of being an Iterator. It takes some doing but when you're done you it will not copy the contents and will be generally usable. One pitfall is how to define the end of the iterator.

2. Design a "view" over an existing container. This may or may not be more convenient depending on the use case.

The two ideas are kind of related but different concepts. You can store a view as a member and it makes sense but storing an iterator as a member is kind of dubious. Depending on your use case either a view or iterator is better, for this particular case I have a feeling that an iterator is better.

Implementation sketch as an iterator

Here I'll outline a start of an implementation of a random iterator and add a utility function in_random_order which provides nice syntactic sugar for use in range based for loops. I guess you could think of in_random_order as a poor-man's temporary view. Anyway here we go:

template<typename It>
class random_iterator{
    using it_traits = std::iterator_traits<It>;
public:
    // You must always provide these for all iterators 
    // or explicitly specialise std::iterator_traits 
    // for your iterator. It's easier to just provide them here.
    using iterator_category = it_traits::iterator_category;
    using value_type = it_traits::value_type;
    using difference_type = it_traits::difference_type;
    using pointer = it_traits::pointer;
    using reference = it_traits::reference;

    // This stores one iterator to each iterator position in the original 
    // container. Any modification of the original container invalidates
    // this iterator. We could use an LCG to avoid the linear memory.
    random_iterator(It first, It last){
        while(first != last){
            its.emplace_back(first);
            ++first;
        }
        // Shuffle the its vector.
    }

    random_iterator& operator ++(){
        ++it;
        return *this;
    }

    // Depending on if you want an input iterator, forward iterator, 
    // bidirectional or random access iterator you need to implement
    // various methods here. Check the concepts page linked earlier
    // for what you must provide.

    reference operator *(){
        return *(*it); // First de-ref gets original iterator
    }    

private:
    std::vector<It> its;
    std::vector<It>::iterator it;
};

template<typename Iterator>
class random_order{
public:
    in_random_order(Iterator f, Iterator l){
        first = f;
        last = l;
    }

    random_iterator<Iterator> begin(){
        return random_iterator(first, last);
    }

    random_iterator<Iterator> end(){
        return random_iterator(); // Figure out how to properly make end
    }

private:
    Iterator first;
    Iterator last;
};

// These functions are necessary because template argument deduction is not
// done for class templates. This is the final piece of the puzzle
// that enables the syntax below.
template<typename Container>
random_order in_random_order(Container& c){
    return random_order<Container::iterator>(c.begin(), c.end());
}

template<typename Iterator>
random_order in_random_order(Iterator first, Iterator last){
    return random_order<Container::iterator>(first, last);
}

When the above is properly implemented you should be able to do:

std::vector<X> data;

for(auto& value : in_random_order(data)){
    // stuff
}

// Or just a range:
for(auto& value : in_random_order(data.begin() + 10, data.begin() + 20)){
    // stuff
}

Note that for range based for to work, the object to be iterated over must provide member methods begin and end; or there must exist specialisations of std::begin and std::end for the object that is being iterated over.

This is why we invent the random_order class, it basically just provides the necessary boilerplate to make the fancy syntax possible in the for loop.

In fact, if you implement different types of iterators like for example filtering iterators and suitable iterables like filter which provide the requisite begin/end methods, you can do all manners of fun stuff by nesting iterators types like for example:

for(auto& : in_random_order(filter(data, 
                [](const X& x) { return x.isHappy();})) {

Although you can do the same with views I'd think the syntax is a bit more cumbersome.

Note: The above code uses a vector of indexes which is undesirable for an iterator. Iterators should ideally be a lightweight objects and are often assumed to be, for example they are often passed by value. This makes code that uses the random iterator slightly inefficient. This is worth keeping in mind or looking for a solution that doesn't need a lot of memory like this implementation does.

Answer 2

It's nice code - clean and well-presented. Thanks for including the test program; that really helps make reviewing easier.

I would choose not to make begin(), end() etc methods of the iterator itself, as that's not part of the iterator interface. Instead, I would create a shuffled_view class to return these indirect iterators.

You could probably cut down on your proliferation of constructors. I would have the public constructors delegate to a "fundamental" constructor that looks like:

shuffled_view(Iter first, Iter last, std::random_device& rd = random_device())

It would also be helpful to create a helper method (make_shuffled_view()?) to allow deduction of template parameters for a new instance, in the style of std::make_shared() and similar.

---

(I will add to this answer when I return from the weekend)

Answer 3

Just to complete others answers

Use const references

A container is usually heavy to copy, so I suggest you take it by const reference instead of by copy, so as to avoid a possibly expensive copy

explicit random_iterator(const Iterable& iterable)
explicit random_iterator(const Iterable& iterable, std::random_device& rd)

an alternative would be to use a move semantic for constructing your object, but that would work only if the Iterable type is std::vector<T>

You could also use const references when you iterate through the container because you aren't actually modifying the content of the container

for (const auto& x : iterable)

Beware the std::vector< bool>

If I want to pass an std::vector<bool> to your constructor, it is unlikely to work, because although it is compiler dependent, you usually cannot iterate through it using references, so you might want to specialise a constructor for it (or maybe not, but then you should document it).

The 'explicit' keyword

Not a big issue, but you are using the keyword explicit for a constructor that takes two arguments. Using this keyword is a very good habit to take, but is of use only for constructors taking exactly one argument.

Answer 4

Here some things i would improve.

Use better constructors

In your constructors you do not reserve the appropriate memory for the vector, which is not optimal. Also you use push_back() rather than emplace_back(). As far as I can see, there is no guarantee that the type of the elements of iterable is the same as T, so you might need implicit conversions for that. Also what happens if iterable is a basic type like double?

Use whats already there.

Why don't you simply derive you class from std::vector<T> and then generate your constructors by delegation?

template<typename T>
class random_iterator : public std::vector<T> {
    using baseType = std::vector<T>;

    template<typename Iterable>
    explicit random_iterator(const Iterable& iterable)
    : baseType(iterable.begin(), iterable.end())
    {
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(begin(), end(), g);
    }

    template<typename Iterable>
    explicit random_iterator(const Iterable&, std::random_device& rd)
    : baseType(iterable.begin(), iterable.end())
    {
        std::mt19937 g(rd());
        std::shuffle(begin(), end(), g);
    }
}

That way you get all the nice things about the container for free. Also note that the container is passed as a const reference, as you do not want to modify it. However, there is still the problem, hat the types of the iterable and the vector might not match.