c++ - C++ 中用于并行化的字符串数组

Question

我正在将一个项目从 Python 转移到 C++，但一开始就卡住了，我必须决定应该使用哪种数据结构。我有一个包含数百万个小数据文件的数据库，这些文件的名称类似于 1986_12_04_23_43_34_458239_VpLGMI(数据文件的名称在长度和类型上可能有所不同)。我想将文件名加载到一个数据结构中，然后我可以从中快速搜索文件名中的子字符串。

由于过去几年我主要使用 Python，所以我不确定应该采用哪种方法。在 C++ 中，有许多方法可以将字符串存储在数组中。现在我在数三:

• 字符串类std::string
• vector 类std::vector
• 二维数组

我想二维数组不是一个好的选择，因为它们不是很灵活。如果我以后想要并行化搜索，应该采用哪种方法？

Answer 1

第一个选项应该是std::vector<std::string>感谢parallel algorithm你可以使用平行版本的find查找 O(N) 复杂度:

#include <algorithm>
#include <vector>
#include <execution>
#include <string>

std::vector<std::string> v;
std::string someString = "someName";
v.push_back(someString);
auto res = std::find(std::execution::par, 
 std::begin(v), std::end(v), someString);
// res is an iterator to an element of which
//has someString

您可以通过对 vector 进行排序然后使用 std::lower_bound 来提高复杂度(使用二进制搜索)而不是 std::find .

或者，@jjramsey 建议您可以使用 std::set，它以排序形式存储字符串并具有 O( log N ) 来搜索单个元素或 std::unordered_set复杂度为 O(1)。同样std::map和 std::unordered_map .

不过，在这些容器中，您需要预先支付一些开销用于插入。

请注意，算法的并行版本需要 C++17。 Live