1

まず、同様の質問を検索しようとしましたが、私の問題が何であるかを説明する回答が見つかりませんでした.

問題は次のとおりです。座標 (x、y、z) を持つ N 個のノードのセットが与えられた場合、それらを 4 番目の値 F を使用してできるだけ速く並べ替えます。

std::setO(log(N)) の複雑さがあるため、この目的のためにカスタム コンパレータを使用したいと考えています。a とonstd::vectorの呼び出しを試すこともできますが、理論的には操作が遅くなります。std::sortstd::vector

なぜこれ？私は常にセットに要素を挿入し、F値を変更しているため（値を変更し、コンテナ内の要素を並べ替えて消去して再挿入することを意味します）、F値が小さい要素を取得したい(コンテナの前にある要素です)。

std::setしかし、問題に行きましょう。

座標は一意性プロパティを定義し、厳密な弱い順序付けルールに従います。つまり、aとbは同じオブジェクトと見なされます。

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

この問題は、座標に基づく一意性基準と F 値に基づく並べ替え基準の定義に関連しています。セットに同じ座標を持つ 2 つの要素を格納したくないが、座標は異なるが同じ F 値を持つ 2 つの要素を格納できるようにしたい

コンパレータは、次の 3 つのプロパティも満たす必要があります。

  1. 無反射 x < x false
  2. 非対称x < y true性が意味することy < x false
  3. 推移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;
    }
};

1つの問題は、座標は異なるがF値が同じ2つのノードの場合である可能性があると思います

具体的なケースを含む完全な例

この例では、上記のクラスを使用していくつかの要素を挿入/検索/消去していますが、出力に表示されているため、期待どおりに動作していません:

#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]

**期待される出力: ** F が小さいもの (n1) から F が大きいもの (n3) に並べられた要素 n1、n5、n2、n3 に対応します。

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

実装の助けやアイデア、代替案をいただければ幸いです。ありがとう

4

2 に答える 2

1

残念ながら、お客様の要件は 1 つだけでは満たすことができませんstd::set。はstd::set、ソートと一意性のために同じコンパレータを使用します。コンパレータには状態がありません。つまり、一度を最初の条件と比較し、次回を 2 番目の条件と比較することはできません。それはうまくいきません。

そのため、2 つのコンテナーを使用する必要があります。最初は、std::unordered_set等しい座標にコンパレーターを使用し、2 つ目のコンテナーはstd::multiset..

std::unordered_mapを と組み合わせて使用​​することもできますstd::multiset。

または、独自のコンテナーをクラスとして作成し、パフォーマンスの最適化を試みます。

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';
}
于 2021-12-03T14:33:54.243 に答える