c++ - 如何使成对 vector 像哈希表一样工作？

Question

我正在为一个类(class)项目开发 1 位双峰分支预测模拟器。我在考虑对表使用 unordered_map，但我需要能够设置大小，所以我在考虑使用成对的 vector ，而 table.reserve(tableSize) 可能是执行此操作的好方法。

但是，这让我只能对 vector 进行线性搜索来查找表条目，这非常慢。有谁知道我可以为此应用程序实现哈希函数的方法吗？

对于那些不知道分支预测表如何工作的人来说，关键是 PC 地址 0x12345678，值是 T 或 NT(分支采用或不采用)。我还需要一种解决冲突的方法。如果采用分支，则该位 (bool) 设置为 true，这将是下一个分支的预测。如果不采用下一个分支，则该位设置为假或 0。模拟器的目的是测量正确预测与总分支以获得准确性并将其与其他方法的准确性进行比较。因此，最终目标是使用 PC 的 2 个最低有效字节(通过将它们屏蔽掉)来定义哈希表中存储预测值 0 或 1 的位置。

如有任何帮助，我们将不胜感激。

旁注:最大表大小为 1024 个条目，因此时间复杂度没有机会真正扩展到那么高，但任何优化都是值得的，因为我将参加比赛。

---

编辑:

决定使用 unordered_map。

这是我目前得到的解决方案:

头文件

// bimodal 1-bit
class BM1Pred{
    private:
            std::ofstream &outputFile;
            //hash table with bool value mapped to addresses
            // 0 - NOT TAKEN, 1- TAKEN
            unordered_map<long long, bool> table;
            int tableSize;
    public:

            // constructor
            BM1Pred(std::ofstream& file, int size)
            : outputFile(file), tableSize(size) {}

            // deconstructor
            ~BM1Pred()
            {}

            // member functions
            void parseResults(std::string filename);

};

Answer 1

您仍然可以使用 std::unordered_map。如果您想保留特定尺寸，可以使用 std::unordered_map::reserve .

但我不明白为什么 std::map 不是一个选项。它的大小是动态变化的。为什么需要“设置它的大小”？

要回答您的其他问题，在这两种情况下 map[key] 都会返回对映射到等效于 key 的键的值的引用，如果此类 key 尚不存在。所以你通过

插入或更新一个项目

map[key] = value;

在这种情况下，如果 key 已经存在于容器中，则为 key 存储的值将更新为 value；否则，执行插入。您不需要自己检查任何东西。