c++ - 查找 std::hash_map 与 std::vector 的速度

Question

在下面的代码中，使用std::hash_map. 我假设在std::hash_map查找过程中增加了需要哈希函数的额外步骤，但是哈希函数可以像向量查找一样快吗？

bool isUniqueChars(const string &str){
        if (str.length() > 128){
            return false;
        }
        vector<bool> char_set(128);
        for (int i = 0; i < str.length(); i++){
            int val = str[i];
            if (char_set[val]){
                return false;
            }
            char_set[val] = true;
        }
        return true;
}

标签： c++

Answer 1

与所有与性能相关的问题一样，您应该衡量差异以回答您自己的问题。幸运的是，使用这个简单的代码就足够简单了。

散列数据结构具有摊销常数复杂性，即每次操作的平均时间只有在您执行许多操作时才是常数。所以我预计unordered_set会比vector.

请注意，您也可以使用std::bitset<128>- 它的开销很小，例如vector，并且可能更具描述性 - 它的大小是恒定的，但vector可以调整大小。