Jump to content
  • Advertisement
Sign in to follow this  
twix

I need a fancy iterator (C++)

This topic is 4157 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Let's say I have a class with a list of objects. I need to iterate over every distinct *pair* of objects in the list. I want an STL-compatible iterator that 'flattens' this process into a single loop, with a value_type of std::pair<MyObject, MyObject>. I'm trying to use boost::iterator_facade to do this, but I can't think of a way to define the constructor that initializes an iterator from its value_type. And even the increment operation is troublesome, because I need to know about the end of the list. Is there some magic that can accomplish this, or maybe an equally convenient iterator-ish interface for doing the same thing? Further, (and this is the point of all this, really) is it possible to have my class generate iterators of this type, which iterate over only a *subset* of all the distinct pairs, according to the state of the class?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by twix
I'm trying to use boost::iterator_facade to do this, but I can't think of a way to define the constructor that initializes an iterator from its value_type. And even the increment operation is troublesome, because I need to know about the end of the list.


It would be possible to create an iterator from two sequences [a,b) and [c,d) represented by four iterators. For obvious reasors, the iterator would be a constant one.

The implementation would consist in keeping around all four iterators, the length of each sequence (as computed with std::distance) plus an additional pair of iterators representing the current position. An additional "end" flag for the iterator would be great as well.

Quote:
Further, (and this is the point of all this, really) is it possible to have my class generate iterators of this type, which iterate over only a *subset* of all the distinct pairs, according to the state of the class?


Rectangular subsets only.

Share this post


Link to post
Share on other sites
Hm, this is disappointing.

I guess I'll just have to content myself with not having STL compatibility, and just have my class output a stream of pairs.

Thanks for clearing this up for me!

Share this post


Link to post
Share on other sites
I'm relatively new to writing iterators, and I didn't understand ToohrVyk's post, so it is quite possible that I'm missing something here. But it doesn't seem that hard to me. I quickly hacked up the following (if there's something Dangerously Wrong with it, someone please tell me):

template <class T, class C = list<T> >
class pair_iterator {
typedef typename C::iterator listiter;
listiter pos1, pos2, end;
public:
typedef pair<T,T> value_type;
typedef input_iterator_tag iterator_category;
typedef int difference_type;
typedef pair<T,T>* pointer;
typedef pair<T,T>& reference;

pair_iterator(listiter start, listiter end_):
pos1(start),
pos2(start),
end(end_) {
}

pair_iterator& operator++() {
++pos2;
if (pos2 == end) {
++pos1;
pos2 = pos1;
}
return *this;
}

pair_iterator operator++(int) {
pair_iterator<T> result = *this;
++(*this);
return result;
}

bool operator==(const pair_iterator& other) const {
return other.pos1 == pos1 && other.pos2 == pos2;
}

bool operator!=(const pair_iterator& other) const {
return !(*this == other);
}

value_type operator*() const {
return make_pair(*pos1, *pos2);
}
};


Share this post


Link to post
Share on other sites
Quote:
Original post by twix
Let's say I have a class with a list of objects. I need to iterate over every distinct *pair* of objects in the list. I want an STL-compatible iterator that 'flattens' this process into a single loop, with a value_type of std::pair<MyObject, MyObject>.

Do you mean you wish to iterate over the list pair-wise (eg. it(i) = L(2i, 2i + 1)), or is the pair association function something different entirely? It's very difficult to implement any software without a specification.
Quote:
I'm trying to use boost::iterator_facade to do this, but I can't think of a way to define the constructor that initializes an iterator from its value_type. And even the increment operation is troublesome, because I need to know about the end of the list.

I'm not familiar with boost::iterator_facade, but an iterator is a class that contains a reference to a range object and a cursor state withing that range. At no time does it make sense to create an iterator for its value_type. You generally have to create an iterator with the range and state.

Oh, and the iterator does not have to know about the end of the list. The list knows about the end of the list and the client code will compare two iterators for equality.
Quote:
Is there some magic that can accomplish this, or maybe an equally convenient iterator-ish interface for doing the same thing?

I don't imagine. You will have to write your software yourself.
Quote:
Further, (and this is the point of all this, really) is it possible to have my class generate iterators of this type, which iterate over only a *subset* of all the distinct pairs, according to the state of the class?

Quite. That's the whole point of iterators. They traverse a half-open range with state. They do not traverse a class, or even an instance of that class.

Here's the basics:

(1) Derive your iterator class from std::iterator -- this will define the common typedefs to make your iterators wok nicely with the standard algorithms.
(2) Implement the &, *, ++, ++(int), and -> operators (at minimum: you'll want even more operators for bidirectional or random-access iterators) and == and != functions.
(3) Provide an appropriate set of constructors including a nullary default contructor to construct a singular instance.
(4) Provide an appropriate set of functions in your container class to construct a non-singular iterator object -- usually begin, end, const begin, const end, but if you want fancy subset stuff, provide an appropriate pair of functions to returns non-singular iterators defining that half-open range.

Done. It's that easy.

Share this post


Link to post
Share on other sites
Quote:
I'm relatively new to writing iterators, and I didn't understand ToohrVyk's post, so it is quite possible that I'm missing something here. But it doesn't seem that hard to me. I quickly hacked up the following (if there's something Dangerously Wrong with it, someone please tell me):


That's close to generic.

A somewhat "better" solution might be to simply not assume anything about types.

// Not an iterator, just class definition

template < class ListA, class ListB >
class pair_iterator
{
typename ListA::const_iterator IteratorA;
typename ListB::const_iterator IteratorB;

IteratorA ia;
IteratorB ib;

ListA &container_a;
ListB &container_b;

pair_iterator &operator++()
{
++ia;
if (ia == container_a.end() ) {
++ib;
ia = container_a.begin();
}
return *this;
}
};



This would obviously need to be converted into an iterator compatible class, but this way, you can combine two containers of arbitrary types, using nothing but iterators. I'd say this is as generic as it gets.

Share this post


Link to post
Share on other sites
I think you're all missing the point. What we need is a way to *transform* an existing iterator into an iterator-over-pairs. For this we can create an *iterator adapter*. Following the example of the standard library reverse_iterator, we get something like this (I *think* I've dealt properly with various tricky issues):


// pair_iterators are always const_iterators.
template <typename Iterator>
class pair_iterator:
public std::iterator<typename iterator_traits<Iterator>::iterator_category,
typename iterator_traits<Iterator>::value_type,
typename iterator_traits<Iterator>::difference_type,
typename iterator_traits<Iterator>::pointer,
typename iterator_traits<Iterator>::reference> {
Iterator current;
typedef typename traits::value_type base_value_type;

public:
typedef iterator_traits<Iterator> traits;
typedef Iterator iterator_type;
typedef typename traits::difference_type difference_type;
typedef std::pair<base_value_type, base_value_type> value_type;
typedef std::auto_ptr<value_type> pointer;

pair_iterator(): current() {}

explicit pair_iterator(iterator_type it) : current(it) {}

// Because of the template, we need to explicitly specify a cctor.
pair_iterator(const pair_iterator& it): current(it.current) {}

template<typename It2>
pair_iterator(const pair_iterator<It2>& it): current(it.base()) {}

iterator_type base() const { return current; }

value_type operator*() const {
return std::make_pair(*current, *(current + 1));
}

pointer operator->() const {
return pointer(new value_type(**this));
}

pair_iterator& operator++() {
current += 2;
return *this;
}

pair_iterator operator++(int) {
pair_iterator tmp = *this;
++*this;
return tmp;
}

pair_iterator& operator--() {
current -= 2;
return *this;
}

pair_iterator operator--(int) {
pair_iterator tmp = *this;
--*this;
return tmp;
}

pair_iterator operator+(difference_type n) const {
return pair_iterator(current + 2 * n);
}

pair_iterator& operator+=(difference_type n) {
current += 2 * n;
return *this;
}

pair_iterator operator-(difference_type n) const {
return pair_iterator(current - 2 * n);
}

pair_iterator& operator-=(difference_type n) {
current -= 2 * n;
return *this;
}

value_type operator[](difference_type n) const {
return *(*this + n);
}
};

// If they're adjacent, we want them to compare equal, probably.

template<typename Iterator>
inline bool operator==(const pair_iterator<Iterator>& x,
const pair_iterator<Iterator>& y) {
Iterator xb = x.base();
Iterator yb = y.base();
if (xb < yb) { ++xb; }
if (yb < xb) { ++yb; }
return xb == yb;
}

template<typename Iterator>
inline bool operator<(const pair_iterator<Iterator>& x,
const pair_iterator<Iterator>& y) {
Iterator xb = x.base();
Iterator yb = y.base();
if (xb < yb) { ++xb; }
return xb < yb;
}

// etc. etc.

template <typename Iterator>
inline typename pair_iterator<Iterator>::difference_type
operator-(const pair_iterator<Iterator>& x,
const pair_iterator<Iterator>& y) {
return (x.base() - y.base()) / 2; }

template<typename Iterator>
inline pair_iterator<Iterator>
operator+(typename pair_iterator<Iterator>::difference_type n,
const pair_iterator<Iterator>& x) {
return x + n;
}

Share this post


Link to post
Share on other sites
Ah, sorry guys, I guess I wasn't completely clear.

I need to iterate over *every* distinct pair in the list, not just pairs of adjacent objects, and possibly an arbitrary subset of all the distinct pairs. So basically, the equivalent of this loop:


for (int i = 0; i < end; ++i)
for (int j = i; j < end; ++j)
{
if (count_pair(i, j))
do_stuff(pair(i,j));
}





turning into just this:


for (my_iterator i = my_class.begin(); i != my_class.end(); ++i)
do_stuff(*i);




I now realize it indeed makes no sense to construct an iterator from its value_type (I was a little braindead last night [grin]), but now I'm confused. Are any particular constructors required for an iterator to be fully STL-compatible?

Share this post


Link to post
Share on other sites
Input and output iterators are required to be copy constructable. Forward iterators are additionally required to be default constructable.

Share this post


Link to post
Share on other sites
Alright, thanks. Sounds like this kind of iterator should be doable, then. I'll see if I can't get it to work.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!