c++ - 检查指针是否指向 vector 元素

Question

我想要一个函数来检查指针是否指向 vector 的元素:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr);

该函数是一个辅助函数，用于从指针安全地创建迭代器:

template <typename T>
std::vector<T>::iterator toIterator(std::vector<T>& vec, T* ptr)
{
    assert(pointsToElement(vec, ptr));
    return vec.begin() + (ptr - &vec[0]);
}

“明显”的方式是这样的:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr)
{
    if (vec.empty())
        return false;
    return ptr >= &vec.front() && ptr <= &vec.back();
}

不幸的是，这似乎会调用未定义的行为，因为它可能会比较指向不同对象的指针。

一个安全的方法是:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr)
{
    for (auto& elem : vec) {
        if (&elem == ptr)
            return true;
    }
    return false;
}

但这当然是 O(N)，所以非常不可取。

我可以想象另一种方式:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr)
{
    if (vec.empty())
        return false;
    intptr_t pos   = reinterpret_cast<intptr_t>(ptr);
    intptr_t begin = reinterpret_cast<intptr_t>(&vec.front());
    intptr_t end   = reinterpret_cast<intptr_t>(&vec.back());
    return pos >= begin && pos <= end;
}

我认为该标准不能保证 inptr_t 上的任何顺序，但这至少应该不会调用任何未定义的行为并在主要平台上产生正确的结果(我目前只关心 Linux 和 Windows)。

这个分析正确吗？有没有更好的方法来检查指针是否落在某个范围内？

(注意:有一些类似的问题，但没有一个考虑使用转换为 intptr_t 的可能性)。

Answer 1

这是 std::less 的情况之一和 std::greater派上用场了。

A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not. The strict total order is consistent among specializations of std::less, std::greater, std::less_equal, and std::greater_equal for that pointer type, and is also consistent with the partial order imposed by the corresponding built-in operators (<, >, <= and >=).

有了这些保证，您就可以使用“明显”的解决方案。

---

DavisHerring 在评论中指出，可以存在具有分段内存布局的架构，其中不相关的指针可以在两个 vector 元素之间排序，并且仍然符合严格的总顺序。