fixing absence of operator[] and at in list

Discussion in 'C++' started by Shriramana Sharma, Apr 22, 2013.

  1. I have been wanting to use a container with efficient inserts and deletes in the middle. Hence it seems list is my choice. But I also require indexed access which list doesn't provide. Hence I thought of the following workaround. Since I'm not an expert, I'd like comments from the experts here. Thanks.

    --- randomlist.hpp ---

    # include <list>
    # include <algorithm>
    # include <stdexcept>

    namespace std
    {

    template < typename T >
    class randomlist : public list<T>
    {
    typedef typename list<T>::reference reference ;
    typedef typename list<T>::const_reference const_reference ;
    typedef typename list<T>::size_type size_type ;
    typedef typename list<T>::iterator iterator ;

    protected :
    void range_check ( size_type n ) const
    {
    if ( n >= this->size() ) throw std::eek:ut_of_range ( "randomlist index out of range" ) ;
    }

    public :
    // element access
    // this is what is missing from list

    reference operator [] ( size_type n )
    {
    iterator it = this->begin() ;
    std::advance ( it, n ) ;
    return *it ;
    }

    const_reference operator [] ( size_type n ) const
    {
    iterator it = this->begin() ;
    std::advance ( it, n ) ;
    return *it ;
    }

    reference at ( size_type n )
    {
    range_check ( n ) ;
    return (*this)[n] ;
    }

    const_reference at ( size_type n ) const
    {
    range_check ( n ) ;
    return (*this)[n] ;
    }
    } ;

    } // namespace std

    --- randomlist-test.cpp ---

    # include "randomlist.hpp"
    # include <iostream>
    using namespace std ;

    int main ()
    {
    randomlist<int> l1 ;
    l1 << 1 << 2 << -1 << 4 << -5 << 6 ;
    cout << l1[6] << endl ;
    cout << l1.at(6) << endl ;

    // list<int> l2 ;
    // l2 . push_back ( 10 ) ;
    // cout << l2[0] << endl ;
    }
     
    Shriramana Sharma, Apr 22, 2013
    #1
    1. Advertising

  2. Shriramana Sharma

    Ian Collins Guest

    Shriramana Sharma wrote:
    > I have been wanting to use a container with efficient inserts and
    > deletes in the middle. Hence it seems list is my choice. But I also
    > require indexed access which list doesn't provide. Hence I thought of
    > the following workaround. Since I'm not an expert, I'd like comments
    > from the experts here. Thanks.


    {please fix the inevitable mess goggle will make of your responses!}

    What is more important to you, efficient inserts, or efficient random
    access? That call is what usually determines which container type best
    fits your needs.

    > --- randomlist.hpp ---
    >
    > # include <list>
    > # include <algorithm>
    > # include <stdexcept>
    >
    > namespace std


    You shouldn't be adding your own types to std.

    > {
    >
    > template < typename T >
    > class randomlist : public list<T>


    Deriving publicly from standard containers is invariably a bad idea. If
    you need to specialise one, you are better off using it as a private base.

    > {
    > typedef typename list<T>::reference reference ;
    > typedef typename list<T>::const_reference const_reference ;
    > typedef typename list<T>::size_type size_type ;
    > typedef typename list<T>::iterator iterator ;
    >


    Why would these be private?

    > protected :
    > void range_check ( size_type n ) const
    > {
    > if ( n >= this->size() ) throw std::eek:ut_of_range ( "randomlist index out of range" ) ;
    > }
    >
    > public :
    > // element access
    > // this is what is missing from list
    >
    > reference operator [] ( size_type n )
    > {
    > iterator it = this->begin() ;
    > std::advance ( it, n ) ;
    > return *it ;
    > }
    >
    > const_reference operator [] ( size_type n ) const
    > {
    > iterator it = this->begin() ;
    > std::advance ( it, n ) ;
    > return *it ;
    > }
    >
    > reference at ( size_type n )
    > {
    > range_check ( n ) ;
    > return (*this)[n] ;
    > }
    >
    > const_reference at ( size_type n ) const
    > {
    > range_check ( n ) ;
    > return (*this)[n] ;
    > }
    > } ;
    >
    > } // namespace std
    >
    > --- randomlist-test.cpp ---



    --
    Ian Collins
     
    Ian Collins, Apr 22, 2013
    #2
    1. Advertising

  3. On Monday, April 22, 2013 6:52:53 AM UTC+5:30, Ian Collins wrote:
    > What is more important to you, efficient inserts, or efficient random
    > access? That call is what usually determines which container type best
    > fits your needs.


    I understand: if efficient random access was an issue I'd be using deque. OK I have a question about deque but I'll ask that separately.

    > > namespace std

    > You shouldn't be adding your own types to std.


    OK.

    > > class randomlist : public list<T>

    >
    > Deriving publicly from standard containers is invariably a bad idea. If
    > you need to specialise one, you are better off using it as a private base..


    Can you explain *why* public inheritance from STL containers is bad?

    > > typedef typename list<T>::reference reference ;
    > > typedef typename list<T>::const_reference const_reference ;
    > > typedef typename list<T>::size_type size_type ;
    > > typedef typename list<T>::iterator iterator ;

    >
    > Why would these be private?


    Oh, I didn't intend to make them private. Actually first I didn't write these lines at all, assuming that the typedef-s from the base class would propagate, but both GCC and CLang gave me "* does not name a type" errors. Why wouldn't they propagate, though, given that I'm doing public inheritance and those are public typedefs?!

    Shriramana SHarma.
     
    Shriramana Sharma, Apr 22, 2013
    #3
  4. Shriramana Sharma

    SG Guest

    On Apr 22, 10:13 am, Andy Champ wrote:
    > [...]
    > What you might like to consider (and I've seen this before somewhere,
    > possibly boost?) is a collection of collections. Have a vector of
    > vectors, and put a few hundred of your objects in each of the child
    > vectors. You'll get fast iteration (usual case defers to vector's
    > iterator) not too slow insertion (either you grow a child vector, or you
    > split it at the insertion point - you don't have to copy the whole lot)
    > and faster random access that your suggestion - which will be linear time
     
    SG, Apr 22, 2013
    #4
    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. =?Utf-8?B?Um95?=

    Debugging ASP.NET in absence of VS.NET

    =?Utf-8?B?Um95?=, Dec 13, 2005, in forum: ASP .Net
    Replies:
    5
    Views:
    1,269
    JIMCO Software
    Dec 15, 2005
  2. taylorius
    Replies:
    1
    Views:
    299
    Matt Humphrey
    Jan 8, 2004
  3. Rafal Majda
    Replies:
    2
    Views:
    952
    Thomas Weidenfeller
    Apr 12, 2005
  4. Erik  Bethke
    Replies:
    1
    Views:
    1,919
    Erik Bethke
    Feb 8, 2005
  5. Sara
    Replies:
    6
    Views:
    275
    John W. Krahn
    Apr 12, 2004
Loading...

Share This Page