c++ - C++ - 排序后的 std::vector 中的元素索引

Question

我有一个std::vector我知道是排序的。使用std::binary_search我可以在日志时间内找到一个元素是否在向量中。不幸std::binary_search的是，在成功的情况下不会返回向量中元素的索引（或者如果成功，我不知道如何访问它）。std::find会给我一个元素的迭代器，但它没有使用向量已排序的事实，因此它以线性时间而不是日志时间运行。我知道我可以轻松实现自己的二进制搜索算法，但我想知道标准中是否有办法做到这一点。

Answer 1

您可以将std::lower_bound(O(log(N)) 和std::distance(O(1) 用于随机访问迭代器)：

auto lower = std::lower_bound(v.begin(), v.end(), val);
// check that value has been found
const bool found = lower != v.end() && *lower == val;

那么，要么

auto idx = std::distance(v.begin(), lower);

或简单的算术：

auto idx = lower - v.begin();

Answer 2

您想使用 lower_bound() 函数。让它普遍有用有点时髦，但可以达到你想要的目的。

Answer 3

使用equal_range，不使用lower_bound。

不能简单地检查返回的迭代器std::lower_bound是否与末尾不同就知道元素是否在集合中。如果元素不存在，则std::lower_bound返回它应该在的位置，而不是集合的结尾。

请参阅：https ://www.fluentcpp.com/2017/01/16/how-to-stdfind-something-efficiently-with-the-stl/

Answer 4

调整std::binary_search你可以得到：

template<typename Iter, typename T>
Iter my_find(Iter begin, Iter end, T value)
{

    Iter i = std::lower_bound(begin, end, value);

    if (i != end && *i == value)
        return i; // found in container
    else
        return end; // not found
}

auto it = my_find(v.begin(), v.end(), val); //it is your iterator

Answer 5

您可以在 STL c++ 中使用 lower_bound 尝试这样的事情：

// 让向量为 v

int func(){
     int position = lower_bound(v.begin(),v.end(),element_to_be_searched) - v.begin();
     if(position == v.size()) // element not found
     {
         return -1;
     }
     else{
          return position;
     }
}