vector vs. linked list

As usual, it depends :)

A std::list is very useful if you keep removing and insert elements in the front or middle. It just adjusts the node pointers around the new/deleted element, but does not need to touch any inserted objects.

A std::vector has to resize and will regularely need to reallocate ALL objects inside. Depending on your stored object type this can use up quite a lot of resources.

If you build a vector once and then just keep reading from it it's the better container.

Quote:

Original post by Endurion As usual, it depends :) A std::list is very useful if you keep removing and insert elements in the front or middle. It just adjusts the node pointers around the new/deleted element, but does not need to touch any inserted objects. A std::vector has to resize and will regularely need to reallocate ALL objects inside. Depending on your stored object type this can use up quite a lot of resources. If you build a vector once and then just keep reading from it it's the better container.

Sums it up nicely. With a vector (or array) it's very fast to get the information you want since the address can be computed. With lists that's not the case since you have to step from each node to the next. It's a real pain to insert elements in the middle of an array or vector though, and time consuming, where with a list it only takes updating a couple of pointers.

It's just going to depend on what you're looking to do. In a great many cases, a vector is the better choice for speed. It can't do everything though. Consider something like a tree, where each node needs a parent and possibly an arbitrary number of children.

You could store the children in a lot of different ways, but a list is a good way to go if you don't know how many children a node might have or if they might get removed at some point. If that's the case, removing a node is going to be quick with a list since it just involves updating a few pointers, but if you tried to use a vector and had to delete a node you might be deleting one in the middle of the vector. That's going to require a lot of time to rearrange the elements, time not incurred with a list.

So, just anywhere where you might have an arbitrary number of elements in a list where you might need to insert or remove them from the middle of the list. That's where a list shines.

So for a texture factory that i'm making for my rendering engine, a list would probably be better. Since I'm always inserting and removing textures. I didn't really think about it like that. That the vector has to reorganize all the time.

First off, let me congratulate you on adopting the best practice advice that is commonly given out (and unfortunately often ignored) - that our under-used friend, the vector is usually the best choice of container.

Now, one usefulness of lists is certainly their ability to insert/remove from the middle in O(1). Of course there's only a speed advantage there when there are a decent number of items, e.g. Easily 50 or more.
Another useful thing that has so far not been mentioned is that the operations on a list cause a minimal amount of iterator invalidation. This means that you can store elsewhere iterators or pointers to items in a list, in cases where you could not safely do so for a vector.
Finally, concatenating two lists together is O(1) - definitely not so for a vector.

Quote:

Original post by Gauge So for a texture factory that i'm making for my rendering engine, a list would probably be better. Since I'm always inserting and removing textures. I didn't really think about it like that. That the vector has to reorganize all the time.

Maybe, maybe not...
Does the order of items in the container matter?
Are there a fair number of objects in the container?
Do you need random access to the items?

Quote:

So for a texture factory that i'm making for my rendering engine, a list would probably be better. Since I'm always inserting and removing textures. I didn't really think about it like that. That the vector has to reorganize all the time.

First make it work, then move on. Worry about the efficiency of the underlying structure if/when the texture factory becomes too slow.

Quote:

Original post by Nitage Quote: So for a texture factory that i'm making for my rendering engine, a list would probably be better. Since I'm always inserting and removing textures. I didn't really think about it like that. That the vector has to reorganize all the time. First make it work, then move on. Worry about the efficiency of the underlying structure if/when the texture factory becomes too slow.

Nitage (and many others here) has a very valid and important point, but don't forget you always want to evaluate if you are using the right containers in the first place for the job.

In my opinion, a texture factory would be more appropriately implemented using some type of map(hash_map/unordered in this case) rather than a vector or a linked list. More than likely, the key would be the reference name of the texture, which is usually what you would use to access the texture in the first place (how else do you know which texture you need when iterating through a vector/list?)

In this case, it is not premature optimization because choosing a container that offers no key based access when you do need key based access is a design issue that can be identified by answering the questions iMalc stated in his last post about functionality and runtime complexity requirements rather than performance.

Of course, I am deviating a little from the original question asked, but I wanted to reiterate what iMalc is getting at, and that is to figure out the design first and then a "working" implementation second [wink]

Quote:

Original post by iMalc Quote: Original post by Gauge So for a texture factory that i'm making for my rendering engine, a list would probably be better. Since I'm always inserting and removing textures. I didn't really think about it like that. That the vector has to reorganize all the time. Maybe, maybe not... Does the order of items in the container matter? Are there a fair number of objects in the container? Do you need random access to the items?

No the order doesn't matter.

Yes there will eventually be hundreds.

Random access would be nice. My plan now, using a list, is to just iterate through the list till I find the texture I need.

Also as far as a vector, I'm on the programming team at my college (presently taking a break in serving in Iraq) so using vectors is a must. The problem is I now immediately think around using that container instead of even considering another container.

Thanks again guys, gamedev never disappoints.

One important benefit of lists is that they usually support constant-time splicing. By contrast, vectors only support linear-time splicing.

Quote:

Original post by Gauge Quote: Original post by iMalc Quote: Original post by Gauge So for a texture factory that i'm making for my rendering engine, a list would probably be better. Since I'm always inserting and removing textures. I didn't really think about it like that. That the vector has to reorganize all the time. Maybe, maybe not... Does the order of items in the container matter? Are there a fair number of objects in the container? Do you need random access to the items? No the order doesn't matter. Yes there will eventually be hundreds. Random access would be nice. My plan now, using a list, is to just iterate through the list till I find the texture I need.

If there is a key type that you can use to look for your texture, I would consider a map of a hash_map.

I do have a key, the texture name. I suppose I could use a map with texture names as the key and an openGL GLuint for the texture as data. I may try implementing that next. Is that much faster than the list in terms of adding and removing data?

Thanks to all who helped I got the list and vector texture factories working.

Quote:

Original post by Gauge I do have a key, the texture name. I suppose I could use a map with texture names as the key and an openGL GLuint for the texture as data. I may try implementing that next. Is that much faster than the list in terms of adding and removing data?

No, the point is that look-ups are fast, which were slow with lists and vectors. Adding and removing data in a list isn't slow.

If you use a hash_map (they are not part of the standard yet, but most STL implementations provide them), every operation you need takes amortized constant time.

Quote:

Original post by Gauge Quote: Original post by iMalc Quote: Original post by Gauge So for a texture factory that i'm making for my rendering engine, a list would probably be better. Since I'm always inserting and removing textures. I didn't really think about it like that. That the vector has to reorganize all the time. Maybe, maybe not... Does the order of items in the container matter? Are there a fair number of objects in the container? Do you need random access to the items? No the order doesn't matter. Yes there will eventually be hundreds. Random access would be nice. My plan now, using a list, is to just iterate through the list till I find the texture I need. Also as far as a vector, I'm on the programming team at my college (presently taking a break in serving in Iraq) so using vectors is a must. The problem is I now immediately think around using that container instead of even considering another container. Thanks again guys, gamedev never disappoints.

On trick with a vector when order doesn't matter, and you want to remove fom the middle, is to swap the item to remove with the last item, and then just pop_back to remove it. That gives you constant time removal.[cool]

However, in this case it seems like a map or set might be more appropriate. This eliminates the need to perform a linear search through the container to find the item of interest. The reason I've suggested a set in this case, is that since you're currently using a vector, you must have the name inside the texture struture, and simply switching to a set would be least change from what you have now.

So a map will be slower when 'adding' things to the cache than a list. However, usually you do many more 'lookups' than 'adds', and you do 'adds' immediately after creating the item to be cached (so the extra hit of a map insert won't be noticed).

The map also gives you a really nice, pretty interface to look up elements.



Much slicker than having to walk a list looking for your element.

Agreed with what's been said so far -- a hash_map or simply a std::map are the ideal solution when you want to look some data up via a key value. My own resource-caching system uses exactly that approach, and both the key and data are template parameters so it can be used to manage any resource type with any ID type. I'm writing an article for GameDev on it right now.

The other point I'd like to touch on is that you seem to have misunderstood how and when adding things to vector is inefficient. With a std::vector, adding something to the end of the list, via the push-back() method, is essentially a constant-time operation, only when the vector needs to grow to accommodate the new item will push_back() take any significant amount of time. Remember, vector is essentially a managed array -- if you had your own array, and you had to put something at the back of it, it doesn't take you any amount of time if there's room to spare. Now, inserting into the middle of any array *always* has a significant overhead, because all the elements from [insert, end] have to be moved over to make room for the new value. So, the short version is that, when order doesn't matter, you can just put new values at the end via push_back, and vector is very efficient.

One last note, if you know how many elements are going to be in the vector or have a good average upper-bound (that isn't too large!), you can always reserve the memory beforehand so that you don't have to allocate or copy at all during push_back. For a texture manager it might not be ideal since you can have a very large upper-bound on the number of textures, but in general it's something to think about when deciding whether or not a vector is appropriate.