Iterator to jump between container C ++
I have a container ints container. Let's admit deque< deque<int> >
. All numbers in deque<int>
are sorted in ascending order. Thus, the information 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 going through all the numbers deque<deque<int>>
in ascending order. This means that my iterator can jump between the containers, and after I will go through them, I will go through the numbers in this order: 1 4 5 5 7 7 9 11 12 22 44 1112
. How can i do this? I was thinking about putting all the numbers in one container and sorting them, but later, if I want to say *it = 10
, I can't, because I don't know where the container is specified it
. Therefore, any ideas and solutions are welcome :)
source to share
Focus on a constant iterator. Such an iterator must have an iterator for each of the requirements, but also for each of them (why is this explained to you below). But these iterators should be stored in a vector instead of a deque, because you will never pop or pop from either end of these containers, since the lifetime of such an iterator ends up modifying 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 (you probably also need the decrement operator, which can be implemented in a similar way) as well as the dereference operator.
The increment operator must find the deque iterator that is currently pointing to the smallest element and increment it.
The dereferencing operator also needs to find the deque iterator that is currently pointing to the smallest element and play it out.
If you are looking for the smallest element at the moment, ignore the signs that already indicate their end. To do this, you need all the deque end iterators. It might be helpful to remember the smallest element in another member variable so that dereferencing becomes a constant time operation. We store this current iterator as an iterator in the vector of iterators so that we can increment it (so the iterator in the vector changes).
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 can be implemented in a helper function that modifies the member variable current
as well at_end
. This needs to be called in the constructor to properly initialize 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 a vector of iterators ... I know this is a little confusing ...)
int operator *() const {
return **current;
}
And the increment will increment the current iterator (dereferenced), and also 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 with pre-increment:
nested_deque_iterator operator++(int) {
nested_deque_iterator old(*this);
++(*this);
return old;
}
We also need an 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 using equality:
bool operator!=(const nested_deque_iterator &o) const {
return !(*this == o);
}
Finally, write a start and end helper function for your nested queries.
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, also a container adapter (if you don't already have one) that uses these build helper functions as their default start 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 .
source to share
Implement your own iterator:
struct sorted_iterator {
int& operator*() { return *(*this->it); }
sorted_iterator& operator++() { ++(this->it); return *this;}
bool operator==( const sorted_iterator& other ) const;
bool operator!=( const sorted_iterator& other ) const;
private:
std::vector<int*> sorted;
decltype(sorted)::iterator it;
};
and inside it, inside, build a vector int*
std::vector<int*> sorted;
for( std::deque<int> x : main_container )
for( int& i : x )
sorted.push_back(&i);
auto compare = []( int* i, int* j ) { return *i < *j; }
std::sort( sorted.begin(), sorted.end(), compare );
source to share