c++ 使用 std::lower_bound 通过 2 个参数查找数组中的元素

Question

我在使用

lower_bound

通过 2 个参数查找数组中的元素时遇到问题。

我有一个

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;

};

从这个结构中有一个

std::vector<person>

如何在已按地区排序的

lower_bound

中使用

vector

找到确切的人？

我的方法效果最差。大多数时候它什么也找不到。

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(); 
}

所有比较器的内部看起来都是这样的：

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 通常用于查找排序范围内不小于给定值的第一个元素。由于您想根据两个参数（区域和 ID）找到准确的人，因此您可能需要使用自定义比较器函数来实现此目的。

在下面的示例中，comparePerson 函数首先通过 m_region 比较两个 person 对象，然后通过 m_id 进行比较。然后将此自定义比较器与 std::sort 一起使用以按区域对向量进行排序。最后，std::lower_bound 与相同的自定义比较器一起使用，以在排序向量中找到确切的人。

以下是如何使用 std::lower_bound 和自定义比较器来查找排序向量中的确切人物：

#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;
     }

希望有帮助。