どのように関連するオブジェクトをカスケードするソートコンパレータを実装するのですか？

Question

と仮定は、以下のタイプの連続した配列をソートする必要がある。そう、コンパレータを書くための最良の方法は何

{i, p, v} 
---------- 
{a, "", 1} 
{b, "", 2} 
{c, "", 3} 
{dc, c, 4} 
{ea, a, 5} 
{fb, b, 6} 

：前述のoperator<で

struct X 
{ 
    string id, parent_id; 
    int value; 

    bool operator< (const X& x) const { return value < x.value; } 
}; 

、それは以下のソートされた配列を作成します

{i, p, v} 
---------- 
{c, "", 3} // grouping of 'c' 
{dc, c, 4} 
{a, "", 1} // grouping of 'a' 
{ea, a, 5} 
{b, "", 2} // grouping of 'b' 
{fb, b, 6} 

表示されるように、配列は特にがソートされていますはグループ番号&を作成し、次に低い値から高い値に基づいて配列が整理されます。つまり、最新の従属オブジェクト（X、空でないオブジェクトはparent_id）がキープレーヤーです。残っている親は彼らに引っ張られます。

私の努力：これを行うための自然な方法は次のとおりです。

1. parent_idのための最高のvalue
2. ルックのための、つま​​り、逆/下から前述のコンパレータと
3. 反復をソート実行します要素x;有効な場合：ちょうど上記x
4. が再帰的にparent_idまで、ステップ3を実行parent_idため
   • 検索 は、コピー&消去、その要素
   • 挿入

質問が見つかりません。これは簡単な方法で達成できますか？

注：：この問題はC++に固有の問題ではありません。

Answer 1

ここでロジックは、をstruct Xに追加することです。はい、メモリはすべてのオブジェクトに対して4〜8バイト増加しますが、それは私の要求には問題ありません。

struct X 
{ 
    string id, parent_id; 
    int value, value_group = 0; 
    //   ^^^^^^^^^^^ new indicator to be used while sorting 
    bool operator< (const X& x) const 
    { return (value_group == x.value_group)? value < x.value : value_group < x.value_group; } 

    void print() const { cout << "{" << id << ", " << parent_id << ", " << value << ", " << value_group << "}\n"; } 
}; 

他の事はvectorが{}を時系列&ない一度更新された、ということです（申し訳ありません：私はQnの中で言及して逃したこの重要な部分）。したがって、新しい要素が追加されたときはいつでも、それはその親をその近くにプルダウンします。そのロジックは、（vector, array, list等）&コレクションを含むクラスの形で以下に記載されているオブジェクトを追加：

struct MyClass 
{ 
    vector<X> vx; 

    void Add (X&& x) 
    { 
    auto end = vx.end(), it = std::prev(end); 
    bool isStandAlone = true; 
    for(auto parent_id = x.parent_id; 
     not parent_id.empty(); 
     parent_id = it->parent_id) 
     for(auto itPrev = it - 1; 
      parent_id != it->id or (isStandAlone = false); 
      it = itPrev--) 
     if(itPrev == vx.begin()) 
     { 
      it->parent_id.clear();  
      break; 
     } 

    if(isStandAlone) 
     x.parent_id.clear(); 
    else 
    { 
     auto begin = it; 
     do { it->value_group = x.value; } 
     while(++it != end and not it->parent_id.empty()); 

     decltype(vx) temp(std::make_move_iterator(begin), std::make_move_iterator(it)); 
     vx.erase(begin, it); 
     vx.insert(vx.end(), temp.begin(), temp.end()); 
    } 
    x.value_group = x.value; 
    vx.push_back(std::move(x)); 
    } 
}; 

Demo。

Answer 2

あなたの現在のコンパレータは、おそらく次のようになります。

int cmp = a.string_id.compare(b.string_id); 
if(cmp == 0) { 
    cmp = a.parent_id.compare(b.parent_id); 
    if(cmp == 0) { 
     cmp = a.value - b.value; 
    } 
} 
return cmp < 0; 

あなたがわずかに異なるコンパレータを使用して並べ替え、あなたの希望を実現することができます。

auto a_effective_parent_id = a.parent_id.empty() ? a.string_id : a.parent_id; 
auto b_effective_parent_id = b.parent_id.empty() ? b.string_id : b.parent_id; 

// compare first by 'effective' parent id 
int cmp = a_effective_parent_id.compare(b_effective_parent_id); 
if(cmp == 0) { 
    // here we order items with empty parent_id before children 
    cmp = a.parend_id.compare(b.parent_id); 
    if(cmp == 0) { 
    // then compare by 'string_id' 
    cmp = a.string_id.compare(b.string_id); 
    if(cmp == 0) { 
     // and eventually compare by 'value' 
     cmp = a.value - b.value; 
    } 
    } 
} 
return cmp < 0; 

これは、私たちがソート最初parent_idによって及び手段ケースparent_idが空の場合は、string_idがparent_id（私がeffective_parent_idと呼んでいます。これは、有効なユーザーIDと同じ意味です））。

クラスコンパレータメソッドを変更できない場合は、特定のコンパレータ（ラムダまたはファンクタなど）を実装してstd::sortと一緒に使用します。

いくつかの参考文献：ラムダとファンクタを使用してソートを例に

• basic_string::compare
• std::sort、。