无法将迭代器元素插入到std::list的std::set中

Question

在展示给我编译器错误的代码之前，我想简要解释一下为什么我需要一个指向列表的迭代器，只是为了避免出现"你真的需要这个吗?"或者可能将它们转换为评论"您的代码可以通过这种方式解决...然而，我应该像这样处理原始问题"。因此，您可以跳过阅读并直接转到最后一节("未编译代码")。 背景原因 我构建了一个有向二分加权图。每个弧都存储在一个结构体中。

typedef struct edge_ {
    int src;
    int des;
    double w; //weight of the arc
}edge;

我使用这样的结构体列表来存储有关图形的信息。

list<edge> all_edges;

接下来，我按权重对弧进行排序，并循环处理它们，从最轻到最重。由于我想要在循环中从all_edges中删除一些元素，在每个循环步骤的开始处调用：

list<edge>::iterator smallest = all_edges.begin();

在循环的每一步中，在完成对弧的权重进行一些操作后，我希望从图中删除所有起点为src或终点为des的节点。为此，在构建图时，我创建了两个向量，一个为二分图的每个组件，以其元素为索引，并且在每个向量的每个位置上，存储了all_edges的边迭代器列表，这些边迭代器是从相应向量位置对应的节点出发的。下面是代码（“small”和“big”是我用来标识二分图两个部分的方式）。

vector<list<list<edge>::iterator>> edges_from_small(small.size());
vector<list<list<edge>::iterator>> edges_from_big(big.size());

这是我用来填充上述向量的代码：

//inside a loop...
    edge e;
    e.src = ...
    e.des = ...
    e.w = ...
    all_edges.push_back(e);                
    edges_from_small[e.src].push_back(--(all_edges.end()));
    edges_from_big[e.des].push_back(--(all_edges.end()));

假设我想删除边缘e。 我会尝试循环所有edges_from_small [e.src]的元素，并为每个元素调用all_edges.erase(iterator)，但是这样做，由于一条边可以列在edges_from_small和edges_from_big中，因此我最终会尝试使用已解引用的迭代器删除一个元素！

使用set就是一个解决方案！ 我只需要创建一个list<edge>::iterator的集合，并用edges_from_small [e.src]和edges_from_big [e.des]的元素填充它，然后，由于重复项被删除，从列表all_edges中删除所有元素。

但是我的代码无法编译，给我一个错误，我无法理解，在以下某一行：

set<list<edge>::iterator> to_remove;

for (auto it = edges_from_small[smallest->src].begin(); it != edges_from_small[smallest->src].end(); ++it) {
        to_remove.insert(*it); //error here! 
    }
for (auto it = edges_from_big[smallest->des].begin(); it != edges_from_big[smallest->des].end(); ++it) {
        //to_remove.insert(*it); //error here!
    }
for (auto it = to_remove.begin(); it != to_remove.end(); ++it) {
        all_edges.erase(*it);
    } 

编译器给我输出了很多内容（都是针对上一行的），目前我只放了第一行和最后一行，我认为这两行最具指示性。

g++ -ggdb3 -g -O0 -std=c++14 -Wall -Werror -o compare main.cpp peaks.cpp common.cpp compare.cpp parameters.cpp 
In file included from compare.cpp:1:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iostream:38:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/ios:216:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__locale:15:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/string:439:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:628:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:606:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iterator:344:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__functional_base:63:21: error: 
      invalid operands to binary expression ('const std::__1::__list_iterator<_edge,
      void *>' and 'const std::__1::__list_iterator<_edge, void *>')
        {return __x < __y;}
                ~~~ ^ ~~~
....................MUCH MORE OUTPUT....................
compare.cpp:226:23: note: in instantiation of member function
      'std::__1::set<std::__1::__list_iterator<_edge, void *>,
      std::__1::less<std::__1::__list_iterator<_edge, void *> >,
      std::__1::allocator<std::__1::__list_iterator<_edge, void *> > >::insert'
      requested here
            to_remove.insert(*it);
                      ^
1 error generated.
make: *** [compare] Error 1

Compilation exited abnormally with code 2 at Tue Sep  5 17:34:39

有没有关于那行代码有什么问题的想法？

不能编译的代码

typedef struct _edge {
    int src;
    int des;
    double w; //weight of the arch
}edge;

list<edge> all_edges;
vector<list<const list<edge>::iterator>> edges_from_small(small.size());
vector<list<const list<edge>::iterator>> edges_from_big(big.size());

//graph construction    
//for loop ...
    edge e;
    e.src = ...
    e.des = ...
    e.w = ... 
    all_edges.push_back(e);
    edges_from_small[e.src].push_back(--(all_edges.end())); 
    edges_from_big[e.des].push_back(--(all_edges.end()));
//end of loop

list<edge>::iterator smallest = all_edges.begin();
set<list<edge>::iterator> to_remove;
for (auto it = edges_from_small[smallest->src].begin(); 
     it != edges_from_small[smallest->src].end(); ++it) {
    to_remove.insert(*it); //<--- COMPILER ERROR HERE, you can see the error description in the last lines of the previous paragraph
}    

- Nisba

---

一个 std::set 要求元素有序，默认使用 < 进行排序。你如何定义这些迭代器的有意义顺序？如果你有一个好的答案，创建该函数并将其作为第二个模板参数提供给 set。 - BoBTFish

@BoBTFish 嗯！可以给出一个合理的顺序，将数字 it->src*size_of_big + it->des 与 它 相关联。 - Nisba

Answer 1

std::list::iterator不能排序，因为没有函数或运算符可以比较它们（相对于less/greater）。

请改用std::unordered_set，它不需要对元素进行排序，而是使用元素的哈希值将它们放入桶中。您可能需要提供一个哈希函数，只需在namespace std中放置一个std::hash的重载即可供std::unordered_set查找和使用。
此外，请注意std::unordered_set的平均插入时间复杂度是常数时间复杂度，而std::set的时间复杂度为对数时间复杂度。

- alain

Answer 2

你面临的问题是，std::set要求元素实现operator<(a,b)（或者在你不指定比较器的情况下使用std::less）。现在，std::list的迭代器是BidirectionalIterator，它缺少上述运算符。

- orhtej2

Answer 3

已经有的回答关于你遇到问题的原因是正确的，但你可能希望考虑boost::bimap，看看它是否适合你的问题（如果没有看到你编写的完整代码，很难理解你正在进行的算法）。

- NoSenseEtAl