Extending std::list

I need to use lists for my program and needed to decide if I use std::vector or std::list. The problem with vector is that there is no remove method and with list that there is no operator []. So I decided to write my own class extending std::list and overloading the [] operator.

My code looks like this:

#include <list>

template <class T >
class myList : public std::list<T>
{
public:
T operator[](int index);
T operator[](int & index);
myList(void);
~myList(void);
};

#include "myList.h"

template<class T>
myList<T>::myList(void): std::list<T>() {}

template<class T>
myList<T>::~myList(void)
{
std::list<T>::~list();
}

template<class T>
T myList<T>::operator[](int index) {
int count = 0;
std::list<T>::iterator itr = this->begin();
while(count != index)itr++;
return *itr; 
}

template<class T>
T myList<T>::operator[](int & index) {
int count = 0;
std::list<T>::iterator itr = this->begin();
while(count != index)itr++;
return *itr;
}

I can compile it but I get a linker error if I try to use it. Any ideas?

From stackoverflow

• Vectors have the erase method that can remove elements. Is that not sufficient?

  Alexander Stolz : Its not as easy to use as the remove method in std::list

  Jasper Bekkers : Then use std::remove instead?

  Alexander Stolz : Didn't know about that. I will look at it

  rstevens : @blizzarac: Why is it not easy? Isn't myvec.erase(myvec.begin() + index) easy enough (index is a simple size_t!)?

• You have to move all your template code into header.

• All template code should be put in header file. This fill fix linking problems (that's the simplest way). The reason it happens is because compilers compiles every source (.cc) file separately from other files. On the other hand it needs to know what code exactly it needs to create (i.e. what is the T in template is substituted with), and it has no other way to know it unless the programmer tells it explicitly or includes all the code when template instantiation happens. I.e. when mylist.cc is compiled, it knows nothing about mylist users and what code needs to be created. On the other hand if listuser.cc is compiled, and all the mylist code is present, the compiler creates needed mylist code. You can read more about it in here or in Stroustrup.

  Your code has problems, what if user requests negative or too large (more than amount of elements in the list). And i didn't look too much.

  Besides, i don't know how u plan to use it, but your operator[] is O(N) time, which will probably easily lead to O(N*N) loops...

  Michael Burr : "your operator[] is O(N) time" - this is exactly why it is not included in the standard's `std::list<>`.

• Given your original problem statement,

  I need to use lists for my program and needed to decide if I use std::vector or std::list. The problem with vector is that there is no remove method and with list that there is no operator [].

  there is no need to create your own list class (this is not a wise design choice anyway, because std::list does not have a virtual destructor, which is a strong indication that it is not intended to be used as a base class).

  You can still achieve what you want using std::vector and the std::remove function. If v is a std::vector<T>, then to remove the value value, you can simply write:

  #include <vector>
  #include <algorithm>
  T value = ...; // whatever
  v.erase(std::remove(v.begin(), v.end(), value), v.end());
  

  dalle : That should be: v.erase(std::remove(v.begin(), v.end(), value), vec.end());

  ChrisN : You're right, of course. Thanks.

  Martin York : And a single element version: v.erase(std::find(...));

  Mr.Ree : If you knew the element index you wanted to erase, for example v[3], you could also use v.erase(v.begin()+3). Random Access Iterators and all that...

• The obvious stuff has already been described in details:
  

  But the methods you choose to implement??

  • Destructor.
    • Not required compiler will generate that for you.
  • The two different versions of operator[] are pointless
    • Also you should be uisng std::list::size_type as the index
    • Unless you intend to support negative indexes.
  • There are no const versions of operator[]
  • If you are going to implement [] you should also do at()
  • You missed out all the different ways of constructing a list.
  • Containers should define several types internally
    • see http://www.sgi.com/tech/stl/Container.html

• In addition to other excellent comments, the best way to extend a standard container is not by derivation, but writing free functions. For instance, see how Boost String Algorithms can be used to extend std::string and other string classes.

• There is no need to call destructor of std::list , because you already derive from std::list when destructor called for myList automatically std::list destructor will be called.

  gbjbaanb : note that std::list doesn't have a virtual destructor.

  Nemanja Trifunovic : A lack of the virtual destructor would be a problem only if he tried to delete an object of myList through a pointer to std::list, which would be a really weird use of a container anyway.

  gbjbaanb : true, but worth reminding anyway.

• Depending on your needs, you should use std::vector (if you need often appends/removes at the end, and random access), or std::deque (if you need often appends/removes at the end or at the beginning, and your dataset is huge, and still want random access). Here is a good picture showing you how to make the decision: