首先，我试图搜索类似的问题，但我没有找到任何解释我的问题可能是什么的回应。
问题如下：给定一组坐标为 (x,y,z) 的 N 个节点，使用第 4 个值 F 尽可能快地对它们进行排序。
为此，我想将 astd::set与自定义比较器一起使用，因为它具有 O(log(N)) 复杂性。我知道我也可以尝试一个std::vector和一个调用std::sortonstd::vector但理论上是一个较慢的操作。
为什么这个？因为我不断地在集合中插入元素，更改 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 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 值相同的情况
具体案例的完整示例
Ì在这个例子中，我使用上面的类来插入/查找/删除一些元素，但是它显示在输出中，它的行为不像预期的那样：
#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]
我将不胜感激任何帮助或想法以及实施的替代方案。谢谢