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:
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:
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.
Topic: Vector versus Slist? (Read 3827 times)
previous topic - next topic
