C++ - Search vector via custom key based on elements

Question

I have a vector of structs which have about 100 members within the struct. The vector itself can grow to be as large as 1000 elements. I am trying to find a simple way to search the list based on a set of 3 elements every struct contains amongst its many members:

std::string firstName;
std::string lastName;
size_t age;

I'm trying to find a way to search the vector based on a key derived from these three values, rather than iterating through the list and doing something like:

for ( int i = 0; i < list.length(); i++ )
{
   if (element[i].lastName  == lastNameToFind  &&
       element[i].firstName == firstNameToFind &&
       element[i].age       == ageToFind)
   {
      // found the element
   }
}

I am looking for faster methods that take advantage of the underlying logic in std::vector to operate more efficiently, and if I want to search by different key tuples, I just change a couple lines of code rather than writing another search function. Is such an approach possible?

Chris Drew · Accepted Answer · 2015-07-28T05:31:21.277

4

You could use std::find_if and provide a lambda as a predicate. It will be simpler and more flexible but I'm not sure it will necessarily be faster.

auto findByNameAndAge = [&lastNameToFind, &firstNameToFind, &ageToFind]
                        (const MyStruct& s) {
                            return s.lastName  == lastNameToFind &&
                                   s.firstName == firstNameToFind &&
                                   s.age       == ageToFind;
                        };
auto result = std::find_if(list.begin(), list.end(), findByNameAndAge);

Live demo.

Alternatively, you could create a comparison operator with a key tuple or struct

using MyKey = std::tuple<std::string, std::string, int>;

bool operator==(const MyStruct& s, const MyKey& key){
  return std::tie(s.lastName, s.firstName, s.age) == key;
}

and use std::find:

auto key = MyKey{"Smith", "John", 10};   
auto result = std::find(list.begin(), list.end(), key);

Live demo.

If you want faster search you might need to reconsider how you are storing the structs. Perhaps maintain indexes or keep the vector sorted but this may impact the performance of insertions.

edited Jul 28 '15 at 05:31

answered Jul 28 '15 at 03:46

Chris Drew

14,926
3
34
54

Awesome! Thank you for the example. This is exactly what I was looking for. – Cloud Jul 28 '15 at 03:54
But it is **not** in any way faster than trivial loop. – stgatilov Jul 28 '15 at 04:25
2

@stgatilov I did make that clear in my answer from the outset. – Chris Drew Jul 28 '15 at 04:26
@ChrisDrew you can simplify a bit by using `return std::tie(s.lastName, s.firstName, s.age) == std::tie(key.lastName, key.firstName, key.age);` – vsoftco Jul 28 '15 at 04:30
@vsoftco Is that simpler? It is actually longer. – Chris Drew Jul 28 '15 at 04:33
@vsoftco If you did something like: `using MyKey=std::tuple; bool operator==(const MyStruct& s,const MyKey& key){return std::tie(s.lastName, s.firstName, s.age)==key;}` then that definitely makes sense. – Chris Drew Jul 28 '15 at 04:41
@vsoftco Actually, I've changed the answer to that because OP mentions key tuple in the question and it is a bit shorter. – Chris Drew Jul 28 '15 at 04:51

score 0 · Answer 2 · edited May 23 '17 at 11:58

The first off, why put it in a vector? I believe an urordered_map might be better off with the hash:

[&last_name, &first_name, age]() 
{
   return std::hash<std::string>(last_name+","+first_name) ^ age;
};

I think ^ is a good way of merging two hashes into one. Maybe google that part?

If you insist on a vector, maybe make a smart_ptr and store that in your vector then an unordered_map with the smart_ptr as a value.

PS: OK xor is a crappy way to hash. use boost::hash_combine or this answer.

C++ - Search vector via custom key based on elements

2 Answers2