Какую структуру данных использовать для оценки порядка объектов?

Question

Я пытаюсь определить оптимальную реализацию для следующей задачи:

Допустим, у нас есть класс A, который представляет сложный математический объект и при построении изначально содержит все необходимое внутреннее состояние. Для каждого объекта a_i из A можно вычислить окончательное числовое значение, которое нетривиальным образом зависит от других a_j с j < i, и известно a_0. Более того, уравнения, которые приводят к окончательному ответу, требуют специального порядка оценки и оператор сравнения для a_i может быть определен.

То, что я хочу сделать, это сначала создать все необходимые a_i s, вставить их в некоторую упорядоченную структуру данных и, наконец, пройти по структуре в правильном порядке, чтобы получить окончательные результаты.

Теперь к реальному вопросу: какую структуру данных я использую, чтобы реализовать структуру для порядка оценки в общем виде? Бинарная куча? Или я просто использую std :: vector и сортирую его потом?

Спасибо!

Answer 1

Если оператор сравнения (скажем, меньше) для a_i может быть определен на основе порядка оценки, то естественным контейнером будет std :: set.Обход карты с использованием std :: set :: iterator даст каждый a_i в возрастающем порядке, что будет вашим порядком оценки.Например,

std::set<A> aMap;
A a_i;
... // You create the rest of the A's
aMap.insert(a_i);
aMap.insert(a_j);

for (std::set<A>::iterator aIter = aMap.begin(); aIter != aMap.end(); ++aIter) {
    // Do your evaluation
}

Answer 2

Я бы рекомендовал использовать вектор вместе с функцией подкачки.Выполните цикл по каждому элементу в массиве и поменяйте местами с предыдущим элементом в массиве, если математическая формула вернет true.

Ваш цикл должен был бы пройти по каждому элементу в векторе, а также иметь цикл внутри этогоперебирает все элементы, которые предшествуют индексируемому в настоящее время элементу вектора.Этот внутренний цикл будет содержать проверку вашей математической формулы, то есть логику сортировки.

Надеюсь, это даст вам представление о том, что делать.Отправьте мне комментарий, если вам нужен псевдокод.