std::unordered_set 与 constexpr std::vector 用于存储不可变数据

Question

不幸的是，即使 C++23 也没有 constexpr 集 :(

我希望存储适量（可能~100）的字符串，代表我的系统中存在的不同配置。我只需要将它们存储在不可变的数据结构中，并只考虑查找。顺序并不重要，我也不会迭代整个结构。

使用 string_view 的 constexpr 向量是否会比 std::unordered_set 更好，即使它的查找可能有点差？或者会有像现在这样更糟糕的查找，字符串会嵌入到二进制文件中吗？

我在网上找不到关于这个问题的太多信息。

Answer 1

an

unordered_set

是一种散列数据结构，具有 O(1) 查找，但需要散列，这对于长字符串来说可能很慢，而使用

std::lower_bound

搜索排序的 vector 的时间复杂度为 O(logn)，并且只有 100 个元素，您会看到 8 次比较的最坏情况，大多数在 1-2 个字符后失败，因此在没有使用真实数据的基准的情况下，很难判断哪个搜索速度更快。

使用不可变数据始终具有的优势是，您可以通过使用排序的 constexpr std::array 在启动时跳过堆分配，如下所示。

#include <string_view>
#include <array>
#include <algorithm>
using namespace std::string_view_literals;

constexpr std::array data = []() {
    std::array arr{"d"sv,"c"sv,"b"sv,"a"sv};
    std::sort(arr.begin(),arr.end());
    return arr;
}();

bool find_element(std::string_view item)
{
    auto iter = std::lower_bound(data.begin(), data.end(), item);
    if (iter == data.end() || *iter != item)
    {
        return false;
    }
    return true;
}

程序只需在启动时将数组从磁盘加载到内存，无需调用

new

，无需额外排序。