How to maintain 2 lists of object

Question

Hi,

My c++ program needs to maintain 2 list of objects.

list<A*> inuse;
list<A*> free;

So objects A can even in 'inuse' list or in 'free' list, but not both.
http://www.cplusplus.com/reference/stl/list/

I am think of using 'list' as the data structure for my lists. My questions are

1. why i can't randomly access an elmenet in the list, I look at the above api, I don't see a way to get inuse[2];
2. How can I remove an element in the list? There is an erase(), but how can I use it to remove element #2? And after I remove element 2? will STL list fill the erased spot automatically? e.g. #3 will become #2, #4 will become #3 and so on?

Thank you.

Answer 1

Use std::vector. It has random element access ([] or at()).

//does NOT check for out of range
myvector[i];

//does check for out of range
myvactor.at(i);

You can remove an element from vector using erase(), and it will handle holes automatically (#3 becomes #2, and so on)

//erase the 6th element
myvector.erase (myvector.begin()+5);

// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);

But if you need to delete many objects 1 by 1, and there cannot be 2 objects that are the same in the list, you can try to use std::map. Use some unique property of object as a key, and object itselt as value (or object itself a key, and true as value). It also has similar random access operator [] and erase() function.

Answer 2

Constant-time removal and constant-time random access are unfortunately mutually exclusive.

Either use a std::list with linear-time std::advance for random access, or a std::deque (my recommendation) or std::vector and accept linear-time removal.

If you are always removing the second item in the series, deque has a fighting chance of maintaining constant removal time. A deque is like a vector but broken into small chunks linked to a table-of-contents.

Or, if your data is sorted, use a std::set for constant-time removal and log(N) time access.

Removing an item from the middle of any container is accomplished by my_container.erase( my_iterator ). List, vector, deque, map, whatever.

Answer 3

A std::list is modeled after a datastructure called doubly linked list.

1. You can't use random access as object are located on the heap and pointers to their location are stored in the previous and next element. In a std::vector the memory is contiguous and you can access the n-th element by the offset*size of object.

2. You remove an element by obtaining an iterator to that object and calling std::list::erase with that iterator (or a range). erase returns an iterator to the element that was pointed to by the next pointer of the element you just erased.

3. Yes, the spot will be filled automatically.

All said, use std::vector when in doubt.

Answer 4

If you need both fast access and fast removal, consider std::set, which should have both logn lookups and logn insert/delete, while still being sorted

Answer 5

A std::list is a doubly linked list. What that means is that you have a series of nodes containing the elements, like so

a <-> b <-> c <-> d.

When you remove 'b', what happens is that the pointers get adjusted so that node a points to node c, and b gets deleted, i.e.

a<->c<->d.

The reason there is no [] operator is that if you want to find the 5th element, you need to follow the links to the fifth element. The data structure simply doesn't support a fast access to a specific location. In an array or vector, all of the elements are right next to each other so this is trivial. You just add 5*sizeof(data) to the pointer to the top.

A deque also allows fast access, but fast insertions and deletions can only be done from the front or back.

I would suspect that what you actually want is std::set or std::map so that you can find the element and move it to the other set quickly.

Answer 6

list<> is a rather poor name; it's actually a linked-list. You want vector<> (the closet thing to .Net's List<> and Java's ArrayList.)

Answer 7

I'm speculating a lot here... But...

I assume that you need to be able to do different things with these two lists. It sounds like you're writing some kind of pooling allocator.

The "free list", I would expect, just needs to allow you to push and pop from its front; it's a fifo stack which you can use to store objects that are not currently in use but that can be used when an allocation is required and the "free list" is not currently empty.

The "active list" is a list of all currently allocated objects. The allocator may need to be able to report on these, or do things to them, or whatever. The "active list" requires that you can remove an object from anywhere when the object becomes deallocated. I'm guessing that it then gets pushed onto the free list for reuse.

Now the data structures that can be used for each "list" may be different. It all depends on the exact requirements. I'd say you should be able to use a std::list<A *> for your "free list" if I'm correct in the required usage semantics. If you do not care about being able to walk the "active list" in the order of allocation then you can use a std::set<A *> for your "active list". To avoid needing to do a lookup in the set to remove the object from the "active list" you could store an iterator to the object's location in the set in the object (this iterator will not become invalidated unless the object itself is removed from the set - or so sayeth this answer and I haven't checked it but I'm sure someone will correct me if I'm wrong). If you DO need to be able to walk the "active list" in order of allocation then you could use a std::map<size_t, A *> and store an incrementing allocation index as the map key; again the 'object holds the iterator for fast erase' trick should work.

Answer 8

I would implement the "inuse" and "free" lists as doubly-linked lists, and then create arrays "inuse_pointers" and "free_pointers" to hold pointers to the elements of the lists. That way, you can index into the linked list using the pointer array (and avoid having to walk the list) and will maintain the fast insert/delete operations of a doubly-linked list. It's not a typical STL approach (this was taken from some C-language cache management code I am working on at the moment) but I know it works and is rather efficient.