如何在C++中获取向量中元素的排名

Question

如何在C++中获取向量中元素的排名

5

我需要在C++中获取像vector或list这样的容器中元素的排名(即位置索引+1)。有没有一种方便的方法来实现？我可以通过nth_element进行基于测试来找到排名，或者排序并进行二分查找来寻找排名。但是这些方法在最坏情况下似乎都不是很高效。如果可能的话，我希望能够使用STL算法实现O(lgn)复杂度。

- Qiang Li

如果你希望比扫描容器更好，那么你选择了错误的容器。至少，并没有一种“万能”的方法可以为每种容器类型提供最佳效果。 - Lightness Races in Orbit

1

@EdS.：“问题是什么方法？” “答案是使用该方法。” 嗯。 - Lightness Races in Orbit

@LightnessRacesinOrbit：请读完第一句话。此外，即使是最简单的STL操作，使用谷歌也很困难，对吧？ - Ed S.

如果您需要在容器中以比“O(n)”更好的时间复杂度获取C++元素的排名，那么您应该使用std::set而不是std::vector或std::list。 - penelope

1

除非您已经对容器进行了排序或以其他方式施加了某种结构，否则不可能实现。草图证明：假设所需元素可以出现在任何位置，并且检查不是所需元素的元素对于目标位置没有任何帮助。然后，无论您以什么顺序检查元素，都会有输入使得目标是您查找的第n个位置。因此，在最坏情况下，性能为Omega(n)。 - Steve Jessop

显示剩余3条评论

3个回答

2

在这里，你很难找到比线性搜索更有效的方法。最坏情况必须是您将所有元素与您要搜索的内容进行比较 - 这正是线性搜索所提供的。

- Johan Kotlinski

0

这可能有点凌乱。

你可以利用向量中的元素在内存中是连续的这一事实。

所以你需要做的是：

1）获取感兴趣元素的迭代器地址

2）用vector.begin()减去它以获得总内存

3）除以一个元素的大小

这应该给你位置（或等级）。

这是假设元素是固定大小的情况下。

- Angel Koh

（a）在帖子中并没有暗示OP已经有一个已存储在向量中的实例，因此这个假设可能不成立。（b）如果他们确实有，他们可以直接相减两个迭代器；通过在上面添加指针层次结构，会增加额外的复杂性和容易出错，并且对于不需要在内存中连续的容器也适用（尽管最好使用std::distance()而不是相减）。 - underscore_d

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- drrlvn · Accepted Answer

如果你的容器有随机访问迭代器(例如vector)且已排序，可以使用std::lower_bound()算法在O(log n)复杂度内获取元素的索引。例如：

std::vector<int> v({10,20,30,30,20,10,10,20});
std::sort(v.begin(), v.end());
auto iter = std::lower_bound(v.begin(), v.end(), 20);
std::cout << "index " << int(iter - v.begin()) << std::endl;

我使用C++11语法使代码更短，但是您应该能够理解。

请注意，您可以以排序的方式向向量中插入元素，因此在查找索引之前无需先进行排序。