如何实现级联相关 objects 的排序比较器？

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，有 non-empty parent_id） objects 是关键球员。剩下的parents拉到他们那里去

我的努力：自然的做法是：

使用上述比较器进行排序
从bottom/reverse开始迭代，即最高的value
寻找 parent_id 元素 x；如果有效则：
- 搜索 parent_id，复制并删除该元素
- 在 x
递归执行第3步直到parent_id没有找到

问题：可以用更简单的方法实现吗？

注意：这个问题不是C++特有的。

Answer 1

您当前的比较器可能如下所示：

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 :)).

如果您无法修改 class 比较器方法，您可以实现一个特定的比较器（例如在 lambda 或仿函数中）并将其与 std::sort.

一起使用

部分参考资料：

basic_string::compare
std::sort，以及使用 lambda 和仿函数进行排序的示例。

Answer 2

这里的逻辑是在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 中没有提到这个重要部分）。因此，无论何时添加新元素，它都会将其父元素下拉到自身附近。该逻辑在下面以 class 的形式提到，其中包含集合（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.

如何实现级联相关 objects 的排序比较器？

How to implement a sorting comparator which cascades the related objects?

c++

sorting

algorithm

grouping

comparator