15

what's the alternative?

Should I write by myself?

James McNellis
  • 348,265
  • 75
  • 913
  • 977
skydoor
  • 25,218
  • 52
  • 147
  • 201
  • 1
    Perhaps you should define what "find" is intended to do? – KevenK Jun 08 '10 at 00:27
  • 20
    There is a `std::find`. See http://stackoverflow.com/questions/571394/how-to-find-an-item-in-a-stdvector/571405#571405 – user229044 Jun 08 '10 at 00:27
  • 14
    The beauty of the STL lies in the __decoupling of containers and algorithms__, done by gluing them together with iterators. That's a _deliberate design decision_, which leads to _higher abstractions_ than all the OO libraries I've seen ever achieved. If you come from a stricter OO background (Java, C#), it might seem strange at first, but _it's definitely worth learning_. – sbi Jun 08 '10 at 06:56
  • There is no beauty in having to use `std::find(v.begin(), v.end(), entry) != v.end()` when we could have had `v.find(entry)` – wmjdgla Jul 26 '23 at 07:31

6 Answers6

48

There is the std::find() algorithm, which performs a linear search over an iterator range, e.g.,

std::vector<int> v;

// Finds the first element in the vector that has the value 42:
// If there is no such value, it == v.end()
std::vector<int>::const_iterator it = std::find(v.begin(), v.end(), 42);

If your vector is sorted, you can use std::binary_search() to test whether a value is present in the vector, and std::equal_range() to get begin and end iterators to the range of elements in the vector that have that value.

James McNellis
  • 348,265
  • 75
  • 913
  • 977
  • 3
    The advantage to having `std::find` as a free function is that it will work over an in memory array, a `std::vector`, or any other container that can be traversed linearly. – Thanatos Jun 08 '10 at 00:52
  • You would only see a constant factor improvement. Furthermore, it's outside the scope of what `std::find` does. (A multi-threaded find is not needed in most situations.) You could write a `parallel_find()` that worked very similarly, however, and would work over all containers that met some set of (fairly loose) requirements. – Thanatos Jun 08 '10 at 01:13
27

The reason there is no vector::find is because there is no algorithmic advantage over std::find (std::find is O(N) and in general, you can't do better for vectors).

But the reason you have map::find is because it can be more efficient (map::find is O(log N) so you would always want to use that over std::find for maps).

R Samuel Klatchko
  • 74,869
  • 16
  • 134
  • 187
  • You can certainly do better than O(N) if the vector is sorted. – moodboom Oct 11 '13 at 00:46
  • Maybe no algorithmic advantage. But there is a consistency advantage. Eg, this is nice: `template bool is_member(const C &c, const E &e) { return c.find(e) != c.end(); }` but it doesn't work with vector. – John H. Mar 14 '23 at 15:58
8

Who told you that? There's is "find" algorithm for vector in C++. Ironically Coincidentally, it is called std::find. Or maybe std::binary_search. Or something else, depending on the properties of the data stored in your vector.

Containers get their own specific versions of generic algorithms (implemented as container methods) only when the effective implementation of the algorithm is somehow tied to the internal details of the container. std::list<>::sort would be one example.

In all other cases, the algorithms are implemented by standalone functions.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • Sorry to nitpick, but what's so ironic about a find function being named "find"? – jalf Jun 08 '10 at 11:37
  • @jalf: I assume it was intended sarcastically...pointing out that the OP is complaining there is no "find" when there is "find" and a google search for "c++ find" returns the second result as a link to `std::find` on cplusplus.com – KevenK Jun 08 '10 at 12:38
  • 3
    So sarcastically calling something ironic... Man, that's deep. ;) – jalf Jun 08 '10 at 14:53
5

Having a 'find' functionality in the container class violates 'SRP' (Single Responsibility Principle). A container's core functionality is to provide interfaces for storage, retrieval of elements in the container. 'Finding', 'Sorting', 'Iterating' etc are not core functionality of any container and hence not part of it's direct interface.

However as 'Herb' states in Namespace Principle, 'find' is a part of the interface by being defined in the same namespace as 'vector' namely 'std'.

fdermishin
  • 3,519
  • 3
  • 24
  • 45
Chubsdad
  • 24,777
  • 4
  • 73
  • 129
  • 3
    However, it is entirely appropriate for a container to provide its own `find` function _if_ it can provide one that performs better than the generic `std::find` algorithm (consider `std::map::find`). – James McNellis Sep 29 '10 at 14:43
4

Use std::find(vec.begin(), vec.end(), value).

And don't forget to include <algorithm>

M. Williams
  • 4,945
  • 2
  • 26
  • 27
3

what's the alternative?

The standard offers std::find, for sequential search over arbitrary sequences of like-elements (or something like that).

This can be applied to all containers supporting iterators, but for internally sorted containers (like std::map) the search can be optimized. In that case, the container offers it's own find member function.

why there is no find for vector in C++?

There was no point in creating a std::vector<???>::find as the implementation would be identical to std::find(vector.begin(), vector.end(), value_to_find);.

Should I write by myself?

No. Unless you have specific limitations or requirements, you should use the STL implementation whenever possible.

utnapistim
  • 26,809
  • 3
  • 46
  • 82
  • This is the best answer here. It actually gives a reason why vector doesn't have a find method, and why map for example does. It is not obvious to a C++ beginner (or even advanced) user as to why this is the case. – Arne Mar 19 '20 at 09:17