std::set<Key, Comparator, 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';
    }
}

std::set<Key, Comparator, Allocator>

std::set<Key, Comparator, Allocator>

c++

set

stdset