如何实现级联比较器，级联相关的对象？

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，与使用的λ和函子排序的一个例子。