creating bidirectional iterator

[greeniekin]

I have searched the internet and have found no good examples.
With the only examples that I did find stated that this is not part of the standard and that it will be made unavailable.
It is 2am so forgive me if I missed something.
I also do not want to use other libries like boost.
A clear example of the correct way to do it would be fantastic.

The reason I want this is because I want to create a buffer of the last x values.
Essentially when I insert a new value to the front. One will be dropped from the back.

Though the idea is I will not be physically doing that. I will have an array of x size and when i add the new value I will over write the value to be dropped but to the user of it will be un aware of the implementation and the added value will appear at the front of the iterator.

Or I might be stuck with a std::list and actually dropping the first and inserting the last. Which is a bit clunky and will require deleting and allocating memory.

[Lowest0ne]

You're making what is called a circular buffer.

Consider the simple example of a double*

// needed variables
double *begin;
double *current;
double *end;

//Psuedo-Code
void create(const unsigned int size)
{
  begin = new int[size];
  current = begin;
  end = begin + (size - 1);
}

void add(double newDouble)
{
  *current = newDouble;

  // Here make it circular
  if (current == end) current = begin;
  else current++;
}

void print(void)
{
  double *iterator = current;
  do
  {
  std::cout << *iterator  << '\n';
  if (iterator  == end) iterator = begin;
  else iterator++;
  }
  while (iterator  != current);
}

Thats basically how it goes. You of course have to delete begin at some point, and take care of your pointers in general (set them to NULL when not in use). If you wanted to have something like char**, then this is even more critical. At that point, your add looks a little different, you have to delete then allocate:

char** begin;
char** current;
char** end;

void add(char* newString)
{
  if (*current) // we set every char* in the buffer to NULL upon construction
               // so this means there is a c-string here
  {
    delete [] *current;
  }
  
  *current = new char[strlen(String) + 1];
  strcpy(*current, String);

  if (current == end) current = begin;
  else current++;
}

If you're going all out with your iterator (has it's own class), then overload the ++ -- operators properly.

I did this for my C homework a while back (though wrote it in C++ first).
http://www.cplusplus.com/forum/beginner/74456/

That theoretically works if you set up main() with an ifstream to read from.

Edit: Oh yeah, and your print needs to know if the entire buffer has been used, or if current points to NULL. Why setting these things to NULL is important.

[greeniekin]

Thank you for the reply, but i was actually more interested in making a proper custom iterator. that behaved like the std list iterator and compatible with anything that uses a bidirectional iterator. if any one could make an example that would be great.

[ne555]

Checkout iterator_traits

[Lowest0ne]

I don't think it's possible. Iterating through a list is much different than iterating through a map or set.

I wouldn't worry about the clunky-ness of the push/pop. Most of the time here will be the construction/destruction of the object, something you'll have to do if you overwrite data anyway.

[naraku9333]

@greeniekin
I think LowestOne's idea of a circular buffer is probably best. If the size of the buffer is going to be static you can keep a pointer to the oldest node(the next one to be "deleted") and just change the data portion of the node.

[greeniekin]

I should not have mentioned what I wanted the iterator class for. People are focusing on how to implement that. Rather than the code that allows you to expose a pretty standard iterator externally.
The constructor and destructor is not an issue. As it will be used for primitive types like int's and floats.

LowestOne's is the implementation. Which is pretty much what I already have. I just want to have an iterator. One reason a linked list bidirectional iterator would be good for this is that it is essentially designed around the idea of a pointer to the previous element and the next element. which means at the end of the array I can have the next element point to the first element in the array. It matches very well.

ne555 comes closest. I thought I read somewhere that Iterator_Traits was the old method that was being discontinued though now I can not find it. Maybe it is the reverse. That Iterator_Traits is now the preferred method.

I would have really liked a complete example. Everywhere else seems to have partially complete examples which is driving me nuts. I have a horrible head ach and can not understand why no one anywhere has shown a complete example yet constantly talk about why iterators are so great.

[Lowest0ne]

One reason a linked list bidirectional iterator would be good for this is that it is essentially designed around the idea of a pointer to the previous element and the next element. which means at the end of the array I can have the next element point to the first element in the array. It matches very well.

Makes me think you're confusing an array with a list, but I don't think I'm right. One point of the iterator in a list is that it would be horrible to have a list.at() function. The iterator provides access to the data in the Node without revealing the actual Node pointer. What makes an iterator for a vector so great, not so sure.

Anyway, I've made things that act like iterators, but I don't think anyone would say "Thats a true c++ iterator". I guess I understand what you want, but the only thing making it not so great is the fact that a "current" needs to be in scope all of the time. Again, don't know much about it.

[greeniekin]

Just looked at the std_list iterator.

I hate looking at these though. They are never very clear.

They do not use iterator_traits at all

it just looks like a struct with one value for _M_node which is a pointer to another class. Then they just overload all the operators with ++ operator changing _M_node to _M_node->_M_next.

_M_node is set with a constructor like so _List_iterator(_List_node_base* __x) : _M_node(__x) { }


Looks like it will require 2 classes to make this work.

iterator_category is a bit strange "typedef std::bidirectional_iterator_tag iterator_category;" as it does no seem to be used at all in the iterator struct. bidirectional_iterator_tag is an empty struct and is just used to differentiate the different iterators.

It all makes much more sense when your not tired. Plus looking at the complete existing code. Even if it is from the stl.

Thanks all for chipping in.


After some fiddling it might be something like this with the class being called buffer and similar to lowestOne's (untested)

// iterator example
#include <iostream>
#include <iterator>
using namespace std;


class myiterator : public iterator<bidirectional_iterator_tag, double>
{
  double *pos;
  Buffer* p;
public:
  myiterator(Buffer* x,double *i) :p(x),pos(i) {}
  myiterator(const myiterator& mit) : p(mit.p),pos(mit.pos) {}
  myiterator& operator++() 
  {
     if(pos==p->end)
        pos=->begin;
     else
        p++;
     return *this;
  }
  myiterator operator++(int) {myiterator tmp(*this); operator++(); return tmp;}
  myiterator& operator--() 
  {
     if(pos==p->begin)
        pos=->end;
     else
        p--;
     return *this;
  }
  myiterator operator--(int) {myiterator tmp(*this); operator--(); return tmp;}
  bool operator==(const myiterator& rhs) {return pos==rhs.pos;}
  bool operator!=(const myiterator& rhs) {return pos!=rhs.pos;}
  double& operator*() {return *p;}
};

[JLBorges]

> I thought I read somewhere that Iterator_Traits was the old method that was being discontinued

std::iterator_traits<> is not deprecated. It is still required for tag dispatching. (AFAIK)


> I would have really liked a complete example.

A toy bidirectional iterator example:

#include <iterator>
#include <cmath>
#include <algorithm>
#include <iostream>

struct prime_number_iterator : std::iterator< std::bidirectional_iterator_tag, int, const int >
{
	explicit prime_number_iterator( int i ) : n( is_prime(i) ? i : next_prime(i) ) {}
	prime_number_iterator( int i, int ) : n( is_prime(i) ? i : previous_prime(i) ) {}

	reference operator*() { return n ; }

	prime_number_iterator& operator++() { n = next_prime(n) ; return *this ; }
	prime_number_iterator operator++(int)
	{ prime_number_iterator old_value(*this) ; ++*this ; return old_value ; }

	prime_number_iterator& operator--() { n = previous_prime(n) ; return *this ; }
	prime_number_iterator operator--(int)
	{ prime_number_iterator old_value(*this) ; --*this ; return old_value ; }

	bool operator== ( const prime_number_iterator& that ) const { return n == that.n ; }
	bool operator!= ( const prime_number_iterator& that ) const { return n != that.n ; }

	private: int n ;

    inline static bool is_prime( int n ) // caveat: inefficient
    {
        if( n < 2 ) return false ;
        if( n == 2 ) return true ;
        if( n%2 == 0 ) return false ;
        int root = int( std::sqrt( double(n) ) + 1.1 ) ;
        for( int i=3 ; i<root ; i+=2 ) if( n%i == 0 ) return false ;
        return true ;
    }

    inline static int next_prime( int n ) // caveat: inefficient
    { do ++n ; while( !is_prime(n) ) ; return n ; }

    inline static int previous_prime( int n ) // caveat: inefficient
    { do --n ; while( !is_prime(n) ) ; return n ; }

};

int main()
{
    prime_number_iterator begin(5000), end(5100) ;
    std::copy( begin, end, std::ostream_iterator<int>( std::cout, " ") ) ;
    std::cout << '\n' ;

    std::reverse_iterator<prime_number_iterator> rbegin( prime_number_iterator(5200,1) ),
                                                 rend(prime_number_iterator(5100,1)) ;
    std::copy( rbegin, rend, std::ostream_iterator<int>( std::cout, " ") ) ;
    std::cout << '\n' ;
}

Note: A bit of code can be saved by using boost iterator library.