Boost Graph Library：以高效的方式检查 vertex_descriptor 的有效性

Question

BGL 旨在尽可能通用。因此，我为另一款软件编写了一个界面，该界面也旨在尽可能通用。但是，当 vertex_descriptor 无效时，我遇到了问题。

这是描述问题的最小示例：

template <class Graph>
class Wrapper {
  public:
    T& get_property_obj(const typename Graph::vertex_descriptor& v) {
        // This should be inserted:
        // if (invalid_descriptor(v)) {
        //    throw something;
        // }
        return g[v];
    }
  private:
    Graph& g;
};

问题是当 Graph 是一个 boost::adjacency_list 且 vecT 作为顶点存储类型时 Graph::operator[ 似乎不检查 v 是否是有效，可以传递无效内存。

我能否以某种方式在包装器 class 中简单检查 v 是否有效？

显然，最简单的解决方案是遍历所有顶点并检查是否相等，但对于给定的示例，检查 vertex_descriptor 和 num_vertices() 就足够了（但当然不是通用的）。

Answer 1

无法判断顶点描述符是否有效。

你只能勾选

范围（在积分顶点描述符的情况下，如 vecS）
通过查找基于节点的顶点存储描述符。

但是，这两种情况都有可能给您错误的结果，原因与标准库容器相同：

 std::vector<int> is{1,2,3};
 auto i1 = is.begin();

 is.push_back(4);

 std::cout << "Undefined Behaviour: " << *i1;

重点是，迭代器（或描述符，视情况而定）已失效。没有办法检测到这种情况发生¹，您总是必须自己处理它。

iterator/descriptor 失效保证遵循底层容器的保证。这意味着对于基于节点的容器，您实际上可以依赖描述符（和引用）在插入甚至删除时保持稳定（除了显然，对于被删除的元素）。

参见例如Iterator invalidation rules

所以对于整数描述符，你会写：

bool descriptor_looks_valid(vertex_descriptor v) const {
    return v>=0 && v < num_vertices(g);
}

如您所知，对于大多数其他容器选择器来说，它的效率非常低：

bool descriptor_looks_valid(vertex_descriptor v) const {
    auto vds = vertices(g);
    return std::count(vds.first, vds.second, v);
}

或者一般（假设 c++17）：

bool descriptor_looks_valid(vertex_descriptor v) const {
    if constexpr(std::is_integral_v<vertex_descriptor>) {
        return v>=0 && v < num_vertices(g);
    } else {
        auto vds = vertices(g);
        return std::count(vds.first, vds.second, v);
    }
}

危险的示范

这个小演示展示了将 "range check pass" 误认为 "valid" 的危险。这个程序重复这个：

template <typename vertexS> void doTest() {
    using Graph = boost::adjacency_list<
        boost::vecS,
        vertexS,
        boost::directedS,
        PropertyObj>;

    Graph g;
    auto v1 = add_vertex({"one"}, g);
    auto v2 = add_vertex({"two"}, g);
    auto v3 = add_vertex({"three"}, g);
    auto v4 = add_vertex({"four"}, g);
    auto v5 = add_vertex({"five"}, g);

    Wrapper w = g;
    std::cout << w.get_property_obj(v3).something << std::endl;

    // but this is confounding, and only accidentally "works" for vecS:
    remove_vertex(v1, g);
    std::cout << w.get_property_obj(v3).something << std::endl;

    try {
        // this looks "valid" with vecS, but should throw for listS
        //
        // of course, like with v3 the descriptor was already invalidated both cases
        std::cout << w.get_property_obj(v1).something << std::endl;
    } catch(std::range_error const& re) {
        std::cout << "(range_error cautgh: " << re.what() << "\n";
    }
}

对于 vertexS 等于 vecS、listS 或 setS。典型的输出是 Live On Coliru:

Testing with vecS:
three
four
two

Testing with listS:
three
three
(range_error caught: get_property_obj

Testing with setS:
three
three
(range_error caught: get_property_obj

结论

未实施有效性检查的原因是底层容器不支持它们。

此外，尽管您可以 "approximate" 进行验证，但这只会防止崩溃，不能防止未指定的行为。

事实上，根据预期的语义，您可能会触发相同的 Undefined Behavior（例如，如果您假设 get_property_obj(v3) 每次都产生相同的值，您将破坏代码 vecS).

Can I somehow do a simple check in the wrapper class that v is valid?

简而言之，no.Descriptor 有效性是使用模式的函数，调用者必须考虑它。

完整列表

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

struct PropertyObj {
    std::string something;
};

template <class Graph, class T = PropertyObj>
class Wrapper {
  public:
    using vertex_descriptor = typename Graph::vertex_descriptor;
    T& get_property_obj(vertex_descriptor v) {
        if (!descriptor_looks_valid(v)) 
            throw std::range_error("get_property_obj");
        return g[v];
    }
    Wrapper(Graph& g) : g(g){}
  private:
    bool descriptor_looks_valid(vertex_descriptor v) const {
        if constexpr(std::is_integral_v<vertex_descriptor>) {
            return v>=0 && v < num_vertices(g);
        } else {
            auto vds = vertices(g);
            return std::count(vds.first, vds.second, v);
        }
    }

    Graph& g;
};

template <typename vertexS> void doTest() {
    using Graph = boost::adjacency_list<
        boost::vecS,
        vertexS,
        boost::directedS,
        PropertyObj>;

    Graph g;
    auto v1 = add_vertex({"one"}, g);
    auto v2 = add_vertex({"two"}, g);
    auto v3 = add_vertex({"three"}, g);
    auto v4 = add_vertex({"four"}, g);
    auto v5 = add_vertex({"five"}, g);

    boost::ignore_unused_variable_warning(v1);
    boost::ignore_unused_variable_warning(v2);
    boost::ignore_unused_variable_warning(v3);
    boost::ignore_unused_variable_warning(v4);
    boost::ignore_unused_variable_warning(v5);

    Wrapper w = g;
    std::cout << w.get_property_obj(v3).something << std::endl;

    // but this is confounding, and only accidentally "works" for vecS:
    remove_vertex(v1, g);
    std::cout << w.get_property_obj(v3).something << std::endl;

    try {
        // this looks "valid" with vecS, but should throw for listS
        //
        // of course, like with v3 the descriptor was already invalidated both cases
        std::cout << w.get_property_obj(v1).something << std::endl;
    } catch(std::range_error const& re) {
        std::cout << "(range_error caught: " << re.what() << "\n";
    }
}

int main() {
    std::cout << "Testing with vecS:\n";
    doTest<boost::vecS>();

    std::cout << "\nTesting with listS:\n";
    doTest<boost::listS>();

    std::cout << "\nTesting with setS:\n";
    doTest<boost::setS>();
}

¹ 虽然某些库实现具有扩展，允许您在某些时候检测到它 - 例如 https://docs.microsoft.com/en-us/cpp/standard-library/debug-iterator-support?view=vs-2019

Boost Graph Library：以高效的方式检查 vertex_descriptor 的有效性

Boost Graph Library: Check validity of vertex_descriptor in a performant way

c++

boost

boost-graph

危险的示范

结论

完整列表