Unordered Iteration of a Container

Question

My intent is to mask the implementation details of the container such that the client is not permitted to rely on the implicit insertion order. I'm trying to enforce this by somehow altering the order in which iteration occurs.

I have a container which I want to be randomly ordered when iterating. Here is some pseudo code.

namespace abc
{
template<class T>
class RandomList
{
  void insert(T t);
  T erase(T t);
  iterator begin();
  iterator end();
}
}

namespace test
{
  int main()
  {
    RandomList<int> list;
    list.insert(1);
    list.insert(2);
    list.insert(3);

    for (typename RandomList::iterator iter = list.begin();
         iter != list.end(); ++iter)
    {
       std::cout << iter << std::endl;
    }
  }    
}

Output:

3, 1, 2

My question is, what is the best way to implement RandomList. My naive thought is to just hold a member std::list and do rand() to determine whether insert does front inserts or back inserts.

Any other ideas?

I'm using mostly C++03, but I have access to boost.

Answer 1

I'm not sure I fully understand your use case but it is an interesting question nonetheless.

Tony D's suggestion to use a std::vector seemed like a good one. I've put the inserted value at the end and then swapped with a random element:

template<typename T>
class RandomList {
  std::vector<T> list;
  RandomIndex    randomIndex;
public:
  using iterator = typename std::vector<T>::const_iterator;
  iterator begin() { return list.begin(); }
  iterator end() { return list.end(); }

  void insert(const T& t) {
    list.push_back(t);

    auto i = randomIndex(list.size());

    using std::swap;
    swap(list[i], list.back());
  }
};

Where RandomIndex is a (non-templated) helper functor to get a random index:

class RandomIndex {
  std::mt19937 eng;
public:
  RandomIndex() : eng(std::random_device{}()) {}

  size_t operator()(size_t size) {
    auto dist = std::uniform_int_distribution<size_t>{0, size - 1};
    return dist(eng);    
  }
};

I'm not sure about the quality of the randomness but it should be enough to ensure a client can't make any assumptions about the order of the elements.