std::set<Key、比较器、Allocator>

Question

最近，我尝试使用set在trie中保留一些配置。

例如，我在比较器上发现了一个疑问：

    #include <iostream>
    #include <set>

    using namespace std;

    struct Node{
      int position;
      int reference;
      Node(int r, int p){
        this->position = p;
        this->reference = r;
      }
    };

    struct Node_c{
      const bool operator()(const Node& n1, const Node& n2){
        // return n1.reference != n2.reference;
        // i've tried some functions here, like n1.reference != n2.reference ? true : n1.position < n2.position;  
      }
    };


    int main(){
      set<Node, Node_c> aNodes;

      aNodes.emplace(1,1);
      aNodes.emplace(1, 2); // i dont want to add this one, the reference already exists and the position is bigger than the last one
      aNodes.emplace(1, 0); // i want to replace the (1,1) for this one


      for(auto nd : aNodes){
        cout << nd.reference << ' ' << nd.position << '\n';
      }
    }

我如何才能保持位置较小的节点的顺序，但排除等号引用？

谢谢。

Answer 1

这不能用std::set的单个方法来完成，因为它严格要求其元素具有唯一的键！

set.emplace要么插入一个元素，要么不插入，但它不会替换现有的元素，请参见the documentation

对于您来说，最好的解决方案可能是使用std::map<int, int>，其中position映射到reference，如果值变小，则更新值；或者继续使用std::set，然后编写一个自定义方法，该方法首先检查集合是否包含元素，如果包含，则仅在新的reference更小时才替换它

此外，您的比较器应该比较小于(<)，而不是不平等(!=)

Answer 2

#include <iostream>
#include <set>

struct Node {
    int position;
    int reference;

    Node(int r, int p)
            : position(p), reference(r) {
    }
};


struct NodeSet {
    struct AscendingReference {
        bool operator()(const Node &n1, const Node &n2) const {
            return n1.reference < n2.reference;
        }
    };

    struct SmallerPosition {
        bool operator()(const Node &n1, const Node &n2) const {
            return n1.position < n2.position;
        }
    };

    using Storage = std::set<Node, AscendingReference>;

    auto &propose(Node n) {
        auto ifind = storage_.find(n);
        if (ifind != std::end(storage_)) {
            if (not SmallerPosition()(n, *ifind))
                return *ifind;
            storage_.erase(ifind);
        }
        return *(storage_.insert(std::move(n)).first);
    }

    auto begin() const { return storage_.begin(); }

    auto end() const { return storage_.end(); }

private:
    Storage storage_;
};


int main() {
    NodeSet aNodes;

    aNodes.propose(Node(1, 1));
    aNodes.propose(Node(1, 2));
    aNodes.propose(Node(1, 0));

    for (auto nd : aNodes) {
        std::cout << nd.reference << ' ' << nd.position << '\n';
    }
}