使用比较器对具有不同唯一性和小于的标准的一组唯一对进行排序

Question

首先，我尝试搜索类似的问题，但没有找到任何可以解释我的问题的回复。

问题如下：给定一组坐标为 (x,y,z) 的 N 个节点，尽可能快地使用第 4 个值 F 对它们进行排序。

我想为此目的使用带有自定义比较器的 std::set，因为它具有 O(log(N)) 复杂度。我知道我也可以尝试 std::vector 并在 std::vector 上调用 std::sort 但理论上操作速度较慢。

这是为什么？因为我经常在集合中插入元素，更改 F 值（这意味着我更改值并重新排序容器中的元素，我擦除并重新插入它）并且我想取F值小的元素（也就是容器最前面的元素）

但是让我们来解决 std::set 问题。

坐标定义了唯一性属性，遵循严格的弱排序规则，即a和b被认为是同一个对象，如果

!comp(a,b) && !comp(b,a)

问题与定义基于坐标的唯一性标准和基于 F 值的排序标准有关。我不希望集合存储具有相同坐标的两个元素，但我希望它允许存储具有不同坐标但相同 F 值的两个元素

比较器还应满足以下三个属性：

非自反性 x < x false
不对称 x < y true 意味着 y < x false
传递性 x < y && y < z 意味着 x < z true

了解所有这些属性后，我一直在使用以下示例实现：

一些定义

class Node;
struct NodeComparator;
using NodePair = std::pair<Node *, int>;
using NodeSet  = std::set<NodePair, NodeComparator>;

这里为了方便我使用指针

Class节点

class Node
{

public:
    Node()
    {
    }
    Node(int _x, int _y, int _z, int _val) : x(_x), y(_y), z(_z), value(_val)
    {
    }

    int x, y, z;
    int value;

    friend inline std::ostream &operator<<(std::ostream &os, const Node &dt)
    {
        os << "[" << dt.x << ", " << dt.y << ", " << dt.z << "], [" << dt.value << "]";
        return os;
    }
    friend bool operator==(const Node &_lhs, const Node &_rhs){
        if( _lhs.x == _rhs.x &&
            _lhs.y == _rhs.y &&
            _lhs.z == _rhs.z ){
                return true;
            }
        return false;
    }
};

此处运算符 << 重载仅用于调试目的

比较器


struct NodeComparator
{
    bool operator()(const NodePair &_lhs, const NodePair &_rhs) const
    {
        if( _lhs.first == nullptr || _rhs.first == nullptr )
            return false;
        /*
        This first check implements uniqueness. 
        If _lhs == _rhs --> comp(_lhs,_rhs) == false && comp(_rhs, _lhs) == false
        So ( !comp(l,r) && !comp(r,l) ) == true
        */
        if( *_lhs.first == *_rhs.first) 
            return false;
        
        int ret = _lhs.second - _rhs.second;
        return ret < 0;
    }
};

我想一个问题可能是两个坐标不同但F值相同的节点

具体案例的完整示例

Ì在这个例子中，我使用上面的类到 insert/find/erase 一些元素，但是它显示在输出中，它没有按预期运行：

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <tuple>

class Node;
struct NodeComparator;
using NodePair = std::pair<Node *, int>;
using NodeSet  = std::set<NodePair, NodeComparator>;
class Node
{

public:
    Node()
    {
    }
    Node(int _x, int _y, int _z, int _val) : x(_x), y(_y), z(_z), value(_val)
    {
    }

    int x, y, z;
    int value;

    friend inline std::ostream &operator<<(std::ostream &os, const Node &dt)
    {
        os << "[" << dt.x << ", " << dt.y << ", " << dt.z << "], [" << dt.value << "]";
        return os;
    }
};

struct NodeComparator
{
    bool operator()(const NodePair &_lhs, const NodePair &_rhs) const
    {
        /*
        This first check implements uniqueness. 
        If _lhs == _rhs --> comp(_lhs,_rhs) == false && comp(_rhs, _lhs) == false
        So ( !comp(l,r) && !comp(r,l) ) == true
        */
        if(_lhs == _rhs) 
            return false;
        
        int ret = _lhs.second - _rhs.second;
        return ret < 0;
    }
};
int main(int argc, char **argv)
{
    Node n1(0, 2, 4, 12), 
         n2(2, 4, 5, 25), 
         n3(0, 1, 4, 34), 
         n4(0, 1, 4, 20), 
         n5(0, 1, 5, 20),
         n6(0, 2, 4, 112);

    NodeSet set;

    set.insert({&n1, n1.value});
    set.insert({&n2, n2.value});
    set.insert({&n3, n3.value});
    set.insert({&n4, n4.value}); //Should not be inserted because it already exists n3 with same coords
    set.insert({&n5, n5.value});

    //Try to insert multiple times a previously inserted node (n1 coords is == n6 coords)
    //It should not be inserted because it already exists one node with the same coords (n1)
    set.insert({&n6, n6.value});
    set.insert({&n6, n6.value});
    set.insert({&n6, n6.value});
    set.insert({&n6, n6.value});
    set.insert({&n6, 0});
    set.insert({&n6, 1});

    if (set.find({&n4, n4.value}) != set.end())
        std::cout << "Found n4" << std::endl;
    
    auto it = set.erase({&n4, 20});
    std::cout << "It value (elements erased): " << it << std::endl;

    if (set.find({&n4, n4.value}) != set.end())
        std::cout << "Found n4 after removal" << std::endl;
    
    std::cout << "Final Set content: " << std::endl;
    for (auto &it : set)
        std::cout << *it.first << std::endl;


    return 0;
}

用C++11或以上编译：g++ -o main main.cpp

输出：

Found n4
It value (elements erased): 1
Final Set content: 
[0, 2, 4], [12]
[2, 4, 5], [25]
[0, 1, 4], [34]
[0, 2, 4], [112]

**预期输出：**对应元素n1,n5,n2,n3从小F(n1)到大F(n3)的顺序。

Final Set content: 
[0, 2, 4], [12]
[0, 1, 5], [20]
[2, 4, 5], [25]
[0, 1, 4], [34]

如果有任何帮助或想法以及实施的替代方案，我将不胜感激。谢谢

Answer 1

很遗憾，您的要求不能仅靠一个 std::set 来满足。 std::set 使用相同的比较器进行排序和唯一性。比较器没有状态，这意味着，您不能将一次与第一次比较，而下一次与第二个条件进行比较。那是行不通的。

因此，您需要使用 2 个容器，例如第一个 std::unordered_set 使用比较器进行相等坐标，第二个容器用于排序，例如 std::multiset..

您还可以将 std::unordered_map 与 std::multiset 结合使用。

或者您创建自己的容器作为 class 并尝试优化性能。

让我向您展示一个使用 std::unordered_set 和 std::multiset 组合的示例。它会很快，因为 std::unordered_set 使用哈希。

#include <iostream>
#include <unordered_set>
#include <set>
#include <array>
#include <vector>

using Coordinate = std::array<int, 3>;

struct Node {
    Coordinate coordinate{};
    int value{};
    bool operator == (const Node& other) const { return coordinate == other.coordinate; }
    friend std::ostream& operator << (std::ostream& os, const Node& n) {
        return os << "[" << n.coordinate[0] << ", " << n.coordinate[1] << ", " << n.coordinate[2] << "], [" << n.value << "]"; }
};
struct CompareOnSecond { bool operator ()(const Node& n1, const Node& n2)const { return n1.value < n2.value; } };
struct Hash {size_t operator()(const Node& n) const {return n.coordinate[0] ^ n.coordinate[1] ^ n.coordinate[2];} };

using UniqueNodes = std::unordered_set<Node, Hash>;
using Sorter = std::multiset<Node, CompareOnSecond>;

int main() {
    // a vector with some test nodes
    std::vector<Node> testNodes{
    { {{0, 2, 4}}, 12 },
    { {{2, 4, 5}}, 25 },
    { {{0, 1, 4}}, 34 },
    { {{0, 1, 4}}, 20 },
    { {{0, 1, 5}}, 20 },
    { {{0, 2, 4}}, 112 } };

    // Here we will store the unique nodes
    UniqueNodes uniqueNodes{};
    for (const Node& n : testNodes) uniqueNodes.insert(n);

    // And now, do the sorting
    Sorter sortedNodes(uniqueNodes.begin(), uniqueNodes.end());

    // Some test functions
    std::cout << "\nSorted unique nodes:\n";
    for (const Node& n : sortedNodes) std::cout << n << '\n';

    // find a node
    if (sortedNodes.find({ {{0, 1, 4}}, 20 }) != sortedNodes.end())
        std::cout << "\nFound n4\n";

    // Erase a node
    auto it = sortedNodes.erase({ {{0, 1, 4}}, 20 });
    std::cout << "It value (elements erased): " << it << '\n';

    // Was it really erased?
    if (sortedNodes.find({ {{0, 1, 4}}, 20 }) != sortedNodes.end())
        std::cout << "\nFound n4 after removal\n";

    // Show final result
    std::cout << "\nFinal Set content:\n";
    for (const Node& n : sortedNodes) std::cout << n << '\n';
}

Answer 2

最后，感谢用户的建议和评论，我实现了一个使用 Boost 多索引和 2 索引的解决方案。一个散列唯一索引和一个有序非唯一索引。尽管如此，我还是将上面的答案标记为已接受，因为这是最标准的解决方案。

#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/key_extractors.hpp>

using namespace ::boost;
using namespace ::boost::multi_index;

struct IndexByCost {};
struct IndexByWorldPosition {};

class Node
{

public:
    Node(int _val, int _i) : value(_val), index(_i) {}

    int value; //NON UNIQUE
    unsigned int index; //UNIQUE

    friend inline std::ostream &operator<<(std::ostream &os, const Node &dt)
    {
        os << dt.index << ": [" << dt.value << "]";
        return os;
    }

};

using MagicalMultiSet = boost::multi_index_container<
  Node*, // the data type stored
  boost::multi_index::indexed_by< // list of indexes
    boost::multi_index::hashed_unique<  //hashed index wo
      boost::multi_index::tag<IndexByWorldPosition>, // give that index a name
      boost::multi_index::member<Node, unsigned int, &Node::index> // what will be the index's key
    >,
    boost::multi_index::ordered_non_unique<  //ordered index over 'i1'
      boost::multi_index::tag<IndexByCost>, // give that index a name
      boost::multi_index::member<Node, int, &Node::value> // what will be the index's key
    >
  >
>;

int main(int argc, char const *argv[])
{
    
    MagicalMultiSet container;

    Node n1{24, 1};
    Node n2{12, 2};
    Node n3{214,3};
    Node n4{224,4};
    Node n5{221,5};
    Node n6{221,6};

    auto & indexByCost          = container.get<IndexByCost>();
    auto & indexByWorldPosition = container.get<IndexByWorldPosition>();

    indexByCost.insert(&n1);
    indexByCost.insert(&n2);
    indexByCost.insert(&n3);
    indexByCost.insert(&n4);
    indexByCost.insert(&n5);

    for(auto &it: indexByCost)
        std::cout << *it << std::endl;
    
    auto it = indexByCost.begin();
    std::cout << "Best Node " << **it << std::endl;

    indexByCost.erase(indexByCost.begin());

    it = indexByCost.begin();
    std::cout << "Best Node After erasing the first one: " << **it << std::endl;

    std::cout << "What if we modify the value of the nodes?" << std::endl;
    n2.value = 1;
    std::cout << "Container view from index by world position" << std::endl;
    for(auto &it: indexByWorldPosition)
        std::cout << *it << std::endl;
    
    auto found = indexByWorldPosition.find(2);
    if(found != indexByWorldPosition.end() )
        std::cout << "Okey found n2 by index" << std::endl;

    found = indexByWorldPosition.find(1);
    if(found != indexByWorldPosition.end() )
        std::cout << "Okey found n1 by index" << std::endl;
    
    std::cout << "Imagine we update the n1 cost" << std::endl;
    n1.value = 10000;
    indexByWorldPosition.erase(found);
    indexByWorldPosition.insert(&n1);

    std::cout << "Container view from index by cost " << std::endl;

    for(auto &it: indexByCost)
        std::cout << *it << std::endl;
    
    return 0;
}

使用比较器对具有不同唯一性和小于的标准的一组唯一对进行排序

Using comparator to sort set of unique pairs with different criterias for uniqueness and less than

c++

sorting

stl

strict-weak-ordering

一些定义

Class节点

比较器

具体案例的完整示例