Как сохранить элементы, отсортированные по динамическому атрибуту?

Question

Я использую STL std :: multiset <> как отсортированный список указателей. Порядок сортировки определяется свойство элементов которые указывают на, что-то вдоль линий этого упрощенного примера:

struct A 
{ 
    int x; 
}; 

bool CompareAPointers(const A* lhs, const A* rhs) 
{ return lhs->x < rhs->x; } 

std::multiset<A*, CompareAPointers> sorted_set; 

сложность заключается в том, что значения имущества, используемого для сортировки набора можно изменить (вы можете изменить Ax в приведенном выше примере), который может сделать порядок сортировки некорректный:

A a1, a2; 
a1.x = 1; 
a2.x = 2; 
sorted_set.insert(&a1); 
sorted_set.insert(&a2); 
a1.x = 3; 

Я могу держать список, отсортированный по стиранию и вставив элементы, когда соответствующие изменения атрибутов, но бухгалтерский учет становится в быть немного болью. Я чувствую, что все это неправильно. Может ли кто-нибудь предложить лучший способ сохранить список, отсортированный, когда порядок сортировки может динамически измениться? Изменения происходят предсказуемыми способами в предсказуемые моменты времени, но мой текущий подход только чувствует неправильно.

Answer 1

Boost Multi-Index поддерживает сортировку всего, что угодно, и поддерживает изменение полей, в которые попадает список, хотя вы не можете просто набрать a1.x=1, вместо этого вы должны использовать MultiIndex::replace().
Я не могу придумать более быстрый/более естественный способ сделать это, так как удаление и повторное вложение элемента должно было быть сделано в любом случае.

Answer 2

Вместо этого я хотел бы использовать отсортированный std::vector. В одном из тех пунктов, где вы предсказуемо изменяете x для одного из членов набора, просто перерисуйте вектор. Это немного чище, чем удалять и повторно вставлять предметы. Это может быть слишком много накладных расходов, хотя, если вы часто изменяете свойство одного элемента набора и повторно сортируете. Было бы гораздо полезнее, если вы, вероятно, сразу меняете многие из этих свойств.

Answer 3

Как указывалось другими, использование std :: set или std :: multiset просто не разрезает его.

Вы, вероятно, не заметили, так как используете указатели, но предположение состоит в том, что объекты неизменяемы (хотя в этом случае это означает, что указатели являются const, но не заостренным значением).

Таким образом, вы не можете использовать (напрямую) стандартный контейнер, который будет автоматически выполнять ваш учет.

На данный момент у вас есть несколько решений:

• вы можете использовать библиотеку, в этом случае Boost.MultiIndex приходит на ум, даже если вам придется научиться использовать его
• или вы может обернуть стандартный контейнер в выделенный класс (например, ваш комплект)

Я думаю, что оба одинаково важны. Поскольку операция очень проста, вы можете не захотеть использовать библиотеку Boost для этого еще (кривая обучения, интеграция, ...).

Также вы можете использовать контейнеры «инвазивные». Я имею в виду, что вы можете использовать шаблон «Наблюдатель» здесь >> ваш объект может уведомлять свой контейнер каждый раз при изменении его значения, чтобы контейнер переместил его в свое «новое» правильное положение (используя внутренний std :: multiset) ,

Если эффективность является проблемой, я бы не стал рассматривать сортировку вектора. Сортировка полного контейнера каждый раз, когда одно изменение объекта представляет собой отходы, метод стирания/вставки намного эффективнее.