Vector versus Slist?

[jamespetts]

Yesterday evening working on Simutrans-Experimental, I had a situation in which I had to replace a singly linked list (slist_tpl) with a vector (vector_tpl), because I needed the ability for objects (factories) to be able to delete themselves whilst iterating through a collection (for the industry retirement feature for Simutrans-Experimental). Using an slist iterator does not work, because the iterator becomes invalid if an object from the collection is deleted, and causes an access violation when it is used. I had to replace the entire slist with a vector, and use code like this:

Code Select Expand


sint16 number_of_factories = fab_list.get_count();
for(sint16 i = number_of_factories - 1; i >= 0; i--)
{
fabrik_t * fab = fab_list[i];
fab->neuer_monat();
// The number of factories might have diminished,
// so must adjust i to prevent out of bounds errors.
sint16 difference = number_of_factories - fab_list.get_count();
i -= difference;
        }


instead of code like this:

Code Select Expand


slist_iterator_tpl <weg_t *> weg_iter (weg_t::get_alle_wege());
while( weg_iter.next() ) {
weg_iter.get_current()->neuer_monat();
}


Unfortunately, that involved a great deal of changing other parts of the code, as the syntax for interacting with a Simutrans vector is different for the code for interacting with a Simutrans singly linked list, although I have it working now, and it seems to work fine. That, however, made me wonder what the advantages and disadvantages of each approach were. Is a vector faster than a singly linked list, or is a singly linked list faster than a vector? What is the advantage of using an iterator object over a simple for loop and overloaded [] operator? Would not an iterator take more memory and have more function call overhead than a for loop? Is each collection type good for different things? I should be very interested in the thoughts of experienced coders on the point.

[gerw]

A short overview can be found at wikepedia (http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._arrays)

A vector is faster when using an overloaded [], because in an list you have to loop over the first elements. And also a for-loop instead of an iterator should be faster (imho).

[jamespetts]

Gerw,

interesting. Do you know the reason why so many slists and iterators are used in Simutrans, then?

Edit: Ahh - so it seems that vectors should be used when one iterates more often than one adds or (especially) deletes items, whereas linked lists should be used when there is more adding and (especially) deleting than iterating?

[VS]

Theoretically:

Vector has constant access time to any item, while list (queue?) has constant add/remove time for any item (but you must first find it!).

Iterators over both types of structure should have constant advance time.

[prissi]

In practice for most applications vectors are faster, if not inserting/removing is the most often operation. Furthermore, data in a vector are close together, thus there is a good chance that the data needed are already in the cache.

But I dislike also the introduction of new function names for vector and slist from the beginning. I will make the similar again.

[jamespetts]

Prissi,

in my experimental branch, I have experimentally converted the halt_list collection from an slist_tpl to a vector_tpl, since the halts need to be iterated every step. I have not been able to profile this, since the only free profiling software that I can find has literally no documentation at all (or, at least, none that I have been able to find with a Google search).

Do you consider this a potentially worthwhile change? Would it be helpful if I produced a code patch for this so that you could test it to see whether it is faster than the current implementation?