Is STL really list really better than good old linked lists? 
Author Message
 Is STL really list really better than good old linked lists?

I have the following need that can be met quite easily with linked lists but
not the new STL lists. Maybe someone would be kind enough as to point me to
the solution.

I am creating objects which must be stored in a container for subsequent
list type operations. However I also
want to be able to delete the objects from the list at random. Using linked
lists each object used to have a head
and tail and so it was straight forward to delete from the list and repair
the hole. However when in an STL list the objects do not contain any
information as to where in the list they are and so it is not possible to do
the
same sort of repair work.  I first tried to include an iterator to the list
in each object and set its value to the end of the list after added the
object to the list however this does not work as it appears one cannot copy
iterators.

Thanks
Paul Gibbons



Sat, 21 Jul 2001 03:00:00 GMT  
 Is STL really list really better than good old linked lists?

Quote:

>I have the following need that can be met quite easily with linked lists but
>not the new STL lists. Maybe someone would be kind enough as to point me to
>the solution.

>I am creating objects which must be stored in a container for subsequent
>list type operations. However I also
>want to be able to delete the objects from the list at random. Using linked
>lists each object used to have a head
>and tail and so it was straight forward to delete from the list and repair
>the hole. However when in an STL list the objects do not contain any
>information as to where in the list they are and so it is not possible to do
>the
>same sort of repair work.

std::list is a self-sufficient class and no "repair work" in the form of
managing links is necessary (or even possible) on your part.

Quote:
>I first tried to include an iterator to the list
>in each object and set its value to the end of the list after added the
>object to the list however this does not work as it appears one cannot copy
>iterators.

One can copy iterators.

--
Doug Harrison



Sat, 21 Jul 2001 03:00:00 GMT  
 Is STL really list really better than good old linked lists?
I do not seem to have expressed my problem well enough.

A function creates an object and puts the pointer to the object in a list
and returns the pointer. (The reason for putting the pointer in a list to to
allow one to iterate through all created objects). The returned pointer is
then used by other functions to directly access the object and at some point
in time to delete the object. When the object is deleted I need to ensure
that the pointer is removed from the list . It is this last step of removing
the item from the list when one only knows the pointer that is the problem.

Thanks for your consideration
Paul

Quote:


>std::list is a self-sufficient class and no "repair work" in the form of
>managing links is necessary (or even possible) on your part.

>>I first tried to include an iterator to the list
>>in each object and set its value to the end of the list after added the
>>object to the list however this does not work as it appears one cannot
copy
>>iterators.

>One can copy iterators.

>--
>Doug Harrison




Sun, 22 Jul 2001 03:00:00 GMT  
 Is STL really list really better than good old linked lists?
You could create a simple reference object that would encapsulate the ptr and
return that instead:
class CPtrRef
{
    MYLIST * m_pList;
    MYOBJECT * m_pObj;
    static int s_refCount; // init to 0
public:
    CPtrRef::CPtrRef( MYLIST * pList) : m_pList( pList )
   {  m_pObj = new CObj;
        pList->insert( MULIST::valuse_type( m_pObj );
        s_refCount++;
    }
    // override copy constructor and operator = to inrement m_refCount
    // override -> to return m_pObj
    CPtrRef::~CPtrRef( )
    { s_refCount--;
       if ( s_refCount == 0 ) {
            delete m_pObj;
            // remove it from list now
        }
    }

Quote:
}

I think you get the idea - the object self-inserts in the list on initial
creation, then self-deletes when there are 0 references.
Taking it one step further and for better design, you can make the ptr list a
static member of CPtrRef. The list can be STL or anything else, your problem has
nothing to do with list implementation.
hope this helps.

Best Regards,
Alen

Quote:

> I do not seem to have expressed my problem well enough.

> A function creates an object and puts the pointer to the object in a list
> and returns the pointer. (The reason for putting the pointer in a list to to
> allow one to iterate through all created objects). The returned pointer is
> then used by other functions to directly access the object and at some point
> in time to delete the object. When the object is deleted I need to ensure
> that the pointer is removed from the list . It is this last step of removing
> the item from the list when one only knows the pointer that is the problem.

> Thanks for your consideration
> Paul



> >std::list is a self-sufficient class and no "repair work" in the form of
> >managing links is necessary (or even possible) on your part.

> >>I first tried to include an iterator to the list
> >>in each object and set its value to the end of the list after added the
> >>object to the list however this does not work as it appears one cannot
> copy
> >>iterators.

> >One can copy iterators.

> >--
> >Doug Harrison




Sun, 22 Jul 2001 03:00:00 GMT  
 Is STL really list really better than good old linked lists?

Quote:

>I do not seem to have expressed my problem well enough.

>A function creates an object and puts the pointer to the object in a list
>and returns the pointer. (The reason for putting the pointer in a list to to
>allow one to iterate through all created objects). The returned pointer is
>then used by other functions to directly access the object and at some point
>in time to delete the object. When the object is deleted I need to ensure
>that the pointer is removed from the list . It is this last step of removing
>the item from the list when one only knows the pointer that is the problem.

You need an iterator to directly remove an arbitrary element from a standard
container. If all you have is a pointer, you'll have to search the list for
the pointer to get an iterator, which is obviously inefficient for long
lists. Look at std::find for a linear search.

As Alen suggested in another message, you could write a class that
implicitly inserts and erases the item, though I think there's a problem
with his static reference count.

--
Doug Harrison



Sun, 22 Jul 2001 03:00:00 GMT  
 Is STL really list really better than good old linked lists?
Doug,
You are right about problems, you'd actually need to have a static reference map
(this to ref count) in order to be able to count references for more than one
object concurrently. (gotta start rereading my code :-) ) Also multithreading
requires synchronising access to ref counting. Anything else? Still a cool
technique IMO as it has a low pain-in-the-ass factor, though maybe a bit
inefficient.

Best Regards,
Alen

Quote:


> >I do not seem to have expressed my problem well enough.

> >A function creates an object and puts the pointer to the object in a list
> >and returns the pointer. (The reason for putting the pointer in a list to to
> >allow one to iterate through all created objects). The returned pointer is
> >then used by other functions to directly access the object and at some point
> >in time to delete the object. When the object is deleted I need to ensure
> >that the pointer is removed from the list . It is this last step of removing
> >the item from the list when one only knows the pointer that is the problem.

> You need an iterator to directly remove an arbitrary element from a standard
> container. If all you have is a pointer, you'll have to search the list for
> the pointer to get an iterator, which is obviously inefficient for long
> lists. Look at std::find for a linear search.

> As Alen suggested in another message, you could write a class that
> implicitly inserts and erases the item, though I think there's a problem
> with his static reference count.

> --
> Doug Harrison




Mon, 23 Jul 2001 03:00:00 GMT  
 Is STL really list really better than good old linked lists?
Can't you just use find and erase?


Quote:
>I do not seem to have expressed my problem well enough.

>A function creates an object and puts the pointer to the object in a list
>and returns the pointer. (The reason for putting the pointer in a list to
to
>allow one to iterate through all created objects). The returned pointer is
>then used by other functions to directly access the object and at some
point
>in time to delete the object. When the object is deleted I need to ensure
>that the pointer is removed from the list . It is this last step of
removing
>the item from the list when one only knows the pointer that is the problem.



Mon, 23 Jul 2001 03:00:00 GMT  
 Is STL really list really better than good old linked lists?
If it was easy to remove the old objects by deleting them because they had
head/tail pointers (as your first message indicated) then those objects
where
actually nodes in  your linked list.

Given that then the function you describe in this last message would be
creating a new node, inserting it in the list, then returning a pointer to
it.

In STL the pointer to a node in the list is an iterator.  You don't directly
delete
nodes but instead you erase them by passing a iterator pointing to them to
the containers erase method.

There's several design issues with to deal with but here's a simplistic
solution - if I've read your requirements right that is.  Note that there's
no
real reason for the factory class except it wraps all the appropriate
functions
together along with the list. And I'm obviously not dealing with
threading...

#include <list>
#include <iostream>

using std::cout;
using std::endl;

typedef     std::list<int>     tIntList;
typedef     tIntList::iterator     tIntPtr;

class IntFactory
{
public:
    static tIntPtr Create(const int num)
     {
        s_ints.insert(s_ints.end(),num);
        return --s_ints.end();
    }

    static void Destroy(tIntPtr& pInt)
    {
        s_ints.erase(pInt);
    }

    tIntList&    Instances()
    {
        return s_ints;
    }

private:
    static     tIntList    s_ints;

Quote:
};

tIntList    IntFactory::s_ints;

void DisplayInstances()
{
    tIntList& ints = IntFactory::Instances();

    for(tIntPtr i = ints.begin();i != ints.end();++i)
        {
            cout << *i << endl;
        }

Quote:
}

int main()
{
    tIntPtr    pInt = 0;

    IntFactory::Create(10);
    pInt = IntFactory::Create(20);
    IntFactory::Create(30);

    DisplayInstances();

    cout << "changing an instance value.." << endl;

    *pInt = 50;

    DisplayInstances();

    cout << "deleting an instance." << endl;

    IntFactory::Destroy(pInt);

    DisplayInstances();

Quote:
}

this console app would display

10
20
30
changing an instance value..
10
50
30
deleting an instance.
10
30


Quote:
>I do not seem to have expressed my problem well enough.

>A function creates an object and puts the pointer to the object in a list
>and returns the pointer. (The reason for putting the pointer in a list to
to
>allow one to iterate through all created objects). The returned pointer is
>then used by other functions to directly access the object and at some
point
>in time to delete the object. When the object is deleted I need to ensure
>that the pointer is removed from the list . It is this last step of
removing
>the item from the list when one only knows the pointer that is the problem.

>Thanks for your consideration
>Paul



>>std::list is a self-sufficient class and no "repair work" in the form of
>>managing links is necessary (or even possible) on your part.

>>>I first tried to include an iterator to the list
>>>in each object and set its value to the end of the list after added the
>>>object to the list however this does not work as it appears one cannot
>copy
>>>iterators.

>>One can copy iterators.

>>--
>>Doug Harrison




Sun, 29 Jul 2001 03:00:00 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Really dumb Linked List Q

2. really having trouble with linked lists

3. plz help - a program that should be really easy (linked list)

4. Best language, Best algo and Sorting huge lists

5. Is C# really better then vb?

6. Is Java really better than C# ?

7. Best way to write really large files...

8. Really good C# and .NET books ?

9. is c# really better than c++ and java?

10. Removing a NODE for good (double linked lists)

11. link list of a linked list (chained links?)

12. really really dumb question

 

 
Powered by phpBB® Forum Software