0

My goal is to check a vector of Person* for a Person object with the name person_name. The vector is sorted by the names alphabetically. Making a temp Person is the only way I've seen to get this lower_bound call to work with the name. Is there a more efficient way of doing this, or is the temp necessary to perform the comparisons?

//person_name is a string
Person temp(person_name);
auto it = lower_bound(personVec.begin(), personVec.end(), &temp, personCompare());
if (it != personVec.end() && (*it)->getName() == person_name) {}
else { return false;  }
Rez
  • 187
  • 12
  • 3
    If you're going to be lookup names often I'd suggest an unordered_map. If you're not then why worry about finding something different when what you have works? Put it in a helper function and forget about it unless you profile and it is a bottleneck. – Retired Ninja Sep 06 '18 at 04:22

1 Answers1

3

The temp is not needed. You need comparator with proper signature.

For example when dereferencing personVec.begin() results with Person*& and person_name is of type PersonName then you can have comparator of such signature: 

bool compare(Person* const& a, PersonName const& b);

Here is just plain function but other callables with such signature will work too. Then you can use lower_bound with person_name directly:

auto it = lower_bound(personVec.begin(), personVec.end(), person_name, compare);

Your general question was about how to improve performance. That is impossible to suggest by seeing 4 lines of program. It should be found out by profiling whole program under heavy load of data and analysing the results. For example it may be that sorting that personVec takes way more time than lower_bound in it. Then usage of unordered_set instead of vector can give lot better results than optimizing the search function in vector.

Öö Tiib
  • 10,809
  • 25
  • 44
  • `unordered_map` looks like the right way to go, but I'm not sure about the implementation. `` I set it up with the hash function and the equals function. `find()` uses the first template parameter (the key), as do hash and equals, but I want to search by the input `person_name` and then get the iterator to the pointer, and I should be able to do this without a `temp`. Could you elaborate? @Retired Ninja – Rez Sep 06 '18 at 09:04
  • I should clarify: I'm investigating `unordered_map` because I read that it may be useful for what I'm trying to do, but I'll use `unordered_set` if it's sufficient. – Rez Sep 06 '18 at 09:29
  • Did you do profiling of ready made flawless product with high load of data? Otherwise the correct way is to implement the product and forget about performance before it is fully correct and then profile it and do performance works. Only then you know what you need to have in that `unordered_set

    ` or `unordered_map` or whatever other container. Don't use "I want", use "I need, because ..." (fill the gap). For example that P, is there need to be Person* not Person? Do you need the Person instance to be mutable, do you need it to be dynamically polymorphic?

     – Öö Tiib Sep 06 '18 at 10:29
  • I made sure the results are correct before going to this step. The reason I am using `Person*` for the vector is that I am making a graph program with `Person` as the node type, and I need an implementation similar to this [https://stackoverflow.com/a/44859718/5181816] in order to have access to all the nodes and perform several tasks while they are available, such as connecting and traversing. – Rez Sep 06 '18 at 17:19
  • I think I figured it out: `unordered_map` This lets it do `find()` on the string, and then the iterator gives access to the `Person` with `it->second`. – Rez Sep 06 '18 at 17:45