fixing absence of operator[] and at in list

[Shriramana Sharma]

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: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 ;
}

 

[Ian Collins]

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: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 ---

 

[Shriramana Sharma]

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.

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


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?

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.

 

[SG]

[...]
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