c++ - 如何在C++中获取vector中元素的等级

Question

我需要为 C++ 中的容器获取元素的排名(位置索引 +1)，例如 vector 或 list。有方便的方法吗？我本可以根据 nth_element 进行测试以找到排名。或者我可以排序并进行二进制搜索以找到排名。但在最坏的情况下，所有这些似乎都不是很有效。我想要 O(lgn) 复杂度，并尽可能使用 STL 算法完成。

Answer 1

如果您的容器具有随机访问迭代器(例如 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 语法来保持代码简短，但你应该明白了)。

请注意，您可以按排序方式将元素插入到 vector 中，因此在找到索引之前不需要排序。