The concerned question is:
If there are a bunch of unique items, which one (vector or set) wold be more efficient to search for a particular item by value and why?
As I understand vector is more efficient (because of contiguous memory) to search by position index. But in this case I don't know the index, I only know the value.
Generalizing this to all containers which one would be more efficient and why?
Jump to PostThe question is how much data is going to be examined. The obvious answer to your question is the use of the "list" container for small to medium sets. But if you have several hundred million sets of data (large simulations) you should write your own search algorithms, anyways.
Jump to PostThe real answer is: it depends.
A std::map is implemented as a red/black tree so it is logarithmic in its search (plus whatever operator< imposes). A vector has contiguous memory so indexing is very fast but insertions/deletions from the middle of the vector are expensive. A list has basically the …
The question is how much data is going to be examined. The obvious answer to your question is the use of the "list" container for small to medium sets. But if you have several hundred million sets of data (large simulations) you should write your own search algorithms, anyways.
The question is how much data is going to be examined. The obvious answer to your question is the use of the "list" container for small to medium sets. But if you have several hundred million sets of data (large simulations) you should write your own search algorithms, anyways.
I am not sure how big is big. But say for a number which could be accomplished just by using the containers.
The real answer is: it depends.
A std::map is implemented as a red/black tree so it is logarithmic in its search (plus whatever operator< imposes). A vector has contiguous memory so indexing is very fast but insertions/deletions from the middle of the vector are expensive. A list has basically the opposite properties of a vector (indexing is linear, insertion/deletion is constant).
There are others, though. std::set, std::deque, ...
What is it you are trying to do (if this is not, in fact, homework)?
Any pointers to urls where I could read about this aspect of containers and understand it more?
If there are a bunch of unique items, which one (vector or set) wold be more efficient to search for a particular item by value and why?
The performance characteristics of the set class imply a balanced binary search tree (or similar) structure. vector is essentially a dynamic array. You'd choose between them exactly the same way you would choose between an array and a tree.
Trees are generally better if searching is the primary function and the number of items could be large. Arrays are generally better for random access and sequential lookup. Trees are inherently sorted, while sorted arrays require special insertion logic which can be more expensive.
It sounds like you should prefer the set class over the vector class, but I can't say for sure without more information on your program's needs.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.