Thread: Speed in array or list structure

Originally Posted by überfuzz

Ok, I guess I don't need any links to any articles then. Thanks!

oogabooga I've been tinkering with vectors and I always seem to end up slowing things down... Shame on those who give in!

Note that I did not recommend vector because I consider it in any way optimal for your needs. I recommended vector because your (lack of) requirements means that any choice of container is sufficient. Vector is a workable default choice, nothing more.

If you care about performance, you need to articulate stronger requirements. If you actually do that, you will actually need to read some articles about the design trade-offs related to selecting containers.

It is possible to slow down things regardless of your choice of container: just pick a series of operations that plays to the weakness of each container. There is no universally optimal container (i.e. each container type supports some operations efficiently by some measure, and other operations inefficiently). It is also possible to hit program performance by unnecessarily creating (non-lazy) copies of entire containers.

Originally Posted by überfuzz

However, I believe wrote that I'm use to work with java, not C++ hence my questions and inexperience. Further, for someone with some code experience it should then be quite obvious that I don't know much about how different libraries preforms in C++.

Ah, but Java has a bunch of standard library components too, including useful containers similiar to those available in the C++ standard library

If I were programming in Java, I would consider the container to use based on similiar considerations of how the elements are to be inserted and how they are to be accessed. For example, if I want to map from keys to values such that the keys are sorted, I might go for TreeMap in Java and std::map in C++. If I just want to map from keys to values with the aim of accessing the keys as fast as possible, I might go for HashMap in Java and std::unordered_map in C++, with a suitable hash function.

I would not ask if HashMap might not be good enough such that I should implement my own hash table, unless after testing I really do discover that the general purpose HashMap is not good enough, yet a hash table is appropriate. This is why your question stunned me: it is like a Java programmer asking if he/she should implement a red/black tree instead of using TreeMap because TreeMap might not be good, even before having any evidence that a custom balanced binary tree implementation might beat TreeMap to satisfy performance requirements in this case... when it may well be that choosing HashMap instead is the way to go, or perhaps the performance requirements will already be met by TreeMap.

Originally Posted by oogabooga

You may be able to speed up the vector by reserving some reasonable amount of space initially:

Yeah, then push_back will go from amortised constant time to constant time, at least until the size of the vector exceeds the reserved capacity.

So far my asessment is still that std::vector is best, however I appear to have forgotten to ask more about how the data will be accessed.
Once you put something in there, do you intend to search for it at some point, or are you only ever just going to process the whole lot at once?
Also, will there ever be any duplicates?

Originally Posted by überfuzz

I'll couldn't see any significant different in performance while preallocating a bigger vector.

Yeah, that coincides with Stroustrup's observation in his answer to the FAQ Why are the standard containers so slow?:

Originally Posted by Bjarne Stroustrup

People sometimes worry about the cost of std::vector growing incrementally. I used to worry about that and used reserve() to optimize the growth. After measuring my code and repeatedly having trouble finding the performance benefits of reserve() in real programs, I stopped using it except where it is needed to avoid iterator invalidation (a rare case in my code).

You might also want to read the rest of that FAQ, though much of it does not apply in your case because you are storing objects of a built-in integer type.

By the way, what compiler are you using?