I have a container of container of ints. Lets say deque< deque<int> >. All the numbers in the deque<int> are sorted in ascending order. So the info in the container looks something like this:
deque<deque<int>> // main container
5 11 22 44 // deque<int> number 1
1 7 12 // deque<int> number 2
4 5 7 9 1112 // deque<int> number 3
I want to make an iterator that traverses thru all the numbers in deque<deque<int>> in ascending order. Meaning my iterator can jump between the containers and after I've gone through them all I will have traversed thru the numbers in this order: 1 4 5 5 7 7 9 11 12 22 44 1112. How can I accomplish this? I thought of putting all the numbers in one container and sorting them, but later if I want to say *it = 10 I won't be able because I don't know to which containers position is it pointing. So any ideas and solutions are welcomed :)
Let's focus on a const iterator. Such an iterator should hold an iterator to each of the deques, but also to each of their end (why you need this is explained below). But these iterators should be held in a vector instead of a deque, because you will never push or pop from either end of these containers, since the lifetime of such an iterator ends with a modification of your data structure.
So basically, you need the following structure:
struct const_iterator {
vector<deque<int>::const_iterator> iterators;
vector<deque<int>::const_iterator> ends;
//...
};
Now, you need to implement the increment operator (maybe you also want a decrement operator, which can be implemented analogously), as well as the dereferencing operator.
The increment operator needs to find the deque iterator which currently points to the smallest element, and increment that one.
The dereferencing operator also needs to find the deque iterator which currently points to the smallest element, and dereference that one.
If you're looking for the currently smallest element, ignore the deques which already point to their end. For this, you need all the deque's end iterators. It might be helpful to remember the currently smallest element in another member variable, such that dereferencing becomes a constant time operation. We store that current iterator as an iterator into the vector of iterators, such that we can increment it (so the iterator in the vector is changed).
struct nested_deque_iterator {
vector<deque<int>::const_iterator> iterators;
vector<deque<int>::const_iterator> ends;
vector<deque<int>::const_iterator>::iterator current;
bool at_end = false;
};
Updating the smallest element could be implemented in a helper function, which modifies the member variable current as well as at_end. This needs to be called in the constructor for a correct initialization of the member variable:
void update_current() {
if (!at_end && iterators.size() > 0) {
// At the beginning, we assume that we didn't find any
// new "next smaller element" in any deque.
at_end = true;
// Iterate through the deques (with two iterators in parallel)
for (auto i = iterators.begin(), e = ends.begin();
i != iterators.end() && e != ends.end();
++i, ++e)
{
// We ignore deques which are already at their end
if (i != e) {
// If we found a smaller next element (or the first try)...
if (at_end || *i < *next) {
// ... then replace the current iterator with it:
at_end = false;
current = i;
}
}
}
}
}
Then, dereferencing becomes as easy as dereferencing the current iterator twice (since it is an iterator into the vector of iterators... I know it is a bit confusing...)
int operator *() const {
return **current;
}
And incrementing will increment the (dereferenced) current iterator, as well as call the helper function to update it (this is the pre-increment operator):
nested_deque_iterator& operator++() {
if (!at_end) {
++(*current);
update_current();
}
}
You can implement the post-increment operator by means of pre-incrementing:
nested_deque_iterator operator++(int) {
nested_deque_iterator old(*this);
++(*this);
return old;
}
We also need the equality operator to compare iterators with each other:
bool operator==(const nested_deque_iterator &o) const {
// If either iterator is at the end, don't dereference current!
if (at_end || o.at_end) {
return at_end == o.at_end;
}
return *current == *(o.current);
}
And finally the inequality operator by means of equality:
bool operator!=(const nested_deque_iterator &o) const {
return !(*this == o);
}
Finally, write a begin and end construction helper function for your nested deques.
nested_deque_iterator nested_deque_begin(const deque<deque<int>> & deques) {
vector<deque<int>::const_iterator> iterators;
vector<deque<int>::const_iterator> ends;
for (const auto & d : deques) {
iterators.push_back(d.begin());
ends.push_back(d.end());
}
return { iterators, ends };
}
nested_deque_iterator nested_deque_end(const deque<deque<int>> & deques) {
vector<deque<int>::const_iterator> ends;
for (const auto & d : deques) {
ends.push_back(d.end());
}
return { ends, ends };
}
And if you want to, also a container adaptor (if you don't already have such) which uses these construction helper functions as their default begin and end methods:
struct nested_deque {
deque<deque<int>> deques;
//...
}
nested_deque_iterator begin(const nested_deque & nd) {
return nested_deque_begin(nd.deques);
}
nested_deque_iterator end(const nested_deque & nd) {
return nested_deque_end(nd.deques);
}
So you can write:
deque<deque<int>> mydeque = ...;
for (int i : nested_deque{mydeque}) {
// Here you go.
}
The full implementation is available here.