Member Avatar for kimw

I would like to implement a function similar to the math function from excel, that is, given a vector and a value in the vector, return the relative position of that value in that container.

However, my code

vector<double> vec;
double x = 25.0;
int pos = 0;

for (int i = 0; i!=vec.size(); ++i) {
     if (x == vec[i])
     pos = i;
}

return pos;

is not as efficient as i wanted to be. What are more efficient ways to implement this simple function?

Thank you.

  • 4 Contributors
  • 6 Replies
  • 111 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by Ancient Dragon

Dani AI

Generated

’s loop works but has two practical problems: it returns 0 if the value is not found (pos is initialized to 0) and it does a linear scan every time. For a one-off search in an unsorted vector this is fine (O(n)), but with many vectors or many repeated lookups the cost adds up. correctly suggested std::find for unsorted data and correctly suggested sorting and binary-searching for repeated queries — the choice depends on frequency of lookups vs. updates.

Useful options and tradeoffs:

  • Single / rare lookup on an unsorted vector: keep the linear scan (std::find). Initialize the “not found” sentinel (e.g., -1) rather than 0.
  • Many lookups on a static vector: sort once and use std::lower_bound / std::distance to get the index (O(log n) per lookup, plus O(n log n) to sort).
  • Many lookups on mutable data: build an index (hash or tree). A hash-based index (std::unordered_map) gives average O(1) lookups; std::map gives O(log n) and orders keys.

Floating-point cautions and duplicates:

  • Exact equality on double can be fragile. If values are the result of computation, compare with an epsilon or quantize/round values before using them as map keys.
  • If duplicates matter, map a value to a vector of indices (value -> std::vector<size_t>), or for sorted data use equal_range to get the subrange of matching entries.

Small examples (compact):

auto it = std::lower_bound(vec.begin(), vec.end(), x);
if (it != vec.end() && *it == x) return std::distance(vec.begin(), it);
return -1;
std::unordered_map<double, std::vector<size_t>> idx;
for (size_t i=0;i<vec.size();++i) idx[vec[i]].push_back(i);
auto it = idx.find(x);

If vectors change frequently, either rebuild the index on change or maintain it incrementally. Measure (profile) before large rewrites: 10k elements is small for one-off searches, but patterns of many repeated queries or many vectors can justify the extra memory and update complexity of an index.

Recommended Answers

All 6 Replies

Member Avatar for Lerner

You could consider the find() or find_first_of() algorhithms or you could consider a map or multimap structure instead of a vector.

Member Avatar for kimw

thank you. i'm new to map and could you fill me some details for me

map<double, int> counter;
vector<double> vec;
double x = 25.0;        // value to search for
int pos = 0;
int i = 0;
while (i < vec.size()) {
      ++counter[!x];
      i += 1;
}
pos = ++counter[!x];

am i on the right track with this? thanks

Member Avatar for Member #46692

When you say not efficient, how bad are we talking. How many values are in your little vector?

How long does it take to find the one you want?

Member Avatar for Lerner

Depending on your needs, map/multimap may not be what you want. If you want a brief overview here's a reference, though I'd recommend a good STL reference book if you don't already have one and want to start working with STL materials.

http://www.cppreference.com/cppmap/index.html


I suspect find() or find_first_of() is likely to be your best bet if the vector is unsorted. If the vector is sorted, then you may be able to use a more efficient search mechanism.

Member Avatar for kimw

thank you all. i guess i'll stick to find() then.
my vectors usually have 10k+ elements and i have many of such vectors. my goal is just to maximize efficiency as much as possible...

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.