Iterators over nested STL container

Discussion in 'C++' started by Patrick Kowalzick, Aug 3, 2005.

  1. 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, Aug 3, 2005
    #1
    1. Advertising

  2. 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;
    }
     
    Patrick Kowalzick, Aug 3, 2005
    #2
    1. Advertising

  3. Patrick Kowalzick

    Chris Theis Guest

    "Patrick Kowalzick" <> wrote in message
    news:newscache$gdbnki$x11$...
    > Ups, sorry. Seems that my post was too early.
    >
    >> I have two containers (standard library) which are nested, e.g.:
    >>

    [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
     
    Chris Theis, Aug 3, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Russ Perry Jr
    Replies:
    2
    Views:
    4,283
    Russ Perry Jr
    Aug 20, 2004
  2. Maitre Bart
    Replies:
    2
    Views:
    548
    Maitre Bart
    Feb 11, 2004
  3. moggous phar
    Replies:
    1
    Views:
    391
    Gianni Mariani
    Oct 15, 2004
  4. Replies:
    4
    Views:
    829
    Daniel T.
    Feb 16, 2006
  5. wolverine
    Replies:
    2
    Views:
    481
    Marcus Kwok
    Jul 24, 2006
Loading...

Share This Page