c++ - 在 C++ 中，检查一个数字是否已经添加到列表中，而不用暴力搜索该列表

Question

假设我有一个二维矩阵，由 vector<vector<double>> matrix 给出，那matrix已经初始化为R行和 C列。

还有一个坐标列表(由N (x,y) 对组成)，我们要处理，这样对于每个坐标，我们获取矩阵中特定行 (r) 和列 (c) 的映射。所以，我们基本上有 [r, c] = f(x,y) .映射函数的特殊性f并不重要。但是，我们想要做的是跟踪行 r和列 c通过将它们插入到另一个名为 list-of-indicies 的列表中来使用。

问题是，我不想继续添加相同的 r和 c到列表中，如果(r,c)对已存在于该列表中。蛮力方法是每次我想检查时简单地扫描整个索引列表，但这将非常耗时。

例如，如果我们有坐标 (x=4, y=5)，则得到 (r=2, c=6)。因此，我们现在将 (r=2, c=6) 添加到索引列表中。现在我们得到一个新点，由 (x=-2, y=10) 给出。这也最终落在 (r=2, c=6) 之下。但是，由于我已经将 (r=2, c=6) 添加到我的列表中，所以我不想再次添加它!但是，如果不对索引列表进行强力扫描，是否有更好的方法？

Answer 1

你需要一张 map 才能做到这一点。

如果你使用 c++11，你可以使用 unordered_map，它是一个 hashmap 并且有一个恒定的时间查找，如果你使用旧版本的 c++，你可以使用标准映射，它是一个 TreeMap ，并且有一个对数查找。

如果您没有很多项目，性能差异不会很大。