This is a discussion on Speed in array or list structure within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by überfuzz I've been tinkering with vectors and I always seem to end up slowing things down... Shame ...
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.
Ah, but Java has a bunch of standard library components too, including useful containers similiar to those available in the C++ standard libraryOriginally Posted by überfuzz
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.
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.Originally Posted by oogabooga
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?
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
oogabooga - Test runs showed: 220 seconds when I stored data or more precisely hits in the form of an integer with push_back in a vector. 177 seconds when I just counted hits. I'll couldn't see any significant different in performance while preallocating a bigger vector. (I don't remember how big i tried, but I'll try a real big and report back.)
Yeah, that coincides with Stroustrup's observation in his answer to the FAQ Why are the standard containers so slow?:Originally Posted by überfuzz
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.Originally Posted by Bjarne Stroustrup
By the way, what compiler are you using?