Как реализовать сортирующий компаратор, который каскадирует связанные объекты?

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

Логикой здесь является добавление дополнительного 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)); 
    } 
}; 

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, аналогично по концепции эффективному идентификатору пользователя в unix :)).

Если вы не можете изменить метод компаратора класса, вы можете реализовать конкретный компаратор (например, в лямбда или функторе) и использовать его с std::sort.

Некоторые ссылки:

• basic_string::compare
• std::sort, с примером сортировки с использованием лямбда и функтор.