如何实现对相关对象进行级联的排序比较器？

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)对象是关键参与者。剩下的父母被拉到他们身边。

My way ：自然的方法是：

1. 使用上述比较器执行排序
2. 从底部/反向迭代，即最高的value
3. 查找parent_id元素x；如果有效，则：
   • 搜索parent_id，复制和删除该元素
   • 插入略高于x的

​

1. 递归执行步骤3，直到parent_id未找到为止

问题：这能以更简单的方式实现吗？

Note：这个问题并不是C++特有的。

Answer 1

这里的逻辑是在int中添加一个额外的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));
  }
};

演示。

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，在概念上类似于unix :中的有效用户id )。

如果无法修改类比较器方法，则可以实现特定的比较器(例如在lambda或函子中)，并将其与std::sort一起使用。

一些参考资料：

• 字符串:比较
• std:分类，并给出了使用lambda和函子进行排序的示例。