Iterators over nested STL container

[Patrick Kowalzick]

Dear NG,

I have two containers (standard library) which are nested, e.g.:

std::vector< std::vector <int> > A;
std::list< std::vector<int> > B;

These structures where put in another class which I will name
ComposedContainer<T> for the moment.

For these I want to use a sequential iterator with a "flat" 1D-view. Below I
post my first approach iterator_2D. It is more pseudo code than
code......but,

-How shall I implement the functions
ComposedContainer<T>::begin()
ComposedContainer<T>::end()

-When I use only the two iterators of the nested containers, I do not have
access to begin() and end().

Indeed it seems that my approach is not well designed. Can somebody help me
out here?

Thanks, regards,
Patrick

// Iterator concept
template < class T >
class iterator_2D
{
public:
typedef T outer_container;
typedef outer_container::value_type inner_container;
typedef inner_container::value_type value_type;

typedef outer_container::iterator outer_iterator;
typedef inner_container::iterator inner_iterator;

// some more typedefs are missing

private:
// The iterator data
outer_iterator outer_it;
inner_iterator inner_it;

public:

// dereference
value_type & operator * ()
{
return * inner_it;
}

// not equal
bool operator != ( const iterator_2D & it )
{
return it1 != it.it1 || it2 != it.it2;
}

// increment
iterator_2D & operator++()
{
// This data access is stupid and not valid:
//if ( it1 != data.end() ) ++it2;
if ( it2 == (*it1).end() )
{
++it1;
// Same here for the data access
//if ( it1 != data.end() )
it2 = (*it1).begin();
}

return * this; // why does this not call the defined derefer above?
}
};

 

[Patrick Kowalzick]

Ups, sorry. Seems that my post was too early.

I have two containers (standard library) which are nested, e.g.:

std::vector< std::vector <int> > A;
std::list< std::vector<int> > B;

These structures where put in another class which I will name
ComposedContainer<T> for the moment.

For these I want to use a sequential iterator with a "flat" 1D-view. Below
I post my first approach iterator_2D. It is more pseudo code than
code......but,

-How shall I implement the functions
ComposedContainer<T>::begin()
ComposedContainer<T>::end()

see below. Code attached.

-When I use only the two iterators of the nested containers, I do not have
access to begin() and end().

Thats true. See Stoustrup page 19.3. He stores the container as a pointer as
well.

Indeed it seems that my approach is not well designed. Can somebody help
me out here?

This still stands. Do I have a conceptual error?

I append my new code (hopefully as a working example), and would be glad to
get some opinions.

Regards,
Patrick

#iclude <stdio>
#include <vector>

// Iterator concept
template < class T >
class iterator_2D
{
public:
typedef T outer_container;
typedef outer_container::value_type inner_container;
typedef inner_container::value_type value_type;

typedef outer_container::iterator outer_iterator;
typedef inner_container::iterator inner_iterator;

// some more typedefs are missing

//private:
// Pointer to the container
T * container;
// The iterator data
outer_iterator outer_it;
inner_iterator inner_it;

public:

// dereference
value_type & operator * ()
{
return * inner_it;
}

// not equal
bool operator != ( const iterator_2D & it )
{
return outer_it != it.outer_it || inner_it != it.inner_it;
}

// increment
iterator_2D & operator++()
{
if ( outer_it != container->end() ) ++inner_it;
if ( inner_it == (*outer_it).end() )
{
++outer_it;
if ( outer_it != container->end() )
inner_it = (*outer_it).begin();
}

return * this; // why does this not call the defined derefer above?
}
};

template < class T >
class ComposedContainer
{
public:
typedef T value_type;
typedef std::vector < value_type > inner_container;
typedef std::vector < inner_container > outer_container;

typedef iterator_2D < outer_container > iterator;

private:
outer_container data;

public:

ComposedContainer() {}
ComposedContainer( const size_t & size1, const size_t & size2)
{
resize( size1, size2 );
}
void resize( const size_t & size1, const size_t & size2)
{
data.resize( size1 );
for ( size_t i = 0; i < data.size(); ++i )
data.resize( size2 );
}

// element access
inner_container & operator[] ( const size_t pos1 )
{
return data[pos1];
}
const inner_container & operator[] ( const size_t pos1 ) const
{
return data[pos1];
}

// basic iterators
iterator begin()
{
iterator ret;
ret.container = &(this->data);
ret.outer_it = data.begin();
ret.inner_it = (*ret.outer_it).begin();
return ret;
}

iterator end()
{
iterator ret;
ret.container = &(this->data);
ret.outer_it = data.end();
ret.inner_it = (*(ret.outer_it - 1)).end();
return ret;
}

};


int main()
{
ComposedContainer<int> a;
ComposedContainer<int> b(3,3);

for ( size_t i = 0; i < 3; ++i )
for ( size_t j = 0; j < 3; ++j )
b[j] = (i + 1) * j;


for ( ComposedContainer<int>::iterator it = b.begin(); it != b.end();
++it )
{
int x = *it;
std::cout << x << std::endl;
}

return 0;
}

 

[Chris Theis]

Ups, sorry. Seems that my post was too early.

[SNIP]

I just did a quick check and the basic concept seems to be okay. However,
I'd suggest to keep your 2D iterator implementation standard lib compliant
and derive it from std::iterator like this:

template <class T>
class Iterator2D : public std::iterator< std::forward_iterator_tag, T,
ptrdiff_t> {

public:

// These type definitions are necessery to be compliant with the STL
// because it uses iterator traits.
typedef std::forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T& reference;
typedef T* pointer;

......

You'll find an example of implementing your own iterator in Nicolai Josuttis
book chapter 7.5.2

Cheers
Chris