STL linked list:: how to access members?

Question

If I have a STL list that contains pointers to a class and want to access a class member how would I go about that? Specifically, I need to be able to delete members of the list which each have a member with a unique id.

So I have something like:

class Actor{

    private:
    int id;

    public:
    int getActorID(){ return id;};
};

std::list<Actor *> actorList;

std::list<Actor *>::iterator i;

So if each actor has a unique id, how could I remove the actor with a specific ID? I've been using a linked list that was hand coded but I want to switch it to STL. Only problem is I can't figure out how to access the method getActorID() to find the node to remove. Thanks for any help.

Are you sure a list is what you want here? It sounds more like you're searching for a map. — obataku, Oct 13 '12 at 22:06
Please reconsider using a linked list. If you will be traversing the list a lot, use a vector. If you need to have a unique id associated with an object, use a map (or unordered_map in c++11). Linked lists are terrible for most uses. http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html — Alexander Kondratskiy, Oct 13 '12 at 22:15

Adrian Herea · Answer 1 · 2012-10-15T18:11:34.727

3

std::list<Actor *>::iterator it;

std::list<Actor *>::iterator iStart = actorList.begin() ;
std::list<Actor *>::iterator iEnd = actorList.end() ;
for (it=iStart ;it!=iEnd;++it)
{
if (*it->getActorId() == searchedId)
  {
   actorList.erase(it);
   break; //you have unique id's so you could delete a maximum 1 item
  }
}

also don't forget that you have alternatives like

std::list::remove
std::list::remove_if

http://en.cppreference.com/w/cpp/container/list/remove

edited Oct 15 '12 at 18:11

answered Oct 13 '12 at 22:09

Adrian Herea

658
6
7

it worked. thanks for the help (that goes for everyone who answered!) – Skywarp Oct 13 '12 at 22:35
This worked? `delete` won't work in that expression, among other problems. – Michael Burr Oct 14 '12 at 08:09
You're right-- i just replaced the delete line with erase. However, what I meant was that it worked in the sense that I was able to access node members. The implementation, however, doesn't work. As many posters pointed out, the list is not ideal. I also tried vector but having problems too. Class Actor is a base class with a derived class on top, all allocated from the heap upon creation. And yes, I have to traverse the nodes on an extremely frequent basis, so I'm open to ideas on how to best implement it. They are game actors for a game. – Skywarp Oct 14 '12 at 20:10
@user1609525 This is a reasonably good answer to your question -- which is about deletion of list elements only. You may want to accept the answer and come up with a new question. – jogojapan Oct 15 '12 at 06:34

score 1 · Answer 2 · answered Oct 13 '12 at 22:07

An iterator acts like a pointer so in order to call a member function of an object stored as a pointer in a STL container you need to dereference twice:

std::list<Actor*>::iterator iter = actorList.begin();
(*iter)->getActorId();

Or:

(**iter).getActorId();

score 1 · Answer 3 · edited May 23 '17 at 11:43

1

Iterator for-loops over containers that may make multiple calls to erase are a disaster waiting to happen because erase usually invalidates at least the iterator passed to it (and any other iterator that pointed at the erased element) and invalidated iterators cannot be safely incremented. Loops that only make a single call to erase can use "break;" to get out of the for-loop without any use of the invalidated iterator.

Iterator invalidation rules

As I told my co-workers after a week of multiple segmentation faults caused by this problem, if you want to loop over a container and call erase, use a while loop and make sure you obtain a valid iterator to the next item (or end()) before you call erase. The easiest way to do this is to post-increment the iterator at the call site. For std::list::erase(iterator), one can also use its return value as the new iterator value.

list iterator not incrementable

edited May 23 '17 at 11:43

Community

1
1

answered Oct 15 '12 at 16:16

John G.

11
2

the current situation doesn't refer to multiple calls of erase during a for loop "members of the list which each have a member with a unique id." – Adrian Herea Oct 15 '12 at 17:25
If break isn't called after the single call to erase, then the moment the for loop head is re-entered and the iterator is incremented, the code becomes non-standard compliant and can blow up. – John G. Oct 15 '12 at 17:42
Iterators are values, not references. One legal implementation of iterators for a list is to use an address of an internal data structure as the iterator value. Well, after erase, that internal data structure is freed. Usually, the dead storage will still have valid data in it when you reference it during operator++... but not always... and if it doesn't, you get a catastrophic error. – John G. Oct 15 '12 at 17:50

score 0 · Answer 4 · answered Oct 13 '12 at 22:11

You must use iterators, since a list is a sequential data structure. Once you have an iterator, you can move forward and extract the pointer to the object using the indirection operator *

list<Actor *>::iterator it = actorList.begin();
Actor * innerPtr = *it;
innerPtr->yourMethod();

Once you know that an actor is the one to be deleted, you can use the method erase(position); USING THE ITERATOR:

if( innerPtr->getActorId() == <your condition> )
{
    actorList.erase(it);
}

However, if you need to search using actor ID, I recommend you to switch to a different data structure, such an associative container (e.g. map).

score 0 · Answer 5 · edited Oct 14 '12 at 15:15

To find the node you want to do something with you can use std::find_if():

#include <algorithm>
#include <list>
using namespace std;


class Actor{

    private:
    int id;

    public:
    int getActorID() const { return id;};
};


// a functor used for pre-C++11 since lambdas aren't supported
struct isActor
{
private:
     int target;

public:
    isActor( int target) : target(target) {}

    bool operator()( Actor const* pa) const
    {
        return pa->getActorID() == target;
    }
};


std::list<Actor *> actorList;

std::list<Actor *>::iterator i;

int main()
{
    // pre-C++11 technique
    i = std::find_if( actorList.begin(), actorList.end(), isActor(42));

    // C++11 lambda technique
    int id = 42;
    i = std::find_if( begin(actorList), end(actorList), [=](Actor const* pa) {
        return pa->getActorID() == id;
    });
}

STL linked list:: how to access members?

5 Answers5