c++ using std::lower_bound to find element in array by 2 parameters

Question

I have a problem using lower_bound to find element in array by 2 parameters.

I have a

struct person{
    public:
    person(const std::string CITY, const std::string ADDRESS, const std::string REGION, const unsigned ID, std::string PARENT = ""): m_city(CITY), m_addr(ADDRESS), m_region(REGION), m_id(ID), m_parent(PARENT) {}

    std::string m_city;
    std::string m_addr;
    
    std::string m_region;
    unsigned m_id;
    
    std::string m_parent;

};

from this structs there is a std::vector<person>

How can I find exact person using lower_bound in vector which is already sorted by Region?

My approach works the worst way. Most of the time it doesn't find anything.

auto iteratorRegion = findPerson(m_sortedByRegion, candidatePerson);

std::vector<person>::iterator findPerson(std::vector<Person>& ARRAY, const person& candidatePerson) const {
    auto iterator = std::lower_bound(ARRAY.begin(), ARRAY.end(), candidatePerson, cityAdressComparator);    if (iterator != ARRAY.end() && iterator->m_city == candidatePerson.m_city && iterator->m_addr == candidatePerson.m_addr) {
        return iterator;
    }
    auto iterator2 = std::lower_bound(ARRAY.begin(), ARRAY.end(), candidatePerson, regionIDComparator);     if (iterator2 != ARRAY.end() && iterator2->m_region == candidatePerson.m_region && iterator2->m_id == candidatePerson.m_id) {
        return iterator2;
    }
    return ARRAY.end(); 
}

All comparators looks like this inside:

if (!(realEstateL.m_city == realEstateR.m_city))
{
    return realEstateL.m_city < realEstateR.m_city;
}
return realEstateL.m_addr < realEstateR.m_addr;

Answer 1

std::lower_bound is typically used to find the first element that is not less than the given value in a sorted range. Since you want to find an exact person based on two parameters (Region and ID), you may need to use a custom comparator function to achieve this.

In below example, the comparePerson function compares two person objects first by m_region and then by m_id. This custom comparator is then used with std::sort to sort the vector by region. Finally, std::lower_bound is used with the same custom comparator to find the exact person in the sorted vector.

Here's how you can use std::lower_bound with a custom comparator to find the exact person in the sorted vector:

#include <iostream>
#include <vector>
#include <algorithm>

struct person {
    public: person(const std::string CITY, const std::string 
    ADDRESS, const std::string REGION, const unsigned ID, 
    std::string PARENT = ""): m_city(CITY), m_addr(ADDRESS), 
    m_region(REGION), m_id(ID), m_parent(PARENT) {}

    std::string m_city;
    std::string m_addr;

    std::string m_region;
    unsigned m_id;
    
    std::string m_parent;

    };

// Custom comparator function
bool comparePerson(const person& p1, const person& p2) 
{
    if (p1.m_region == p2.m_region)
    {
        return p1.m_id < p2.m_id; // If regions are the same, 
        compare by ID
    } 
    else
    {
        return p1.m_region < p2.m_region; // Otherwise, compare by 
         region
    }
 }

int main() {
    std::vector<person> persons = {
        {"CityA", "AddressA", "RegionA", 1},
        {"CityB", "AddressB", "RegionA", 2},
        {"CityC", "AddressC", "RegionB", 3}
    };

    // Sort the vector by region using custom comparator
        std::sort(persons.begin(), persons.end(), comparePerson);

    // Define the person to search for  
        person targetPerson("", "", "RegionA", 2); 
    // Searching for person in RegionA with ID 2

    // Find the person using lower_bound with custom comparator
        auto it = std::lower_bound(persons.begin(), persons.end(), 
        targetPerson, comparePerson);

        if (it != persons.end() && it->m_region == 
         targetPerson.m_region && it->m_id == targetPerson.m_id) 
          {
           std::cout << "Person found: " << it->m_city << " " << it- 
           >m_addr << std::endl;
          } 
        else {
           std::cout << "Person not found!" << std::endl;
          }
          return 0;
     }

hope it helps.