为什么编译器在某些优化级别会警告未初始化的边缘迭代器？

Question

我已尽可能减少可重现的示例。在其中，我循环遍历增强图中的所有边并收到我不理解的警告。请向我解释为什么我收到此警告，也许还有为什么它只出现在某些优化级别中。

/*
 *  reproducing the warning about maybe uninitialized edge iterator
 */
#include <vector>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> traits;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property,
    boost::property<boost::edge_capacity_t, long>> graph;

typedef traits::vertex_descriptor vertex_desc;
typedef traits::edge_descriptor edge_desc;
typedef boost::graph_traits<graph>::edge_iterator edge_iterator;

int main(){
    // build a graph
    graph G(10);
    // get its capacity map
    auto c_map = boost::get(boost::edge_capacity, G);
    // get a handle to the first vertex
    vertex_desc source = boost::vertex(0, G);
    // add an edge, with a capacity of 1
    edge_desc e = boost::add_edge(boost::vertex(0, G), boost::vertex(1, G), G).first;
    c_map[e] = 1;
    // loop over all edges in the graph
    std::pair<edge_iterator, edge_iterator> eip = boost::edges(G);
    for (edge_iterator eit = eip.first; eit != eip.second; eit++){
        edge_desc e = *eit;
        vertex_desc a = boost::source(e, G);
        vertex_desc b = boost::target(e, G);
        bool source_involved = ((a == source) || (b == source));
        std::cout << (source_involved ? "yes" : "no") << std::endl;
    }
}

使用-O0或编译-O1，没有警告：

g++ -std=c++14 -Wall -Wextra -O0 repro.cpp -o repro.exe

编译后-O2我收到此警告：

# g++ -std=c++14 -Wall -Wextra -O2 repro.cpp -o repro.exe
repro.cpp: In function 'int main()':
repro.cpp:28:24: warning: '*((void*)& eit +48)' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for (edge_iterator eit = eip.first; eit != eip.second; eit++){
                        ^~~

并用-O3,编译-O4，-O5我收到类似的警告，但很丑陋：

# g++ -std=c++14 -Wall -Wextra -O3 repro.cpp -o repro.exe
repro.cpp: In function 'int main()':
repro.cpp:28:24: warning: '*((void*)(& eit)+32).__gnu_cxx::__normal_iterator<boost::detail::stored_edge_property<long unsigned int, boost::property<boost::edge_capacity_t, long int> >*, std::vector<boost::detail::stored_edge_property<long unsigned int, boost::property<boost::edge_capacity_t, long int> >, std::allocator<boost::detail::stored_edge_property<long unsigned int, boost::property<boost::edge_capacity_t, long int> > > > >::_M_current' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for (edge_iterator eit = eip.first; eit != eip.second; eit++){

我的g++ --version是

g++ (Ubuntu 8.4.0-1ubuntu1~18.04) 8.4.0

我正在 docker 中运行

# uname -a
Linux 88157d45c773 5.4.0-58-generic #64~18.04.1-Ubuntu SMP Wed Dec 9 17:11:11 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

该警告确实出现在-std=c++11和 中-std=c++14，但-std=c++17似乎没有出现在 中。

这个警告告诉我什么？有什么问题吗？

Answer 1

正如我所评论的，这可能是特定编译器版本的编译器问题，其中内联+死代码省略会导致虚假的未使用变量警告。

我不认为查找是否有与修复相关的错误报告有什么好处。相反，让我向您展示用 c++14 编写代码的更优雅的方法。

无意作为所提出问题的答案。尽管纯属巧合，您遇到的具体警告可能会消失。

我发布答案是出于灵感/教育价值，因为我看到很多严重落后于时代的复制/过去的 BGL。

现场直播

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

using capacity_prop = boost::property<boost::edge_capacity_t, long>;

using graph = boost::adjacency_list<
                    boost::vecS, boost::vecS, boost::directedS,
                    boost::no_property, capacity_prop
                >;

int main() {
    graph G(10);
    auto add = [&G](auto a, auto b, auto c) {
        add_edge(vertex(a, G), vertex(b, G), capacity_prop{c}, G);
    };
    add(0, 1, 1);
    add(1, 2, 2);
    add(1, 3, 3);
    add(1, 7, 4);
    add(1, 8, 5);
    add(2, 5, 6);
    add(5, 3, 7);
    add(5, 0, 8);
    add(7, 0, 9);

    auto const s = vertex(0, G);

    for (auto e : boost::make_iterator_range(edges(G))) {
        auto a = source(e, G);
        auto b = target(e, G);
        std::cout << e << " involves " << s << "? "
            << std::boolalpha << (a == s || b == s) << std::endl;
    }
}

印刷

(0,1) involves 0? true
(1,2) involves 0? false
(1,3) involves 0? false
(1,7) involves 0? false
(1,8) involves 0? false
(2,5) involves 0? false
(5,3) involves 0? false
(5,0) involves 0? true
(7,0) involves 0? true

C++17 奖励

这样初始化代码会更容易写得更自然

for (auto [a,b,c] : { std::tuple
        {0, 1, 1}, {1, 2, 2}, {1, 3, 3},
        {1, 7, 4}, {1, 8, 5}, {2, 5, 6},
        {5, 3, 7}, {5, 0, 8}, {7, 0, 9}, })
{
    add_edge(vertex(a, G), vertex(b, G), capacity_prop{c}, G);
}

逻辑奖励

如果你真的只想找到涉及 vertex 的边集s，你可以这样写，可能会更有效：

现场直播

auto const s = vertex(2, G); // different example
auto [f,l] = out_edges(s, G);
edge_set involved(f, l);

for (auto e : make_iterator_range(edges(G)))
    if (target(e, G) == s)
        involved.insert(e);

for (auto e : involved)
    std::cout << e << " ";

印刷

(1,2) (2,5) 

正如人们所预料的那样。

性能提示

如果您可以调整图模型，则通过更改它以维护 adjacency_list 的双向边可以获得更好的性能：

std::set<graph::edge_descriptor> involved;

auto insert = [&](auto range) { involved.insert(range.first, range.second); };
insert(out_edges(s, G));
insert(in_edges(s, G));

或者，实际上，立即打印它们：

for (auto e : make_iterator_range(out_edges(s, G)))
    std::cout << e << " ";
for (auto e : make_iterator_range(in_edges(s, G)))
    std::cout << e << " ";

观看现场 Ob Wandbox

打印相同。

这是否会提高应用程序的性能主要取决于图表上是否有更多突变或更多查询。

聚苯乙烯

这是我为示例制作的图表以供参考

这是做的结果

boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, G));
dp.property("label", get(boost::edge_capacity, G));
write_graphviz_dp(std::cout, G, dp);

并使用dot（例如在线）