Menu
Is there any advantage to using C++11's std::find over a container's find method?
In the case of std::vector (which does not have a find method) does std::find use some smart algorithm or the naive way of simply iterating over every element?
In the case of std::map it seems you need to pass along an std::pair, which is the value_type of an std::map. This does not seem very useful as usually you'd want to find for either a key or a mapped element.
What about other containers like std::list or std::set or std::unordered_set ?
802
std::find in C++ last, including the element pointed by first but not the element pointed by last. Return Value : An iterator to the first element in the range that compares equal to val. If no elements match, the function returns last.
A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.
Array is memory efficient data structure. Vector takes more time in accessing elements. Array access elements in constant time irrespective of their location as elements are arranged in a contiguous memory allocation.
Vectors are the same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators.
In the case of std::vector (which does not have a find method) does std::find use some smart algorithm or the naive way of simply iterating over every element?
It cannot, because vectors are not sorted. There is no other way to find an element in an unsorted vector than a linear search with O(n) complexity.
On the other hand, sequence containers do not offer a find() member functions, so you could not possibly use that.
In the case of std::map it seems you need to pass along an std::pair, which is the value_type of an std::map. This does not seem very useful as usually you'd want to find for either a key or a mapped element.
Indeed, here you should use the find() member function, which guarantees a better complexity (O(log N)).
In general, when a container exposes a member function with the same name as a generic algorithm, this is because the member function does the same thing, but offers a better complexity guarantee.
What about other containers like std::list or std::set or std::unordered_set ?
Just like std::vector, std::list is not a sorted container - so the same conclusion applies.
For std::set and std::unordered_set, instead, you should use the find() member function, which guarantees a better complexity (O(log n) and average O(1), respectively).
162
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
