How to find an object in std::vector?

Question

Suppose I have a class called Bank, with attributes

class Bank {
      string _name;
}

Now I declare a vector of Bank.

vector<Bank> list;

Given a string, how do I search the vector list for that particular Bank object that has the same string name?

I'm trying to avoid doing loops and see if there is an stl function that can do this.

[`std::find` or `std::find_if`](http://en.cppreference.com/w/cpp/algorithm/find). This is assuming that `Bank` has other members, but you only want to find on `_name`. — BoBTFish, Feb 19 '14 at 15:12
`vector` does not impose any ordering on the list, so searching it can only be done linearly. There are STL containers that do order their contents, though. — Brian A. Henning, Feb 19 '14 at 15:12
Although `vector` does not impose ordering, ordering may be imposed on it. In this case, you can use other algorithms such as `std::binary_search` (only tests for the presence of the search item and returns a `bool`) or `std::equal_range` for O(log n) searches. — Fred Larson, Feb 19 '14 at 15:18
I don't have to bother about efficiency, but just want a compact code. — Yellow Skies, Feb 19 '14 at 15:20
@FredOverflow: Because it's outdated and not shipped with your toolchain. One should prefer the C++ Standard Library (even though the STL tracks it pretty closely nowadays). — Lightness Races in Orbit, Feb 19 '14 at 15:43

fredoverflow · Accepted Answer · 2014-02-19T15:30:52.340

13

You can use good old linear search:

auto it = std::find_if(list.begin(), list.end(), [&](const Bank& bank)
{
    return bank._name == the_name_you_are_looking_for;
});

If there is no such bank in the list, the end iterator will be returned:

if (it == list.end())
{
    // no bank in the list with the name you were looking for :-(
}
else
{
    // *it is the first bank in the list with the name you were looking for :-)
}

If your compiler is from the stone ages, it won't understand lambdas and auto. Untested C++98 code:

struct NameFinder
{
    const std::string& captured_name;

    bool operator()(const Bank& bank) const
    {
        return bank.name == captured_name;
    }
};

NameFinder finder = {the_name_you_are_looking_for};
std::vector<Bank>::iterator it = std::find_if(list.begin(), list.end(), finder);

edited Feb 19 '14 at 15:30

answered Feb 19 '14 at 15:12

fredoverflow

256,549
94
388
662

Yet another syntactic sugar treat that allows to implement incredibly inefficient search without noticing, unless you're a template expert. "Leave the user free to shoot himself in the foot" philosophy", I suppose. – kuroi neko Feb 19 '14 at 15:15
12

@kuroineko I have no idea what you're talking about. Are you complaining that linear search has linear complexity? – fredoverflow Feb 19 '14 at 15:16
Never seen auto before. What does it do? I'm new to programming/c++. – Yellow Skies Feb 19 '14 at 15:18
@YellowSkies Since 2011, `auto` means "type inference" in C++. That is, the compiler will figure out the type of a variable based on the expression that is used to initialize it. In this case, the type of `it` is inferred to be `std::vector::iterator`. – fredoverflow Feb 19 '14 at 15:19
@YellowSkies: Note that in addition to `auto`, this also uses a lambda function. You'll need to compile C++11 enabled for both. There are pre-C++11 ways to do this if necessary. – Fred Larson Feb 19 '14 at 15:24
where is the lambda function being used? [](const Bank& bank) ? – Yellow Skies Feb 19 '14 at 15:25
The lambda function is `[](const Bank& bank) { return bank._name == the_name_you_are_looking_for; }` – Fred Larson Feb 19 '14 at 15:26
Can I get a quick crash course on what is a lambda function? No need for details. – Yellow Skies Feb 19 '14 at 15:26
@YellowSkies: Try reading something like http://stackoverflow.com/a/7627218/10077 – Fred Larson Feb 19 '14 at 15:27
Is there anyway to avoid using this lambda expression and yet get a short and sweet answer like the above? Haven't learnt that yet. the link lost me at functor. – Yellow Skies Feb 19 '14 at 15:28
@YellowSkies Sure, see my update. Note how much boilerplate code lambdas prevent. – fredoverflow Feb 19 '14 at 15:31
@FredOverflow when it could be in log2(n), yes. What is the point in giving access to a standard feature that does no better than a vintage for loop, except enticing a newbie into implementing an inefficient data structure? – kuroi neko Feb 19 '14 at 15:37
@kuroineko All I did was answer the OP's question. We don't have enough information about the use cases to decide what operations we should optimize for. If searching for a bank by name is the predominant operation, and the list rarely changes, then binary search on a sorted list would probably be the best idea. – fredoverflow Feb 19 '14 at 15:40
@FredOverflow Yeah, leave the noob free to shoot himself in the foot, and don't waste any time warning him about using a potentially inappropriate data structure hidden behind the syntactic sugar. Pure C++ philosophy. – kuroi neko Feb 19 '14 at 15:44
3

@kuroineko Feel free to provide an answer that discusses more efficient data structures. You'll have my upvote. – fredoverflow Feb 19 '14 at 15:48
1

@kuroineko: You don't know what other data structure would be more efficient. It may well be that the OP's requirements simply mean that a linear search isn't that big of a deal or that other data structures can't be used. You can't know in advance that linear search *is* inappropriate. – Puppy Feb 19 '14 at 15:52
2

@kuroineko There's no syntactic sugar. It's a function that performs linear search. There's another function that performs binary search. Neither is syntactic sugar. They're both functions and they use the same syntax that *every other function* uses. They have one key difference, though: the binary search function has special preconditions that linear search doesn't, and it hides those preconditions behind the "syntactic sugar". How's that for shooting yourself in the foot? And you are wrong. Linear search cannot run in logarithmic time. That's why it is called *linear* search. – R. Martinho Fernandes Feb 19 '14 at 15:52
2

@kuroineko: To use binary search, the data must first be sorted. Depending on collection size and frequency of search vs. modification, keeping the collection sorted to allow binary search can easily be an overall loss. – Jerry Coffin Feb 19 '14 at 15:54

kuroi neko · Answer 2 · 2014-02-19T17:19:26.647

As per popular request, just a side note to warn potential beginners attracted by this question in the future:

std::find is using a linear method, because the underlying object (a vector in that case) is not designed with search efficiency in mind.

Using a vector for data where search time is critical will possibly work, given the computing power available in your average PC, but could become slow quickly if the volume of data to handle grows.

If you need to search quickly, you have other containers (std::set, std::map and a few variants) that allows retrieval in logarithmic times.

You can even use hash tables for (near) instant access in containers like unordered_set and unordered_map, but the cost of other operations grows accordingly. It's all a matter of balance.

You can also sort the vector first and then perform a dichotomic search with std:: algorithms, like binary_search if you have a strict order or lower_bound, upper_bound and equal_range if you can only define a partial order on your elements.

Why not talk about `std::unordered_set` and `std::unordered_map` while you're at it? They allow constant time retrieval. That's much better than logarithmic time. — Etienne de Martel, Feb 19 '14 at 16:42
@Etienne Yep, I added them, though their use is quite far from what you would expect from an array. The main point was to warn newbies about the potential inefficiency of a linear search. — kuroi neko, Feb 19 '14 at 17:20

score 0 · Answer 3 · answered Feb 19 '14 at 15:12

0

std::find will allow you to search through the vector in a variety of ways.

answered Feb 19 '14 at 15:12

Sean

60,939
11
97
136

How to find an object in std::vector?

3 Answers3