在C++中,检查一个数字是否已经添加到列表中,而不是强力搜索该列表

Question

让我们说我有一个2D矩阵,由下面给出vector<vector<double>> matrix,并且matrix已经初始化为具有R行和C列.

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

问题是,我不想继续增加同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

你需要一张地图才能做到这一点.

如果你使用c ++ 11,你可以使用unordered_map这是一个hashmap并且有一个恒定的时间查找,如果你使用旧版本的c ++,你可以使用标准的map,它是一个树形图,并具有对数查找.

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