- Forum
- General C++ Programming
- What data structure does a vector use?
What data structure does a vector use?
Does it use Linked List or Dynamic Array?
I want to know this because if I happen to want to use a lot of insertions and deletions then it is more efficient to make use of Linked List instead of Dynamic Array.
While, if I happen to want to just access random parts of the Array, then Dynamic would be more efficient.
-------
I want to make a 2D game using SDL engine and I need to check whether or not an object is colliding with a list of other objects. (because there would be more then one objects on the map.)
Since I would simply be accessing each object sequentially to check whether or not the object is colliding with another the object in question, and since any of those objects could "die" and be deleted at any time, it makes more sense to use Linked List then a Dynamic Array.
I want to know this because if I happen to want to use a lot of insertions and deletions then it is more efficient to make use of Linked List instead of Dynamic Array.
While, if I happen to want to just access random parts of the Array, then Dynamic would be more efficient.
-------
I want to make a 2D game using SDL engine and I need to check whether or not an object is colliding with a list of other objects. (because there would be more then one objects on the map.)
Since I would simply be accessing each object sequentially to check whether or not the object is colliding with another the object in question, and since any of those objects could "die" and be deleted at any time, it makes more sense to use Linked List then a Dynamic Array.
Last edited on
Vector is not a linked list and a vector is fine to use for games. A linked list sounds like a bad idea for a game? :s
threeright:
You're right to use a linked list. I have not studied the internals of vector, but I do know that std::list was made for this:
http://www.cplusplus.com/reference/list/list/?kw=list
very handy, good luck!
You're right to use a linked list. I have not studied the internals of vector, but I do know that std::list was made for this:
http://www.cplusplus.com/reference/list/list/?kw=list
very handy, good luck!
I don't see how a linked list is going to faster in a game? You're going to be jumping around memory to do these insertions and deletes, and that's not going to be efficient. In a vector, all the memory should be together and faster to access and iterate over. Since you're going to be iterating over the entire block or large segments of it at a time in a game, the vector should be faster.
Mats, it's more efficient to use a linked list, because if you use an array, you have to copy all of the values. "Jumping" around memory is not like "jumping" around a hard disk drive. It's as efficient as the speed of electricity itself, and it doesn't matter.
Linked lists would be superb for insertions and deletions. Look it up.
As for iterating over larg blocks of data, I highly suggest using a map. If you need to find somthing, it will be FAR more efficient than a vector. A map uses a hashing scheme to hash the values it stores. Try finding a string in a vector of 1,000 strings, and a map of 1,000 strings. The map will be instantanious, and the vector will not.
Linked lists would be superb for insertions and deletions. Look it up.
As for iterating over larg blocks of data, I highly suggest using a map. If you need to find somthing, it will be FAR more efficient than a vector. A map uses a hashing scheme to hash the values it stores. Try finding a string in a vector of 1,000 strings, and a map of 1,000 strings. The map will be instantanious, and the vector will not.
Last edited on
@ IWishIKnew: just an observation, in theory it's true that vectors are slower than lists at inserting/removing elements, however in practice modern computers with big CPU caches will speed things up quite a bit. I think...
http://www.codeproject.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us
http://www.codeproject.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us
I would be incredibly surprised if you see any sort of difference between std::list and std::vector here...
You would have to be doing a very large amount of insertions and deletions to see a difference. And even if you're at a point where you see differences, a standard linked-list is still probably not what you want... They're not very efficient. But they are used in building some incredibly efficient data structures.
Constant lookup time != Instant lookup time.
It could constantly take 15 seconds to look anything up, and the map would still be O(1).
You would have to be doing a very large amount of insertions and deletions to see a difference. And even if you're at a point where you see differences, a standard linked-list is still probably not what you want... They're not very efficient. But they are used in building some incredibly efficient data structures.
| The map will be instantanious, and the vector will not. |
Constant lookup time != Instant lookup time.
It could constantly take 15 seconds to look anything up, and the map would still be O(1).
@resident:
When that happens, and it taks that long to find somthing in a map, I would recommend a hash... or getting innovative...
When that happens, and it taks that long to find somthing in a map, I would recommend a hash... or getting innovative...
Last edited on
@ResidentBiscuit
How has a map a constant lookup time? Mathematical analysation would come to that the maximum amount of compares and ptr dereferences in a binary tree is ln((elements + 1)/2) / ln(2); which implies O(ln_2(elements)).
@Catfish666
I have read the same about the linked list vs vector; I can only imagine that std::list may be better to use if you have huge classes, as the standard would permit them to be scattered around in memory; vector is - according to the standard - linearly placed in memory. Thus you can prevent std::bad_alloc.
How has a map a constant lookup time? Mathematical analysation would come to that the maximum amount of compares and ptr dereferences in a binary tree is ln((elements + 1)/2) / ln(2); which implies O(ln_2(elements)).
@Catfish666
I have read the same about the linked list vs vector; I can only imagine that std::list may be better to use if you have huge classes, as the standard would permit them to be scattered around in memory; vector is - according to the standard - linearly placed in memory. Thus you can prevent std::bad_alloc.
Topic archived. No new replies allowed.