Vectors/Lists/Sets ?

vectors: Implemented as dynamic arrays. If you add in elements one at a time, the size is doubled when it runs out of space so that insertion time remains linear, not quadratic. Inserts at end take O(1) time except when you need to resize, in which case it is O(n) time. Gets and sets also take O(1) time. Insertions in the beginning or middle take O(n) time even if it doesn''t need to be resized. Deletions take O(1) time at the end, O(n) time for the beginning or middle.

lists: implemented as doubly-linked lists. Insertions and deletions take O(1) time for any point. Gets/sets for an arbitrary element take O(n) time, gets and sets for the head or tail take O(1) time. Almost always slower than vectors for most cases, except when you have a large number of insertions and deletions in the middle compared to the number of gets and sets in the middle.

sets: Implemented as red-black trees, which are a type of binary tree that use certain algorithms so that they don''t become very unbalanced. Insertions and deletions take O(log n) time. Gets and sets also take O(log n) time. Useful when you don''t care about the order of things and you will be doing many lookups to determine if certain elements are in the set or not.

Each has it''s advantages and disadvantages depending on how it''s used. For example, vectors give you fast random access and end insertions, while other operators such as insertions and removals from the middle can be slower. Lists give you fast insertions and removals from the middle, while searching can be slower. It''s all about how you use it.

A set also would logically have set semantics, yes? Meaning that it won''t hold multiple copies of equal objects - it will do nothing silently return on insert() if the thing being inserted is already there. This can be a good thing or a bad thing.

don''t forget deques, they are the most general purpose list in the bunch.

a vector is the best at iteration, and random access, the worst at insertion, and very very bad at random insertion (like inserting into a sorted list).

a list is the best at random insertion, consistent but not ideal at iteration, and doesn''t support random access in any constant time way.

a deque is in between the two, it is almost always implemented in a way in which random access is often twice as costly as the ideal vector case (but still very good), iteration is usually worse than vector and better than lists, but not by much either way, insertion at the beginning or end is very close to the speed of a list, and random insertion / removal is noticably worse than a list, but still within the same ballpark (much better than a vector).

I always use a deque first by default, and then change to lists and vectors those lists which have known access patterns suited to each (anything computed at init time, and then read a lot should be a vector - anything of static size, but the values are changed and rearranged should be a vector - anything which is always accessed by iteration can be a list - and anything which is always accessed by iteration and interted and deleted from often should be a list).

Thanks a lot, that's really useful.

And I have another question, what is exactly the point of iterators?

When I want to loop throught a vector, I usually do this:

for(int i=0; i<MyVector.size(); i++)
{
  if(MyVector[i].GetBla() == 666)
  {
    MyVector[i].DoBla();
  }
}

But I've seen usage of iterators:

vector<SomeClass>::iterator iter;
for( iter = MyVector.begin(); iter != MyVector.end(); iter++)
{
  if((*iter)->GetBla() == 666)
  {
    (*iter)->DoBla();
  }
}

(I'm not totally sure of the syntax as I never really used iterators..)

Is there wrong in just looping with an int? Should I use iterators? What would be the advantages?

Thanks

[edited by - Hedos on April 25, 2004 7:59:45 PM]

Iterators separate the traversal algorithms from the generic container they are used on. Basically, you can use the same exact loop to traverse a list, or a vector, or whatever container you can think of. If not for iterators, you would have to write separate code to go through a vector (it would look like your first code), and something different for a list (you would have to look at the next node pointer, etc). Iterators let you abstract all of that away so you don''t worry about the details and your code is more uniform, less error prone, and more maintainable.

iterators can also be more efficient for many cases:

for example, this code:

if you have int indexs, then

int i=0; // initializes the index to 0
i < MyVect.size(); // calls size function and compares
++i; // adds 1 to i
MyVect // multiplies i by size of element, then adds to MyVect base address and dereferences.

if you have this:

iterator it = MyVect.begin(); // calls func an initializes
it != MyVect.end(); // calls func and compares
++it; // adds size of element to it
*it; // dereferences it

you see that on platforms OTHER than modern x86 (which has an indexing function built in), the simply dereference could be much faster than the subscripting / multiplying version. Especially if you have something like this:

temp = myvect[i];
myvect[i] = othervect[x];
othervect[x] = temp;

temp = *currMyVect;
*currMyVect = *currOtherVect;
*currentOtherVect = temp;

could be much quick without an optimizer, or when the operation uses too many registers for the platform.

on x86 these issues rarely matter for vectors or arrays ... but for the other items: sets, maps, deques, ... they make a HUGE difference .. cause the [] operator on these items is much more costly than on a vector, but the *it operation nearly ideal for all containers.

wow, thanks a lot


Here is a last question: I also heard stl vectors/lists,etc.. aren''t that fast and they''re not always good to use in games.. And I think I saw some people saying that they wrote their own vector/lists..etc.. class, wich was faster than the stl ones.
Do you think this could really make a difference in a game, writing his own class?

quote:

---

Here is a last question: I also heard stl vectors/lists,etc.. aren''t that fast and they''re not always good to use in games.. And I think I saw some people saying that they wrote their own vector/lists..etc.. class, wich was faster than the stl ones.
Do you think this could really make a difference in a game, writing his own class?

---

The non-STL classes are faster until it comes to functions
such as push_heap(..) and other sorting algorithms.

however the STL documentation is not user friendly - variable
names are like "__L__r" or "__R" etc

Depending on the implementation, the STL containers can usually be just as fast, if not faster, than anything you write yourself. The allocator is a common choke point, which is why it might be a good idea to write your own if you need that extra performance.

However I heard that SWG made heavy use of STL.