如何實現級聯比較器，級聯相關的對象？

Question

假設，下列類型的鄰接陣列具有被排序：

struct X 
{ 
    string id, parent_id; 
    int value; 

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

隨着上述operator<，它創建以下排序後的數組：

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

什麼是寫比較器的最佳方式，所以它創建以下排序的數組：

{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} 

正如你可能會看到，該陣列是專門分類，其中parent_id創建一個分組&然後根據最低到最高值排列數組。換句話說，最近的對象（那些X，非空parent_id）對象是關鍵參與者。剩下的父母被拉到他們身邊。

我的努力：自然的方式來做到這一點是：

1. 執行從底部與上述比較排序
2. 迭代/反轉，即最高value
3. 查找parent_id爲元件x;如果那麼有效：
   • 搜索爲parent_id，複製&擦除該元素
   • 插入略高於x
4. 遞歸執行步驟3，直到parent_id沒有找到

問題：這可以通過更簡單的方式實現嗎？

注意：此問題不是特定於C++。

Answer 1

此處的邏輯是在struct X中添加額外的int。是的，每個對象的內存都會增加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，並在case parent_id是空的，我們的做法就好像string_id是parent_id（我稱之爲effective_parent_id，概念上類似於unix中的有效用戶ID :)）。

如果你不能修改類比較器方法，你可以實現一個特定的比較器（例如在一個lambda或函數中）並將其與std::sort一起使用。

的一些參考文獻：

• basic_string::compare
• std::sort，與使用的λ和函子排序的一個例子。