C++

Question

我有 vector 个 struct 成员，struct 中有大约 100 个成员。 vector 本身可以增长到 1000 个元素。我正在尝试找到一种简单的方法来搜索基于一组 3 个元素的列表，每个 struct 包含在其众多成员中：

std::string 名字；
std::string 姓氏；
size_t年龄；

我试图找到一种方法来根据从这三个值派生的键搜索 vector，而不是遍历列表并执行类似以下操作：

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

我正在寻找更快的方法来利用 std::vector 中的底层逻辑来更有效地运行，如果我想通过不同的键元组进行搜索，我只需更改几行代码而不是编写另一个搜索功能。这样的方法可行吗？

Answer 1

您可以使用 std::find_if 并提供一个 lambda 作为谓词。它会更简单、更灵活，但我不确定它是否一定会更快。

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.

或者，您可以使用键元组或结构创建比较运算符

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

并使用 std::find:

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

Live demo.

如果您想要更快的搜索，您可能需要重新考虑存储结构的方式。也许维护索引或保持向量排序，但这可能会影响插入的性能。

Answer 2

首先，为什么要把它放在向量中？我相信 urordered_map 使用散列可能会更好：

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

我认为 ^ 是将两个散列合并为一个的好方法。也许 google 那部分？

如果您坚持使用向量，可以制作一个 smart_ptr 并将其存储在您的向量中，然后使用 smart_ptr 作为值的 unordered_map。

PS: OK xor 是一种蹩脚的散列方法。使用 boost::hash_combine 或 this answer.

C++ - 通过基于元素的自定义键搜索向量

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

search

stdvector