When should vector/list be used?

jokoon
  • When should vector/list be used? jokoon

    I can understand when to use lists, but I don't understand when it is better to use vectors than using lists in video games: when it is better to have fast random access ?

    (And I understand why it's faster to insert/delete in lists because it just removes/adds pointers, but it still has to find the corresponding item...)

  • My rule of thumb, and I'm sure there will be debate on this, is to never use lists (unless you need to very, very frequently remove things from the middle of large lists).

    The speed you'll gain by having all your elements in your container in contiguous memory (and therefore more cache-friendly) is worth the offset of the additional costs of adding/removing/resizing the vector.

    Edit: Just to clarify a bit more, of course it should go without saying that any kind of "which is faster" question should be tested on whatever platform with whatever data sets are pertinent to your particular needs. If I just need a collection of elements I just use vector (or deque, which is almost the same thing) unless there's a good reason not to.

  • Usually lists are used for structures like queues where there are lots of append and remove operations. Example: An ever changing list of entities that should be updated. The list itself only contains entities on screen and therefore changes frequently.

    Vectors (or arrays) are better suited for a collection that doesn't change that much and where you need fast access to individual items within the collection. Example: A tile-map where you have to lookup tiles at a given index.

    Tetrads opinion might be true, but it depends on the programming language that is used. I see that you tagged your question c++, but I tried to give an answer that isn't language-specific.

  • Use a list when iterator invalidation caused by modifying the middle of your data structure is going to cause a problem, or you need to keep your elements sorted so the swap and pop trick for quick middle collection deletes won't work and you have a large number of mid collection deletes.

    You may also want to consider using a Deque. It has similar performance characteristics to a vector but doesn't have vector's need for contiguous memory, and is a little more flexable.

  • Your choice should reflect your needs. All the elements of the vectors are continous in memory and lists has pointers to next / previous elements so they each have their advantage / disavantages :

    Lists :

    • Each elements takes 2 integers to point previous and next elements, so most commonly, that's 8 bytes more for each elements in your list
    • Insert is linear in time : O(n)
    • Remove is a constant operation : O(1)
    • Access the x element is linear in time : O(n)

    Vectors :

    • Needs less memory (no pointers to other elements, it's a simple math algorithm)
    • Remove is linear in time : O(n)
    • Access the x element is constant : O(1) (That's because the elements are continious in memory so it's a simple math operation vectorPtr + ( x * bytesOfTheType ) )
    • Insert can be in linear time, but most commonly, it's a constant operation : O(1) (That's because the vector in an array but always reserve 2 times it's capacity when the array is full so array copy is not frequent )

    So list is better when you program needs to add and remove elements frequently, but never access (or rarely access) a particular element without the need of the others before. The vector should be used for better access time, but lacks effeciency when you need to remove or add elements.

    Check this post on stackoverflow, it present a really nice graph with basic questions on your needs that drives you to a specific container depending on your answers :

    https://stackoverflow.com/questions/366432/extending-stdlist

  • In console games we never, ever use std::list because:

    1. it does memory allocations whenever you add a new item. memory allocations are slow.
    2. it's full of pointers. pointers are bad. a pointer is a cache miss. a cache miss is bad.

    even std::vector is losing favor on consoles because:

    1. you often care only about, for example, the positions of all the objects. like for example you want to collide the objects with each other, in which case you don't care what their color is. so you want all the positions to be contiguous in memory and you want the colors to be somewhere else far away, to avoid polluting the cache. but std::vector requires you to store everything for each object in a contiguous chunk of memory (e.g. position then color.) so if you do work that reads only the positions, you need to read all the colors into the cache too, even if you don't use them. this is wasteful.

Tags
c++ algorithm data-structure
Related questions and answers
  • as the cost. I think a better solution should be to use the portal between the two sectors, compute its center, and then the cost should be : distance( sector A center, portal center ) + distance ( sector B.... Micropather exposes a pure virtual Graph class that you must inherate and overrides 3 functions. I understand how pathfinding works, so there's no problem in overriding those functions. Right now, my..., this approximation could mislead the A* algorithm. For the LeastCostEstimate method : I just take the midpoint of the two sectors. So, as you understand, I'm always working with sectors' centers, and it's working

  • First theoretical question. What is better (faster)? Develop your own gpgpu techniques for physics simulation (cloth, fluids, colisions...) or to use PhysX? (If i say develop i mean implement existing algorithms like navier-strokes...) I don't care about what will take more time to develop. What will be faster for end user? As i understand that physx are accelerated through PPU units in gpu...-theoretical question: Is physx able to do sofisticated simulation equal to lets say Autodesk's Maya fluid solver? Are there any c++ gpu accelerated physics frameworks to try? (I am interested in both physx

  • I've been using OpenGL for a short time now- and I'd like some clarification on VBOs. As I understand it, a VBO is an object stored on VRAM. In immediate mode, to apply a texture we simply bind it and specify the texture coordinates before the vertex coordinates, however it doesn't seem that way with VBOs. Question 1: Can I specify texture data in a VBO? What portion of the data? Normally when I make a game in 2d I'd store all of my objects in instances of different classes, then when my drawing routine comes up- just draw the objects that are on screen. With a 3D environment it would

  • that I have generated. I handle the threads by using turn-based concurrency. My problem is I worry about lag of the input events when there are fast moving objects, and I am curious to see if there are better ways of handling the input events then currently? My current idea, of handling the simple hit test of fast moving objects with user input, is that I try and use the timestamp generated by the event to work out where everything was at that time, but it seem like a lot of work - probably because the way I have implemented everything on the update side - so is there a better way? I did

  • ); When using this code I'm able to detect a ray intersection via a sphere, but I have questions when determining an intersection via a plane. First off should I be using my vRayOrig & vRayDir variables for the plane intersection tests or should I be using the new vectors that are created for use in object space? When looking at a site like this for example: http://www.tar.hu...I'm developing a picking system that will use rays that intersect volumes and I'm having trouble with ray intersection versus a plane. I was able to figure out spheres fairly easily, but planes

  • I am trying to build and run Doom 3 from the open source release in order to better understand how the engine works. Unfortunately I am not able to run the game from the binary I built. I just get the console, but cannot run the actual game. Here is what I did: Downloaded the source code from the game repo Downloaded and installed the DirectX SDK Purchased, downloaded and installed Doom 3 from... if the warning I am getting is the problem or if there is something else. Also, this is when the configuration being used is "Dedicated release", but I have also tried with "Dedicated Debug". It is my

  • shows clearly how this one works, but I can't figure out how to implement in my game, maybe I don't understand that good but I find some things that are not really clearly to me. In my game, the player decides when change direction in the X-Axis but I can't figure out how with this RK4 implementation change the direction of the object, in the example the point goes side to side but I don't understand how I can control when he goes right or left. So if anyone can give a little bit of clarity in this implementation and my problem which I do not understand I will be really grateful. Thanks

  • Components in GameSubsystems (when GameObject is created and composed). There are 4 approaches: 1: Chain of responsibility pattern. Every Component is offered to every GameSubsystem. GameSubsystem makes..., GameSubsystemParticleEmmiter can be merged into GameSubsystemSpatial (to place all audio, emmiter, render Components in the same hierarchy and use parent-relative transforms). con. Every-to-every check. Very innefficient. con. Subsystems know about Components. 2: Each Subsystem searches for Components of specific types. pro. Better performance than in Approach 1. con. Subsystems still know about

  • component associated with it). No problem until this point. For this function I want to use a scientifically tested, accurate N-body simulation algorithm (like this). It's my field so I already know how... the predefined number of loops has passed, or when the user gives a movement command, the algorithm is activated again, producing the new portion of the trajectory to use next. This might require... there is a totally different and better way to do this, please let me know. Additional info: the game is in C++, and the graphics engine is Ogre3D. EDIT: changed the part about the trajectories of the non