c++ std::vector search for value

Question

I am attempting to optimize a std::vector "search " - index based iterating through a vector and returning and element that matches a "search" criteria

struct myObj {
   int id;
   char* value;
};

std::vector<myObj> myObjList;

create a few thousand entries with unique id's and values and push them to the vector myObjList.

What is the most efficient way to retrieve myObj that matches the id. Currently I am index iterating like:

for(int i = 0; i < myObjList.size(); i++){
   if(myObjList.at(i).id == searchCriteria){
    return myObjList.at(i);
   }
}

Note: searchCriteria = int. All the elements have unique id's. The above does the job, but probably not the most efficient way.

Solution 1

The C++ standard library has some abstract algorithms, which give C++ a kind of functional flavour, as I call it, which lets you concentrate more on the criteria of your search than on how you implement the search itself. This applies to a lot of other algorithms.

The algorithm you are looking for is std::find_if, a simple linear search through an iterator range.

In C++11, you can use a lambda to express your criteria:

std::find_if(myObjList.begin(), myObjList.end(), [&](const myObj & o) {
    return o.id == searchCriteria;
});

When not having C++11 available, you have to provide a predicate (function object (=functor) or function pointer) which returns true if the provided instance is the one you are looking for. Functors have the advantage that they can be parameterized, in your case you want to parameterize the functor with the ID you are looking for.

template<class TargetClass>
class HasId {
    int _id;
public:
    HasId(int id) : _id(id) {}
    bool operator()(const TargetClass & o) const {
        return o.id == _id;
    }
}

std::find_if(myObjList.begin(), myObjList.end(), HasId<myObj>(searchCriteria));

This method returns an iterator pointing to the first element found which matches your criteria. If there is no such element, the end iterator is returned (which points past the end of the vector, not to the last element). So your function could look like this:

vector<myObj>::iterator it = std::find_if(...);

if(it == myObjList.end())
    // handle error in any way
else
    return *it;

Solution 2

Using std::find_if.

There's an example on the referenced page.

Here's a working example that more precisely fits your question:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct myObj
{
   int id;
   char* value;

   myObj(int id_) : id(id_), value(0) {}
};

struct obj_finder
{
    obj_finder(int key) : key_(key)
    {}

    bool operator()(const myObj& o) const
    {
        return key_ == o.id;
    }

    const int key_;
};

int main () {
  vector<myObj> myvector;
  vector<myObj>::iterator it;

  myvector.push_back(myObj(30));
  myvector.push_back(myObj(50));
  myvector.push_back(myObj(100));
  myvector.push_back(myObj(32));

  it = find_if (myvector.begin(), myvector.end(), obj_finder(100));
  cout << "I found " << it->id << endl;

  return 0;
}

And, if you have C++11 available, you can make this even more concise using a lambda:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct myObj
{
   int id;
   char* value;

   myObj(int id_) : id(id_), value(0) {}
};

int main ()
{
  vector<myObj> myvector;
  vector<myObj>::iterator it;

  myvector.push_back(myObj(30));
  myvector.push_back(myObj(50));
  myvector.push_back(myObj(100));
  myvector.push_back(myObj(32));

  int key = 100;

  it = find_if (myvector.begin(), myvector.end(), [key] (const myObj& o) -> bool {return o.id == key;});
  cout << "I found " << it->id << endl;

  return 0;
}

Solution 3

This isn't really an answer to your question. The other people who answered gave pretty good answers, so I have nothing to add to them.

I would like to say though that your code is not very idiomatic C++. Really idiomatic C++ would, of course, use ::std::find_if. But even if you didn't have ::std::find_if your code is still not idiomatic. I'll provide two re-writes. One a C++11 re-write, and the second a C++03 re-write.

First, C++11:

for (auto &i: myObjList){
   if(i.id == searchCriteria){
      return i;
   }
}

Second, C++03:

for (::std::vector<myObj>::iterator i = myObjList.begin(); i != myObjList.end(); ++i){
   if(i->id == searchCriteria){
      return *i;
   }
}

The standard way of going through any sort of C++ container is to use an iterator. It's nice that vectors can be indexed by integer. But if you rely on that behavior unnecessarily you make it harder on yourself if you should change data structures later.

Solution 4

If the ids are sorted you may perform binary search(there is also a function binary_search in stl). If they are not nothing will perform better, but still you may write your code in a shorter way using stl(use find_if).

View more solutions

Comments

[Omnifarious]

The OP may not have lambda's yet.

[leemes]

Thank you both, added a non-C++11 solution.

[narkis]

thanks - I will see if there would be a reasonable way to sort by ids when the vector is initially filled with "myObj"s - thought that would incur overhead as well, no doubt. Thanks for the suggestions!

[Christian Rau]

For the sake of clarity you might want to use the OP's definitions in your example. But nevermind, got my up-vote long ago. Maybe an int could be captured by value, but well.

[narkis]

the incoming data structure is etched in stone by some ISO standard - so probably can rely on it being unchanged - for now. Thanks for all the input though!

[Omnifarious]

@narkis: This is also faster than what you were doing, and being idiomatic means other people who know C++ will pick up on the loop faster. :-)

[Steve Jessop]

@Omnifarious: you've written your range-based for loop as if i is an iterator, but it isn't. I think you mean either for (auto i : myObjList) { if(i.id == searchCriteria) return i; } or for (auto &i : myObjList) { same thing; }.

[fgiraldeau]

Note: the return statement in the lambda example is missing