STAT datastructure с сортировкой

Question

Мне нужна структура данных, которая может автоматически сортироваться на основе структуры.

struct{ 
    int key; 
    int comparisonValue(size of the vector); 
} 

мне это нужно в следующем виде:

datastructure<struct, vector<int>> 

Если структура данных автоматически сортируется на основе comparisonValue и на основе минимального значения значения для сравнения, я хотел бы получить вектор и добавить к нему некоторые данные.

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

Что мне делать, если мне нужно изменить ключ, в этом случае compareValue и сохранить порядок сортировки?

Благодаря

Answer 1

std::map из STL.

По умолчанию, это сортирует значения ключей, сравнивая их с помощью std::less<Key>, который по умолчанию вызывает operator< по значениям ключа. Таким образом, вы можете определить перегрузку operator< для вашего типа STRUCT ::

bool operator<(const Key &a, const Key &b) 
{ 
    return (a.someField < b.someField); 
} 

Answer 2

»... и на основе минимального значения значения для сравнения, я хотел бы получить вектор и добавить в него данные "

Если вы имеете в виду, что хотите получить наименьший элемент во всей коллекции, вам может быть лучше с std::priority_queue, предполагая, что вы только обновляете самый маленький элемент.

В противном случае std::map, вероятно, вам нужно, как предлагает Оли Чарльворт. Вероятно, вам стоит взглянуть на map's lower_bound() и upper_bound() методов.

Вы также должны знать, что контейнеры STL содержат экземпляров объектов, поэтому, если вы хотите, чтобы ваши изменения отражались в другом месте, вам нужно вместо этого сохранить указатели на объекты. Затем вы будете использовать отдельный Functor для сравнения указателей в соответствии с тем, что они указывают.