C ++ get index of array element by value

Question

So far, I have saved the array in a vector, and then iterated over the vector to find the corresponding element, and then returned the index.

Is there a faster way to do this in C ++? The STL structure that I use to store the array does not matter to me (it does not have to be a vector). My array is also unique (no duplicate elements) and ordered (like a list of dates going on time).

Answer 1

Since the elements are sorted, you can use binary search to find the corresponding element. The C ++ standard library has an algorithm std::lower_bound , which can be used for this purpose. I would recommend wrapping it in my own binary search algorithm for clarity and simplicity:

 /// Performs a binary search for an element /// /// The range `[first, last)` must be ordered via `comparer`. If `value` is /// found in the range, an iterator to the first element comparing equal to /// `value` will be returned; if `value` is not found in the range, `last` is /// returned. template <typename RandomAccessIterator, typename Value, typename Comparer> auto binary_search(RandomAccessIterator const first, RandomAccessIterator const last, Value const& value, Comparer comparer) -> RandomAccessIterator { RandomAccessIterator it(std::lower_bound(first, last, value, comparer)); if (it == last || comparer(*it, value) || comparer(value, *it)) return last; return it; } 

(The C ++ standard library has std::binary_search , but returns bool : true if the range contains the false element otherwise. This is not useful if you want the iterator to be in the element.)

Once you have an iterator for the element, you can use the std::distance algorithm to calculate the index of the element in the range.

Both of these algorithms perform equally well any random access sequence, including both std::vector and regular arrays.

Answer 2

If you want to associate a value with an index and quickly find the index, you can use std::map or std::unordered_map . You can also combine them with other data structures (for example, std::list or std::vector ) depending on other operations that you want to perform on the data.

For example, when creating a vector, we also create a lookup table:

 vector<int> test(test_size); unordered_map<int, size_t> lookup; int value = 0; for(size_t index = 0; index < test_size; ++index) { test[index] = value; lookup[value] = index; value += rand()%100+1; } 

Now, to look at the index, you simply:

 size_t index = lookup[find_value]; 

Using a hashtable-based data structure (like unordered_map) is a pretty classic space / time trade-off and can outperform performing binary searches for this kind of “reverse” lookup operation when you need to search a lot. Another advantage is that it also works when the vector is unsorted.

For fun :-) I did a quick test in VS2012RC, comparing James binary search code with linear search and using unordered_map to search, all on the vector:

Up to ~ 50,000 elements of unordered_value (x3-4) surpasses binary search, which demonstrates the expected behavior of O (log N), a somewhat unexpected result is that unordered_map loses O (1) behavior for 10,000 elements, presumably to hash collisions, possibly to the problem of implementation.

EDIT: max_load_factor () for an unordered map is 1, so there should be no collisions. The performance difference between the binary search and the hash table for very large vectors seems to be related to caching and varies depending on the search pattern in the benchmark.

Choosing between std :: map and std :: unordered_map talks about the difference between ordered and unordered maps.