Solved

Wrapper class for std::list that supports pointers and non-pointers

Posted on 2012-03-13
29
417 Views
Last Modified: 2012-08-14
I have written a wrapper class around the std::list template.
I have not inherited from the std::list for many reasons; one of them being it has no virtual destructor.
My reasons for doing this are valid, and I will not go into them here.
However, I have hit a problem:
My class is defined as

template<class TYPE>
class List
{
public:
    List(void){};
    virtual ~List(void){};
    ...
    inline bool IsEmpty(void) { return m_list.empty(); }
    ...

    inline void Clear();
private:
    std::list<TYPE> m_list;
};

in the inline file for the template declaration:


template<class TYPE>
void List<TYPE>::Clear(void)
{
    if ( !m_list.empty() )
    {
        ListIndex iter = m_list.begin();
        TYPE item = *iter;

        if ( IsPointerType( item ))
        {
            while ( m_list.size() > 0 )
            {
                TYPE& item = m_list.front();
                delete item;                                 // <<-- problem is here
                m_list.pop_front();
            }
        }
        else
        {
            m_list.clear();
        }
    }
}

Now, if the list is populated with pointers to objects, this works well.
However, if the list template is used to store non-pointer objects, the code will not compile.
How can I come up with a definition that will support both objects and pointers to objects and still compile?
0
Comment
Question by:Orcbighter
  • 13
  • 13
  • 3
29 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 37718495
Is this getting philosophical when I start to theorize about deleting objects you don't really 'own'? And yes, i mean it.
0
 
LVL 86

Expert Comment

by:jkr
ID: 37718504
Or, to be more blunt: You are deciding to use a container to store pointers. Fine, yet I'd rather let the coder/you to be responsible for the cleanup, not the container - and neither would I expect that - just think of a

List<char*> MyList;

  MyList.Add'("this is a string literal"); // OK, I am making the method's name up, but you know what I mean

  MyList.Clear(); // now you'dend up in calling 'delete' for a string literal -> instant segfault

Open in new window

0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37718649
Thanks for your response jkr,
though I did ask for helpful responses, not philosophical diatribes.

I am providing a template class for developers to use, as such, it is my responsibility to try and ensure that the code is as robust as possible.
I don't agree with your argument about "...deleting objects I don't really own". By providing a container for objects, or pointers to objects, that container is accepting responsibility!

If my class is not going to accept responsibility, then it is my responsibility as the designer to let the programmers using my class know in some way, either at compile time or run-time, that this is the case.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37718688
You could specialize the Clear function for pointers, so you can do something different for pointers compared to objects.

However, you should probably use smart pointers instead (ala boost::shared_ptr eg.), and avoid the whole issue altogether. While at the same time addressing the ownership issue jkr pointed out.
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37718737
I hear what you are saying about smart pointers, and I have in fact created a template class that uses the smart_ptr<>.
However, I have created a non-pointer class for objects, and am trying to cater for the case of someone using it to store raw C++ pointers.

If My class is declared thus:
List<dummyObject*> myList
and I call myList.Clear()
all is well.

However, If my class is declared thus:
List<dummyObject> myList
and I call myList.Clear()
I get a compiler error at the line with the delete statement.

My current solution is to provide a second method called ClearPointers()
which will use RTTI to determine if the type in the list is a pointer, and if so, iterate through the list, popping and deleting, and if not, just calling the std::list::clear() method.

In the Clear() method, I use RTTI to test the type stored in the list, and if it is a pointer to spit out an error message and abort, or throw an exception.

I was hoping for a solution that would allow me to have one method named "Clear", even if I had to overload it, Hence my question here.
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 37719093
>> I was hoping for a solution that would allow me to have one method named "Clear", even if I had to overload it, Hence my question here.

And that's why I suggested to specialize the Clear function for pointer types.

Example :

template <typename T>
class ListBase {
  public :
    ListBase(void) { }
    virtual ~ListBase(void) { }

    // ...

    void clear(void);

  private :
    std::list<T> m_list;
};

template <typename T>
class List : public ListBase<T> {
};

template <typename T>
class List<T*> : public ListBase<T*> {
  public :
    void clear(void);
};

template <typename T>
void ListBase<T>::clear(void) {
  // code here for clearing a list of objects
}

template<typename T>
void List<T*>::clear(void) {
  // code here for clearing a list of pointers
}

Open in new window



But I'd like to re-iterate my recommendation to use reference-counted smart pointers here.

That way, your list does NOT need special behavior for pointers, and can treat everything as an object.

So :

List<int> would store int's, and own them.
List<int*> would store pointers to int. It owns the pointers, but NOT the int's they point to.
List<boost::shared_ptr<int> > would also store pointers to int, but in this case reference counted smart pointers. This means that the list has shared ownership of the int's they point to. It also means that the user can transfer full ownership to the list if it wants to, or can keep a pointer to the int for its own use.

If you then phase out the use of List<int*> altogether, you've got a more robust solution.
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37719220
Yes, you are suggesting something I have already done.
I guess I could just abandon the idea of a list template for non-pointers and stay with my design of list using shared pointers.
I would not use Boost. I see no point in dragging in third-party libraries with all their attendant problems when I can use standard C++. My list uses the shared pointer from the tr1 namespace of the standard template library.

The only drawback is that such a list is using the heap to store its data rather than the stack. A large list of objects might have resource implications.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37719271
>> Yes, you are suggesting something I have already done.

Are you sure ? The current solution you described involved providing a function with a different name. It did not involve specializing the existing clear function.


>> I would not use Boost. I see no point in dragging in third-party libraries with all their attendant problems

boost::shared_ptr is an include-only library, so no extra runtime dependencies. It's also a very well-tested library - I've never had any problems with it.


>> My list uses the shared pointer from the tr1 namespace of the standard template library.

That's ok too. It's compatible with boost::shared_ptr (apart from the different namespace).
You might be interested to know that std::shared_ptr is in C++11.


>> The only drawback is that such a list is using the heap to store its data rather than the stack. A large list of objects might have resource implications.

I'm not following you here. How would a list of objects or raw pointers involve the stack ? If you mean you are storing pointers to stack allocated objects, then you most definitely should NOT call delete for those pointers.

std::list's contents are on the heap, not the stack (unless you are doing some funky stuff with memory allocators, or are working on an exotic platform).
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37719465
Sorry I was unclear.
I have created two template classes that wrap the std::list template class.
The first one stored shared pointers and there was no need to do anything else except call the std::list::clear method, since the shared pointer would call the objects destructor the minute it went out of scope. Done and dusted.

The second list class was designed to store objects, without making them pointers, eg

class Porridge;

List<Porridge> myList

The std::list::clear method is fine here too, since the object's destructor is called.
However, I can see someone using my class to store pointers, eg

List<Porridge*> myList

In this case, the destructors will not be called when the list is cleared.
I tried, using RTTI, to deterrmine if the type of object stored in the list is a pointer, if not then just call the std::list::clear method.
If it was a pointer, then iterate through the list and delete each item after popping it from the list.
Sounded simple, and it works if the list contains pointers
List<Porridge*> myList
but will not compile if it does not:
List<Porridge> myList

An error message is generated, pointing to the line with the delete element statement:
"error C2541: 'delete' : cannot delete objects that are not pointers"

I am trying to find a solution, hence my discussion on this forum.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37721030
>> I am trying to find a solution, hence my discussion on this forum.

And I offered you a solution in the form of a specialization of the Clear function for pointers. For an example, see my earlier post http:#37719093.

It does exactly what you need. It allows for both List<Porridge> and List<Porridge*>, and both will be handled appropriately - ie. nothing special will be done for objects, but pointers will be deleted.

Have a closer look at the example code, and play around with it to see what it does.
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37721716
I did look at your suggestion.
It does not compile. I get the error

error C3860: template argument list following class template name must list parameters in the order used in template parameter list

at the end of the function declaration:

template<class TYPE>
void List<TYPE*>::Clear(void)
{
}
0
 
LVL 86

Expert Comment

by:jkr
ID: 37721737
>>though I did ask for helpful responses, not philosophical diatribes.

That's exactly my point. If someone provides me a container that automatically deletes dynamically allocated content, I'd rather not use it. Since you stated you are creating a wrapper for a std::list, you are in this case adding unexpected behaviour.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37722164
>> error C3860: template argument list following class template name must list parameters in the order used in template parameter list

You might have missed something vital from my example ... Can you show the exact code that caused that error message ?

Or alternatively, try this compilable example without changing anything (I just added a main and some output) :

#include <list>
#include <iostream>

template <typename T>
class ListBase {
  public :
    ListBase(void) { }
    virtual ~ListBase(void) { }

    // ...

    void clear(void);

  private :
    std::list<T> m_list;
};

template <typename T>
class List : public ListBase<T> {
};

template <typename T>
class List<T*> : public ListBase<T*> {
  public :
    void clear(void);
};

template <typename T>
void ListBase<T>::clear(void) {
  std::cout << "clear function for objects" << std::endl;
}

template<typename T>
void List<T*>::clear(void) {
  std::cout << "clear function for pointers" << std::endl;
}

int main(void) {
  List<int>  objList;
  List<int*> ptrList;
  objList.clear();
  ptrList.clear();
  return 0;
}

Open in new window

0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37723315
I get what you were driving at.
I renamed my List class as ListBase
 and then added an entry for
 
 template<class TYPE>
 class SList<TYPE*> : public SListBase<TYPE*>
 {
 public:
    inline void Clear()
    {
        if ( !m_list.empty() )
        {
            TYPE* item = m_list.front();
            while ( m_list.size() > 0 )
            {
                TYPE* item = m_list.front();
                delete item;
                m_list.pop_front();
            }
        }        
    }
 };
 
 and it worked fine.
 However, this solution broke something else.
 
 in my ListBase class I had defined two methods:
 template<class TYPE>
 class SListBase
 {
 public:
     typedef bool (*CompareFunction)( TYPE& lhs, TYPE& rhs );

...
    inline void Sort(void) { m_list.sort(); };
    inline void Sort( CompareFunction compFunc ) { m_list.sort( compFunc ); };
};

and I now get compiler errors:
Error      1      error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'DummyClass'

If I comment out the code m_list.sort();
it compiles, but that is not a lot of use
0
Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

 
LVL 53

Expert Comment

by:Infinity08
ID: 37723764
>> Error      1      error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'DummyClass'

Strange error. It seems to imply that you're trying to compare lists rather than the items in the list.

Could you post a complete compilable sample that has the same error ?
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37724614
I have zipped up the Visual Studio 2008 project.
1. some of the files have an extension of "._txt" added to the end of their file extentions so that the File Attacher would work. Just remove the extension and it should all compile.
The line commented out in the MainApplication.cpp file
        //myList.Sort();   <<<<---- uncomment this line to see the problem
if uncommented, will illustrate the problem
ListPtrTesterForEE.zip
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37724873
I don't see how that code implements the solution I proposed.

I also don't find a sort anywhere in that code.

That said, the only error I'm finding in the code, is that you're trying to instantiate a FindFunctor with a shared_ptr as third template parameter, whereas mem_fun_ref will expect that to be the object itself.

Something like boost::mem_fn (http://www.boost.org/doc/libs/release/libs/bind/mem_fn.html) supports smart pointers.
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37727142
I am not surprised you don't recognise anything, as I sent the wrong project.
Note to self: Do nothing after midnight.

Here is the real project.

And to anyone who is kind enough to respond to this post: Nothing personal but I am NOT INTERRESTED in any solution that has the word "Boost" in it.

cheers

Maybe you could have a look at this one.
LinkTesterClearForEE.zip
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37727440
>> Here is the real project.

It seems you haven't provided an operator< for DummyClass.
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37728129
oops!
Forgot in all, the fuss about Clear().

One last question.
In the code I sent you I have defined an entry for Sort() in both the List<TYPE> and List<TYPE*> definitions. It now works thanks to your reminder about "<".
However, If I move the Sort() back to the ListBase() class I get the following error:

Error      1      error C2660: 'List<TYPE>::Sort' : function does not take 0 arguments

By my reasoning, the code should be able to see the definition in the base class because it is both a public method and is in a class that is publicly inhertied by both the List<TYPE> and List<TYPE*> classes.

Where is my reasoning flawed?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37728336
It should, yes. The original example code I posted did exactly that, but for the Clear function.

However, the error is because you've only moved the Sort without arguments back to the base class, and left the other overload in List<TYPE>.

The overload you left behind is hiding the Sort without arguments from the base class, so you cannot call it from a List<TYPE> object.

You can explicitly make the Sort without arguments visible again using :

using ListBase<TYPE>::Sort;

Open in new window


in the definition for the List<TYPE> class.
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37728717
Excellent!
It works, just like a bought one!
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37729075
Glad to hear that :)
0
 
LVL 9

Author Closing Comment

by:Orcbighter
ID: 37729338
This has been a learning exercise for me, both to expand my understanding of templates and of the behaviour of destructors.
The solutions here have proven valuable and workable.
However, I have found, despite the design to make the Clear() function work (which it now does), that if I just let the list of pointers fall out of scope, the destructors are not called. Even the std::list::erase( iterator ) method does not seem to call the destructor of the object, whether pointer or no.

I will abandon my design of the List class to incorporate pointers.
I will modify my List class to not accept pointer types, using RTTI to perform a check inside the List constructor and throw an exception if they try it.
I will recommend, in the notes in the header file, to use my List_Ptr class (using shared pointers) if they need to use pointers.
 I thank all for their contributions.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37729880
Sounds like a sane conclusion.

Except that I'd even simplify it further by keeping only one List class that can :

(a) store objects - which will be handled just fine, since their destructor will be called when they are removed from the list.

(b) store raw pointers - which will be stored of course, but NOT deleted when they are removed from the list. ie. the list has no ownership of the pointers, and the user of the list needs to be aware of that.

(c) store smart pointers - which will be handled just fine, since the smart pointers' destructor will be called when they are removed from the list.

Note that for none of these cases, anything special needs to be done. This is because the base std::list already does all that's necessary to handle these 3 cases as described.

What you might do though, is to document the fact that the list does not take ownership of raw pointers (which should be the expected behavior anyway).
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37730043
Given that my shared pointer list is declared thus:

   template<class TYPE>
    class SList
    {
    public:
        typedef tr1::shared_ptr<TYPE> ItemPtr;
        typedef typename std::list<ItemPtr>::iterator ListIndex;
 
     public:
        SList_Ptr(void);
        SList_Ptr( const SList_Ptr& rhs );
        virtual ~SList_Ptr(void);

        inline void AddFirst( const ItemPtr& item );

        inline bool GetFirst( ItemPtr& item, ListIndex& pos );
        inline bool GetNext( ItemPtr& item, ListIndex& pos );

        ...
       
    private:  // member variables
        list<ItemPtr> m_list;
    };

    and my list or objects and pointers are declared as
             
template<class TYPE>
class ListBase
{
public:
    typedef typename std::list<TYPE>::iterator ListIndex;

 public:
    ListBase(void);
    ListBase( const ListBase& rhs );
    virtual ~ListBase(void);

    inline void AddLast( const TYPE& item );

    inline bool GetFirst( TYPE& item, ListIndex& pos );
    inline bool GetNext( TYPE& item, ListIndex& pos );

    inline void Reverse(void);

    inline void Sort(void);

    virtual void Clear(void) = 0;

private:  // methods
    void Copy( const ListBase& rhs );

protected:  // member variables
    list<TYPE> m_list;
};



// List of objects
template<class TYPE>
class List : public ListBase<TYPE>
{
public:
    using ListBase<TYPE>::Sort;

public:
    typedef bool (*CompareFunction)( TYPE& lhs, TYPE& rhs );
    inline void Sort( CompareFunction compFunc );
    inline void Clear();
};



// list of pointers to objects
template<class TYPE>
class List<TYPE*> : public ListBase<TYPE*>
{
public:
    typedef bool (*ComparePtrFunction)( TYPE* lhs, TYPE* rhs );
    inline void Sort( ComparePtrFunction compFunc );
    inline void Clear();
};

I can not quite see how to make a single declaration covering all your options.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37730094
>> I can not quite see how to make a single declaration covering all your options.

Like so :

template<typename T>
class List {
  public:
    // whatever functionality you need here ...

    void clear() { m_list.clear(); }

  private :
    std::list<T> m_list;
};

Open in new window


and then use it as you want :

List<int> intList;
// fill it ...
intList.clear();   // will work as expected

List<int*> rawPtrList;
// fill it ...
rawPtrList.clear();    // will remove the pointers from the list, but not delete them

List<shared_ptr<int> > smartPtrList;
// fill it ...
smartPtrList.clear();    // will work as expected

Open in new window


As I said, nothing special needs to be done. Just let the user decide which of these three options they need, and let them worry about the consequences of their choice.

It's a lot more flexible that way, and corresponds to people's expectance of how a container behaves.
0
 
LVL 9

Author Comment

by:Orcbighter
ID: 37734082
You are going to hate this, but I found a solution to cleaning up a list of pointers when it just falls out of scope:

I added a virtual destructor to the List<TYPE> and List<TYPE*> classes, and just called Clear() inside the destructor.

The madness continues  :-)
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 37734231
Enjoy the madness :)
0

Featured Post

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now