Is there such an iterator?

[Arturo Cuebas]

I've got a bunch of file_iterator<> (http://tinyurl.com/3uuxa)
begin/end pairs that point to various chunks in a file. It would be
super-cool, in my program, to be able to treat all of these ranges as
though they were one huge range. I'm envisioning something along the
lines of a library facility that provides an iterator type that
encapsulates a set of ranges and abstracts out code to handle
traversal through all of them as though all the little sets of ranges
were one big one.

Maybe this will help clarify:

int main(void)
{
vector<pair<file_iterator<>, file_iterator<> >
ranges(2);

ranges.at(0).first = file_iterator<>("somefile.txt");
ranges.at(0).second = ranges.at(0).first + 5;

ranges.at(1).first = ranges.at(0).second + 5;
ranges.at(1).second = ranges.at(1).first + 5;

// this is fictional
typedef single_range_emulating_iterator</*some stuff here*/>
sre_iterator;

sre_iterator begin(ranges);
sre_iterator end = begin.make_end(); // or something

// this results in a traversal through all the ranges.
for_each(begin, end, some_operation());
}

Is there such a thing? Is such a thing possible?

 

[Siemel Naran]

I've got a bunch of file_iterator<> (http://tinyurl.com/3uuxa)
begin/end pairs that point to various chunks in a file. It would be
super-cool, in my program, to be able to treat all of these ranges as
though they were one huge range. I'm envisioning something along the
lines of a library facility that provides an iterator type that
encapsulates a set of ranges and abstracts out code to handle
traversal through all of them as though all the little sets of ranges
were one big one.

There is no such segmented iterator in the standard library, though the
implementation of std::deque is a little along the lines you describe.
Wonder if boost has such a class. Anyway, it would be something like

template <class Iter>
class segmented_iterator {
public:
typedef typename std::iterator_traits<Iter>::value_type value_type;
typedef typename std::iterator_traits<Iter>:ointer pointer;
segmented_iterator(const std::vector<Iter>& begins, const
std::vector<Iter>& ends);
reference operator*() const { return *d_iter; }
pointer operator->() const;
const segmented_iterator operator++(int) {
segmented_iterator out = *this;
++*this;
return out;
}
segmented_iterator operator++() {
++d_iter;
if (d_iter == d_ends[d_current]) {
++d_current;
if (d_current < d_begins.size()) {
d_iter = d_begins[d_current];
}
return *this;
}
}
bool operator!=(const segmented_iterator& that) const {
return
this->d_current != that.d_current
|| this->d_iter != that.d_iter
;
}
private:
std::vector<Iter> d_begins;
std::vector<Iter> d_ends;
size_type d_current;
Iter d_iter;
};

 

[Dietmar Kuehl]

I've got a bunch of file_iterator<> (http://tinyurl.com/3uuxa)
begin/end pairs that point to various chunks in a file. It would be
super-cool, in my program, to be able to treat all of these ranges as
though they were one huge range. I'm envisioning something along the
lines of a library facility that provides an iterator type that
encapsulates a set of ranges and abstracts out code to handle
traversal through all of them as though all the little sets of ranges
were one big one.

I don't know whether there is a ready made iterator for this (you
might want to check <http://www.boost.org/>) but it seems fairly
easy to create it: You just store your vector of pairs of iterators
(or a pointer to the corresponding vector) in one of the iterators.
The past-the-end iterator would store no data.

Effectively, you would create an iterator iterating over a sequence
of segments (quite similar to the iterator of 'std::deque'): It
would store information about the current segment and the position
of the segment in the vector of pairs. Advancing the iterator would
actually advance an iterator into the current segment switching to
the next segment if it hits the end of the current segment. If all
segments are processed, the iterator would compare equal to the
past the end iterator.

Here is an untested sketch of the code:

| template <typename Cont>
| class segment_pair_iterator
| {
| public:
| typedef typename Cont::value_type::first_type seg_iterator;
| segment_pair_iterator(): m_cont() { init(); }
| explicit
| segment_pair_iterator(Cont const& cont): m_cont(cont) { init(); }
|
| typename std::iterator_traits<seg_iterator>::reference
| operator*() const { return *m_seg_current; }
| segment_pair_iterator& operator++() {
| if (++m_seg_current == m_seg_end) {
| if (++m_cur_segment != m_cont.end()) {
| m_seg_current = m_cur_segment->first;
| m_seg_end = m_cur_segment->second;
| }
| }
| return *this;
| }
|
| bool operator== (segment_pair_iterator const& it) const {
| return (m_cur_segment == m_cont.end())
| == (it->m_cur_segment == it->m_cont.end());
| }
| // more members, mostly with derived logic...
| private:
| void init() {
| m_cur_segment = m_cont.begin();
| if (m_cur_segment != m_cont.end()) {
| m_seg_current = m_cur_segment->first;
| m_seg_end = m_cur_segment->second;
| }
| }
| Cont m_cont;
| typename Cont::const_iterator m_cur_segment;
| seg_iterator m_seg_current;
| seg_iterator m_seg_end;
| };

 

[clarkcox3]

Such a class wouldn't be that difficult to write, here's something that
I cobbled together just now (standard warning applies; hasn't been
tested, yadda, yadda, yadda), should give you an idea where to start


----Begin code ---
#include <deque>
#include <utility>

template<typename Iterator>
class DisjointIterator
{
public:
typedef std::input_iterator_tag iterator_category;
typedef typename std::iterator_traits<Iterator>::value_type
value_type;
typedef typename std::iterator_traits<Iterator>::difference_type
difference_type;
typedef typename std::iterator_traits<Iterator>:ointer pointer;
typedef typename std::iterator_traits<Iterator>::reference reference;
typedef const reference const_reference;
typedef const pointer const_pointer;

private:
bool m_is_end;
std::deque<std:air<Iterator,Iterator> > m_iters; //Pairs of begin
and end iterators
Iterator m_iter;
Iterator m_next_end;

void pop_next_iterator_range()
{
m_is_end = m_iters.empty();
if(!m_is_end)
{
m_iter = m_iters.front().first;
m_next_end = m_iters.front().second;
m_iters.pop_front();
}
}

public:
DisjointIterator() : m_is_end(true) {}
DisjointIterator(const DisjointIterator &other) :
m_is_end(other.m_is_end), m_iters(other.m_iters), m_iter(other.m_iter),
m_next_end(other.m_next_end) {}


template<typename IteratorListInputIterator> //Should be an
InputIterator into a sequence of std:air<Iterator,Iterator>
DisjointIterator(IteratorListInputIterator iter,
IteratorListInputIterator end)
{
for(;iter != end; ++iter)
{
if(iter->first != iter->second)
{
m_iters.push_back(*iter);
}
}

pop_next_iterator_range();
}

DisjointIterator &operator=(const DisjointIterator &other)
{
m_is_end = other.m_is_end;
m_iters = other.m_iters;
m_iter = other.m_iter;
m_next_end = other.m_next_end;
return *this;
}

DisjointIterator &operator++()
{
if(!m_is_end)
{
++m_iter;
if(m_iter == m_next_end)
{
pop_next_iterator_range();
}
}
return *this;
}

DisjointIterator operator++(int)
{
DisjointIterator temp(*this);
++*this;
return temp;
}

bool operator==(const DisjointIterator &other) const
{
if(m_is_end)
{
return other.m_is_end;
}
else
{
return m_iter == other.m_iter;
}
}

bool operator!=(const DisjointIterator &other) const { return
!operator==(other); }
reference operator*() { return *m_iter; }
const_reference operator*() const { return *m_iter; }

pointer operator->() { return &(operator*()); }
const_pointer operator->() const { return &(operator*()); }
};
---- end code ----

And, for a sanity check, I just used it like so:

---- begin code ----
#include <vector>
using std::vector;

#include <utility>
using std:air;
using std::make_pair;

#include <iterator>
using std:stream_iterator;

#include <iostream>
using std::cout;

int main()
{
vector<int> vec;

for(int i = 0; i<100; ++i)
{
vec.push_back(i);
}

vector<pair<vector<int>::iterator, vector<int>::iterator> > iters;

iters.push_back(make_pair(vec.begin(), vec.begin()+3));
iters.push_back(make_pair(vec.begin()+20, vec.begin()+20));
iters.push_back(make_pair(vec.begin()+21, vec.begin()+30));
iters.push_back(make_pair(vec.begin()+90, vec.end()));
iters.push_back(make_pair(vec.begin()+20, vec.begin()+25));

DisjointIterator<vector<int>::iterator>
disjoint_begin(iters.begin(), iters.end());
DisjointIterator<vector<int>::iterator> disjoint_end;

std::copy(disjoint_begin, disjoint_end, ostream_iterator<int>(cout,
", "));

cout << "\n";

return 0;
}
---- end code ----

Which produced the following output:
0, 1, 2, 21, 22, 23, 24, 25, 26, 27, 28, 29, 90, 91, 92, 93, 94, 95,
96, 97, 98, 99, 20, 21, 22, 23, 24,

 

[Larry Evans]

I've got a bunch of file_iterator<> (http://tinyurl.com/3uuxa)
begin/end pairs that point to various chunks in a file. It would be
super-cool, in my program, to be able to treat all of these ranges as
though they were one huge range. I'm envisioning something along the

[snip]
I don't know whether there is a ready made iterator for this (you
might want to check <http://www.boost.org/>) but it seems fairly

There's also something in the boost files that does something
similar. The file is:

http://groups.yahoo.com/group/boost/files/Joining Iterator Adaptor/

You have to join the group to see the file, but that's not hard.