...or is that just a myth? Back when I had a game programming job, we used a custom templated List class instead of using STL lists or vectors, because programmers there who were far senior to me wanted to avoid STL. I was just curious as to why that might be, because as far as I understand it, STL containers maintain memory pools to make sure that the data is in contiguous memory. So I'm curious as to what other optimizations they might have been making for the sake of speed. I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically. Maybe that was enough of a reason? I dunno. Or maybe they just felt more comfortable using a list class that they designed, understanding intimately the inner-workings of it. Our engine was cross-platform, and even though STL is fairly portable, maybe they just wanted to make sure that all platforms had the same implementation, internally. I dunno. I mean I know you can't read their minds or anything, but I am curious as to what your thoughts are. My game right now is tiny, running at 200fps, so the STL containers are working just fine for me. : )

Quote:Original post by CDProp

I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically. Maybe that was enough of a reason? I dunno.

If using custom allocator, the proper way to signal such condition would be throwing std::bad_alloc. But this would be closer to abuse of exceptions:

std::vector<int, special_allocator> my_v;try {  v.add(x);} catch (std::bad_alloc) {  v.get_allocator().allocate_some_more();  v.add(x);}

But this is ugly, since STL is designed to abstract away allocations, so it simply does that internally and automatically, so bad_alloc should get thrown only rarely.

Unfortunately, this makes std::vector suboptimal for certain types of tasks. Alternative would be to provide alternate interface to above functionality:

template < class T, class A > bool push_back(vector<T,A> & v, T & x) {  if (v.size() < v.capacity()) {    v.push_back(x);    return true;  } else {    return false;  }};...if (!push_back(v, x)) {  v.get_allocator().allocate_some_more();  if (push_back(x)) {    // seems we're out of memory  }}

Of course, we now end up with what vector already does, so unless the out of memory condition really requires some complex handling, then default implementation would do the just just fine.

Such patterns are idiomatic when avoiding use of exceptions, but they can result in somewhat simpler generated code, while source is somewhat more complex.

Quote:Our engine was cross-platform, and even though STL is fairly portable, maybe they just wanted to make sure that all platforms had the same implementation, internally.

That is a valid reason. There are quite some differences in implementation. MVS's checked iterators can be a cause of problems, MVS's string uses internal (16 byte IIRC) buffer in every string, so that can cause different allocation patterns. Hash map is a mess since it resides in different namespaces.

Quote:My game right now is tiny, running at 200fps, so the STL containers are working just fine for me. : )

For vector, element access should be exactly the same as with plain arrays.

Most of the time, bottlenecks occur due to allocations and re-allocations, but those commonly expose problem with algorithm, not so much with STL implementation.

If one needs a list of sorts to which elements are added, then it's reasonable to examine which method is most suitable. Can list be pre-allocated to fixed number of elements, can its storage be pre-allocated in single chunk, does it even need to be allocated or can it be re-used, and similar.

The STL in itself is very fast, in fact is is very hard to write your own versions which will be faster. Many game studios cook up their own versions of containers for many different reasons.

One big reason is knowing how that container will act. Meaning, knowing when and how basic functions access the data structure. Or knowing, for instance, how large, or when a vector will resize. By making your own container, you know for certain how each container will behave under different conditions.

For console developers there are a few good reasons not to use the STL. Biggest is memory issues; the console only has a fixed amount of memory. STL containers could easily grow in size or fragment memory. As mentioned before, it is not always wise to resize a vector by doubling the size or something similar. Instead, it is a better use of memory to only add enough space for eight or 16 new items at a time.

Another important thing for consoles to watch for is cache coherency. Node based data structures (list, map, etc. ) can easily have to load in new data every step. Instead you can cook up a version of these containers which hold everything in contiguous memory, but acts like a node based structure, this way there is a better chance of the node already being loaded into memory.

Lastly, there may be feature that you wish to add or remove from the STL. For instance, it is usually undesirable for a map to create a new element when one does not exist using operator[]. Or you may wish for push_back() to return a reference to the newly inserted element. These are small things that can prevent bugs and make development go much faster.

Wow, some great insights, guys. Thanks!

Quote:Original post by CDProp

I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically.

I'm having trouble seeing the advantage of this. All it really does is set an upper size limit on the vector, which is quite easily done with a push_back wrapper.

Quote:Original post by scjohnno

Quote:Original post by CDProp

I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically.

I'm having trouble seeing the advantage of this. All it really does is set an upper size limit on the vector, which is quite easily done with a push_back wrapper.

That's right. Why go through all the trouble of implementing your own containers, making sacrifices in performance (since the people who write implementations of STL usually know very well what they're doing), when you can just make a wrapper? Make an inherited class Vector<> that checks for the capacity and pre-allocates the way you want when adding a new element. You may not be able to override many functions (I'm not sure but I think most of them aren't virtual) but you can certainly add your own.