如何在C++中获得向量中元素的等级

Question

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

Answer 1

如果您的容器具有随机访问迭代器（例如向量）并且已排序，您可以使用该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 语法来保持代码简短，但您应该明白这个想法）。

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

Answer 2

您似乎不太可能在这里找到比线性搜索更有效的东西。最坏的情况必然是您将所有元素与您搜索的内容进行比较 - 这正是线性搜索给您的结果。