Member Avatar for ontherocks

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?

  • 4 Contributors
  • 6 Replies
  • 186 Views
  • 11 Hours Discussion Span
  • Latest Post Latest Post by Narue

Dani AI

Generated

Building on ' question and the points by , and : for lookups by value the practical contenders are (1) a hash-based container, (2) a sorted dynamic array, and (3) a tree. std::unordered_set gives average-case constant-time lookup via hashing; a sorted std::vector + binary search gives logarithmic lookup but often wins in real-world throughput because of contiguous storage and cache locality; std::set gives ordered traversal and guaranteed logarithmic complexity. (std::unordered_set, std::vector, std::set). (en.cppreference.com)

Practical examples — insert once, many lookups (sorted vector) vs dynamic insert/lookup mix (unordered_set):

#include <vector>
#include <algorithm>
#include <string>

std::vector<std::string> v = /* filled */;
std::sort(v.begin(), v.end());
auto it = std::lower_bound(v.begin(), v.end(), "key");
if (it != v.end() && *it == "key") { /* found */ }
#include <unordered_set>
#include <string>

std::unordered_set<std::string> s;
s.reserve(1000);
s.emplace("key");
if (s.find("key") != s.end()) { /* found */ }

See the container docs for exact member calls and complexity guarantees. (en.cppreference.com)

Trade-offs and gotchas: hashing has overhead (compute hash + equality) and worst-case behavior depends on bucket distribution; rehashing can be avoided with reserve(). Sorted-vector lookups pay O(log n) for search but benefit from superb cache performance (spatial locality), so for mostly-read, rarely-modified data a sorted vector is often fastest in practice. Trees (std::set) pay O(log n) and are best when ordered iteration or stable iterator validity for updates is required. Linked lists have constant-time splice/insert once you have an iterator but are poor for value lookups because of pointer-chasing. (Locality of reference, std::list). (en.wikipedia.org)

Quick checklist: if lookups ≫ updates and memory is tight → sorted vector + binary search; if many inserts/removals and fastest average lookup needed → std::unordered_set (choose a good hash, call reserve); if ordered keys or strict worst-case guarantees → std::set. Benchmark with representative data (use std::chrono and realistic key distributions) before committing.

Recommended Answers

All 6 Replies

Member Avatar for PhysicsExpert

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.

Member Avatar for ontherocks

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.

Member Avatar for L7Sqr

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)?

Member Avatar for ontherocks

Any pointers to urls where I could read about this aspect of containers and understand it more?

Member Avatar for L7Sqr

A pretty good survey is here Complete with the types, runtime behavior (in Big-O notation), and links to more in-depth discussion for each supported method.

Member Avatar for Narue

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.