C++ 在 <int, pair> 的向量中查找
C++ Find in a vector of <int, pair>
所以之前我只需要查找 1 个键，所以我可以使用地图：
std::map <int, double> freqMap;
但现在我需要查找 2 个不同的键。我正在考虑使用带有 std::pair 的向量，即：
std::vector <int, std::pair<int, double>> freqMap;
最终我需要查找这两个键以找到正确的值。有没有更好的方法来做到这一点，或者这是否足够有效（将有 ~3k 条目）。另外，不确定如何使用第二个键（std::pair 中的第一个键）进行搜索。是否可以根据第一个密钥找到该对？基本上我可以通过以下方式访问第一个密钥：
freqMap[key1]
但不确定如何迭代并找到密钥对中的第二个密钥。
编辑：确定添加用例以进行说明：
我需要根据 2 个键、一个多路复用器选择和一个频率选择查找一个 val。原始数据看起来像这样：
Mux, Freq, Val
0, 1000, 1.1
0, 2000, 2.7
0, 10e9, 1,7
1, 1000, 2.2
1, 2500, 0.8
6, 2000, 2.2
对“哪个更快”的笼统回答通常是“您必须对其进行基准测试”。
但除此之外，您还有很多选择。 A std::map 在纸面上比其他数据结构更高效，但在实践中不一定。如果您确实处于性能关键（即避免过早优化）的情况下，请尝试不同的方法，如下所示，并测量您获得的性能（memory-wise 和 cpu-wise）。
与其使用 std::map，不如考虑将数据放入 struct，为其赋予适当的名称并将所有值存储在简单的 std::vector. If you modify the data only seldom, you can optimise retrieval cost at the expense of additional insertion cost by sorting the vector according to the key you are typically using to find an entry. This will allow you to do binary search, which can be much faster than linear search.
中
但是，由于 cache locality and branch prediction，线性搜索在 std::vector 上可以出奇地快。在处理地图、unordered_map 或（二进制搜索）排序向量时，您可能会丢失这两者。因此，尽管 O(n) 听起来比 map 的 O(log n) 甚至 unordered_map 的 O(1) 更可怕，但它可以 still 更快在合适的条件下。
特别是如果您发现您没有可用于对条目进行排序的可识别索引成员，您将不得不坚持在连续内存（即向量）中进行线性搜索或 投资于双重索引数据结构（实际上类似于两个地图或两个 unordered_maps）。拥有两个索引通常会阻止您使用单个 map/unordered_map.
如果您可以更紧密地打包数据（即您需要 int 还是 std::uint8_t 来完成这项工作？您需要 double 吗？等等）您将放大缓存局部性，并且对于只有 3k 个条目，您很有可能使未排序的向量表现最佳。尽管对 std::size_t 的操作本身通常比对较小类型的操作更快，但迭代连续内存通常会抵消这种影响。
结论：尝试一个未排序的向量、一个排序的向量（+二进制搜索）、一个映射和一个 unordered_map。进行适当的基准测试（重复几次）并选择最快的一个。如果没有区别，请选择最 straight-forward 理解的那个。
编辑：根据您的示例数据，听起来第一个键的域非常小。据我所知，“Mux”似乎仅限于少数彼此接近的不同值，在这种情况下，您可以考虑使用 std::array 作为您的主要索引结构并进行合适的查找结构作为你的第二个。例如：
std::array<std::vector<std::pair<std::uint64_t,double>>,10>
std::array<std::unordered_map<std::uint64_t,double>,10>
所以之前我只需要查找 1 个键，所以我可以使用地图：
std::map <int, double> freqMap;
但现在我需要查找 2 个不同的键。我正在考虑使用带有 std::pair 的向量，即：
std::vector <int, std::pair<int, double>> freqMap;
最终我需要查找这两个键以找到正确的值。有没有更好的方法来做到这一点，或者这是否足够有效（将有 ~3k 条目）。另外，不确定如何使用第二个键（std::pair 中的第一个键）进行搜索。是否可以根据第一个密钥找到该对？基本上我可以通过以下方式访问第一个密钥：
freqMap[key1]
但不确定如何迭代并找到密钥对中的第二个密钥。
编辑：确定添加用例以进行说明：
我需要根据 2 个键、一个多路复用器选择和一个频率选择查找一个 val。原始数据看起来像这样：
Mux, Freq, Val
0, 1000, 1.1
0, 2000, 2.7
0, 10e9, 1,7
1, 1000, 2.2
1, 2500, 0.8
6, 2000, 2.2
对“哪个更快”的笼统回答通常是“您必须对其进行基准测试”。
但除此之外，您还有很多选择。 A std::map 在纸面上比其他数据结构更高效，但在实践中不一定。如果您确实处于性能关键（即避免过早优化）的情况下，请尝试不同的方法，如下所示，并测量您获得的性能（memory-wise 和 cpu-wise）。
与其使用 std::map，不如考虑将数据放入 struct，为其赋予适当的名称并将所有值存储在简单的 std::vector. If you modify the data only seldom, you can optimise retrieval cost at the expense of additional insertion cost by sorting the vector according to the key you are typically using to find an entry. This will allow you to do binary search, which can be much faster than linear search.
但是，由于 cache locality and branch prediction，线性搜索在 std::vector 上可以出奇地快。在处理地图、unordered_map 或（二进制搜索）排序向量时，您可能会丢失这两者。因此，尽管 O(n) 听起来比 map 的 O(log n) 甚至 unordered_map 的 O(1) 更可怕，但它可以 still 更快在合适的条件下。
特别是如果您发现您没有可用于对条目进行排序的可识别索引成员，您将不得不坚持在连续内存（即向量）中进行线性搜索或 投资于双重索引数据结构（实际上类似于两个地图或两个 unordered_maps）。拥有两个索引通常会阻止您使用单个 map/unordered_map.
如果您可以更紧密地打包数据（即您需要 int 还是 std::uint8_t 来完成这项工作？您需要 double 吗？等等）您将放大缓存局部性，并且对于只有 3k 个条目，您很有可能使未排序的向量表现最佳。尽管对 std::size_t 的操作本身通常比对较小类型的操作更快，但迭代连续内存通常会抵消这种影响。
结论：尝试一个未排序的向量、一个排序的向量（+二进制搜索）、一个映射和一个 unordered_map。进行适当的基准测试（重复几次）并选择最快的一个。如果没有区别，请选择最 straight-forward 理解的那个。
编辑：根据您的示例数据，听起来第一个键的域非常小。据我所知，“Mux”似乎仅限于少数彼此接近的不同值，在这种情况下，您可以考虑使用 std::array 作为您的主要索引结构并进行合适的查找结构作为你的第二个。例如：
std::array<std::vector<std::pair<std::uint64_t,double>>,10>
std::array<std::unordered_map<std::uint64_t,double>,10>