c++ - 用于比较字符串的结构 vector 的 lower_bound

Question

我想问你一个问题，但首先我会解释一下......

我在 vector People 中有一个结构 SPerson。

typedef struct SPERSON {
   string name;
   string address;
   string birthcertificatenumber;
} SPerson;
std::vector<SPerson> People;
People.resize(100);
counter = 0;

有一个类是添加新人的函数

bool NewPerson(const string & name, const string & address, const string & birthcertifikatenumber)
{
   SPerson sPerson;
   sPerson.name = name;
   sPerson.address = address;
   sPerson.birthcertificatenumber = birthcertificatenumber;
   People[counter] = sPerson;
   counter++;
 return true;
}

在这个函数中，我需要检查是否已经有一个人有相同的名字“和”地址或一个人有出生证明号码

我需要对数搜索，而不是线性搜索。

我使用了下面的 NewPerson 中的函数，它按我想要的方式工作，但是当有大量数据时，它很慢，我需要更快。我听说过 lower_bound 函数用于二进制搜索，但我不知道如何将它应用到我的案例中。你能给我一个建议吗？谢谢。

 auto it = find_if(begin(People), end(People), [=] (SPerson const& f) { 
    return (((strcasecmp(name.c_str(), f.name.c_str()) == 0) and (strcasecmp(address.c_str(), f.address.c_str()) == 0)) or (f.birthcertifikatenumber == birthcertifikatenumber));  
    });
bool found = (it != end(People)); 
if (found == true)
{    
    return false;
}

---

@Slava:谢谢，它实际上工作得很好。

我有这些输入记录:

• 姓名:John，地址:eee，出生日期证明:abcdef
• 姓名:Pierre，地址:aaa，出生日期证明:123456
• 姓名:Jean，地址:bbb，出生日期证明:1234
• 姓名:Peter，地址:ccc，出生日期证明:ABCDEF

它按出生日期证书排序，就像这样:

• 姓名:Jean，地址:bbb，出生日期证明:1234
• 姓名:Pierre，地址:aaa，出生日期证明:123456
• 姓名:Peter，地址:ccc，出生日期证明:ABCDEF
• 姓名:John，地址:eee，出生日期证明:abcdef

按名称和地址分类如下:

• 姓名:Jean，地址:bbb，出生日期证明:1234
• 姓名:John，地址:eee，出生日期证明:abcdef
• 姓名:Peter，地址:ccc，出生日期证明:ABCDEF
• 姓名:Pierre，地址:aaa，出生日期证明:123456

很好，谢谢。现在我想通过姓名和地址或出生日期证明找到一个人，这样我就可以调用如下函数:ErasePerson("Peter", "ccc");//通过名字和地址删除这个人ErasePerson("123456");//通过出生日期证书删除此人

我想使用 O(log n)，所以现在我想找到特定的人并将其删除。我不确定如何使用 lower_bound 函数。我尝试了一些事情，但没有成功。我不确定如何创建比较函数以及我的比较函数是否正确。

 struct SPerson {
     string name;
     string address;
     string birthdatecertificate;
};   
std::vector<SPerson> VPeople;
std::vector<size_t> idxNameAddress;

bool People::ErasePerson(const string & name, const string & address)
{
   SPerson Person;
   Person.name = name;
   Person.address = address;
   Person.birthdatecertificate= ""; 

  std::lower_bound(idxNameAddress.begin(), idxNameAddress.end(), Person, cmpFunction);
return false;
}

Answer 1

std::lower_bound只能用于排序后的容器(否则，您将得到无效结果...没有警告/错误)，这不是您的 std::vector 的情况。 .

最简单的方法是将您的元素存储在一个排序的容器中。像std::set或 std::map .然后，您的排序容器将能够使用非线性搜索算法报告对象是否已经存在。

那些容器将要求您提供比较运算符:

bool operator<(const SPERSON& left, const SPERSON& right )
{
    return left.name < right.name;
}

然后做:

std::set<SPERSON> People;

使用以下方法添加元素:

if ( People.find( sPerson ) == People.end() )
    People.insert( sPerson );
// else: item with same name already exists!