C++ 最快的字符串小写和查找

Question

我有一个通过 ifstream 从文件加载的字符串 vector ，它不需要是一个 vector ，但它看起来像这样:

std::vector<std::string> data;
data.push_back("CONSISTENTTEXT:variabletext1");
data.push_back("CONSISTENTTEXT:variabletext2");
// 100,000 + more push_back's

因为它是一个大 vector ，我需要循环查找搜索字符串的所有引用我想知道如何进行最有效的不区分大小写的字符串查找，因为我可以忽略字符串的前 15 个字符？

Answer 1

首先要尝试的是显而易见的:

std::copy_if(data.begin(), data.end(), output,
    [&searchForMe](std::string const& str) {
        return caseInsensitiveEquals(
            std::string_view{str}.remove_prefix(15),
            std::string_view{searchForMe}.remove_prefix(15));
    });

^{参见 std::copy_if 和 std::string_view::remove_prefix}

您还可能只想在将前缀添加到 data 之前删除前缀.这将显着减少您的内存使用量，并可能使您的字符串适合小字符串优化大小。搜索将非常容易:

std::copy_if(data.begin(), data.end(), output,
    [&searchForMe](std::string const& str) { // maybe `std::string_view str`
        return caseInsensitiveEquals(str, searchForMe);
    });

如果这不够快(很可能它不够快，因为你的 vector 很大)，有一些选择。你总能找到 Execution Policies ，但它们无助于减少需要完成的工作量。

接下来我要考虑的是 std::equal_range ，这将需要对数据进行排序:

// assuming you removed all the prefixes
std::sort(data.begin(), data.end(), caseInsensitiveLessThan);
auto rangePair = std::equal_range(data.begin(), data.end(), searchForMe, caseInsensitiveLessThan);

O(n log n)之后排序，查找是O(log n) .

如果这仍然不够快，或者您可能无法支付排序费用，则您需要专门的数据结构。你也许可以逃脱 std::unordered_multiset<std::string, CaseInsensitiveHash, CaseInsensitiveEquals> .