Unordered container iteration

Question

My intention is to mask the implementation details of the container so that the client is not allowed to rely on the implicit insertion order. I am trying to apply this, somehow changing the order in which the iteration occurs.

I have a container that I want to arrange randomly during iteration. Here are some pseudo codes.

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 simply hold on to the std :: list member and do rand () to determine if the inserts are pasted in front or back.

Any other ideas?

I mainly use C ++ 03, but I have access to boost.

Answer 1

I'm not sure how much I understand all aspects of your problem. I think that what qualifies as a good solution depends a lot on the application and on what type of T will be in practice. In any case, I suggest changing the RandomList interface (see below).

First, your idea of ​​using std::list internally and randomly to insert front or back seems like a possible solution.

I don’t think it’s a good idea to use std::vector if you are targeting a wide range of applications. The reason is that std::vector implementations usually do a lot of extra stuff inside, which can harm the performance / memory requirements of your container type. Typically, std::vector uses a memory buffer that is larger than the actual size of the vector to avoid allocation during subsequent calls to insert operations, such as push_back . Thus, the performance of attachments can change on subsequent calls (suddenly you need to increase the vector buffer ...), and your container can use much more memory than is really necessary. Again: this may not be a problem, it depends on your application and what T really is. But as a user of your RandomList interface, it would be hard for me to hear that it uses std::vector internally ...

So, if you just ask for a “different idea” and also want to allow multiple inserts of the same value into the container - this is what: essentially make RandomList a wrapper in std::map . Randomization must be implemented by using the card key correctly. To iterate the container, you simply use the std::map iterator. This actually gives you links to pairs (key, value). You can use the std::map key to implement additional functions that may be interesting. First of all, you can hide the key type and, therefore, hide the details of your implementation by entering typedef RandomList::handle . I recommend that the insert method actually return RandomList::handle . This way you allow users to directly access specific container values ​​by adding the access method to your interface. access takes RandomList::handle as an argument and returns a link to the corresponding map value. If you change the interface in this way, you will agree that your RandomList iterator (which is only a map iterator) refers to the RandomList::handle and T pairs. Whether this is useful or not much depends on what T will be.

erase should accept RandomList::handle as an argument. Again: if multiple inserts are not welcome, the idea of ​​basing your implementation on std::map is problematic, or at least it should be approached differently.

This approach allows you to accurately control the "implementation of randomization." For example, if you use std::list with random inserts in front or behind, the randomization implementation is very closely related to your internal storage / container implementation. An implementation based on std::map could keep the details of randomization more independent from the rest of the implementation, since randomization is completely controlled in terms of choosing a map key. For example, if you use the int as key, you can hold the counter inside, which increases on subsequent inserts. The current counter value is used as a key for the next card insertion. Since this will result in a completely unbalanced tree structure, RandomList will behave like a regular std::list in iterations. I would suggest choosing new key values ​​so that the tree is perfectly balanced. Thus, the direct access function is implemented most efficiently (because search operations are fast), and a simple iteration of RandomList / std::map through begin() / end() should lead to a rather "random" result.

Finally, regarding the interface: I suggest you use perfect forwarding for the insert operation instead of a direct copy. Thus, you avoid unnecessary copy operations when inserting elements into std::map (the same story for std::list , of course), and you additionally allow move operations. If you do not want to use perfect redirects, at least change T to const T& , since another copy operation is required to insert the object into the std::list / std::map container.

Answer 2

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

Tony D's suggestion of using std::vector seemed good. I put the inserted value at the end and then swapped 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 (not templated) helper functor for getting 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 randomness, but this should be enough so that the client cannot make any assumptions about the order of the elements.

Answer 3

I would avoid random inserts and randomize the iteration. The idea that the large container is correct will be difficult to see visually, and understanding insertion problems is difficult.