stl — лучший отсортированный контейнер c ++

Ваш вопрос не совсем понятен. С одной стороны, вы говорите, что хотите отсортированный контейнер, но с другой стороны, способ, которым вы говорите о вещах, заключается в том, что вы собираетесь генерировать движения, помещать их в контейнер, затем сортируйте их в соответствии с критериями, определенными вашим AI.

Давайте рассмотрим их отдельно. Во-первых, мы предположим, что вы хотите использовать баллы в качестве ключа, и рассмотрите ходы, которые идут с конкретными баллами. В этом сценарии вы сгенерируете ход, ИИ оценит этот ход, затем вы сохраните ход с его счетом в качестве ключа. Поскольку вы можете иметь несколько ходов с одним и тем же счетом (т. Е. Эквивалентными ключами), структура данных, которую вы хотите для этого случая, представляет собой std::multimap,

Другая возможность состоит в том, что вы генерируете все ходы, помещаете их все в структуру данных, оцениваете их все, а затем сортируете все по счету. Для этого сценария вы, вероятно, хотите использовать std::vector<std::pair<score_type, move>>, В этом случае, когда вы генерируете каждый ход, вы, вероятно, присваиваете ему оценку примерно в 0. Затем вы проходите вектор, и ИИ генерирует счет для каждого хода. Затем вы сортируете их, используя функцию сравнения, которая учитывает только оценку.

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

Сила std::multiset является то, что он остается отсортированным все время. Например, если вы хотите генерировать ходы до тех пор, пока не достигнете некоторого временного лимита, это позволит вам выполнить это довольно четко — сгенерировать ход, забить его, вставить в мультимножество. Независимо от того, когда вы останавливаетесь, все сгенерированные вами ходы до этой точки уже отсортированы, поэтому (например), если человек, играющий против вашей программы, может заставить ИИ сделать ход немедленно, ИИ всегда имеет рекорд лучшего переместите его, пока он найден, так что он может немедленно сделать ход, который он «считает» лучшим.

Другой возможностью было бы использование очереди с приоритетами. В типичном случае для шахмат одна вещь, которую вы будете делать, это генерировать (скажем) пару десятков или возможных следующих ходов. Затем вы выберете лучшее из них и наберете количество возможных встречных ходов. Затем вы выберете лучшее из них и наберете счетчики для этих ходов и так далее, пока не наберете (скажем) 4 или 5 полных ходов вглубь.

Для этого вам не нужно все ходы по порядку — вы просто хотите быстро получить N лучших ходов. В этом случае приоритетная очередь работает довольно хорошо. Вы можете получить N лучших ходов, а затем проигнорировать остальные. Это означает, что вы только полностью сортируете N лучших ходов (те, которые вас интересуют) и минимизируете накладные расходы для остальных, но только делаете достаточно, чтобы убедиться, что у них более низкие оценки.

Я должен также отметить, что если это то, что вы действительно хотите, вы можете сделать то же самое в случае массива. Вместо того чтобы использовать сортировку для сортировки всех ходов в порядке убывания, вы можете использовать nth_element, чтобы найти только N лучших результатов. nth_element упорядочивает массив / вектор в две группы: те, которые будут сортировать перед выбранным элементом, затем выбранный элемент, затем те, которые будут сортироваться после этого выбранного элемента. Например, учитывая 100 ходов, из которых вы хотите сохранить 5 лучших, вы бы использовали nth_element организовать их в 95 меньших ходов, 95^го элемент, затем другой 4. Тем не менее, не предпринимаются попытки упорядочить элементы в каждой группе.

Преимущество этого состоит в том, что это может быть завершено за O (N) время вместо O (N log N), необходимого для полной сортировки.

Между этими двумя возможностями (priority_queue против nth_element) мы получаем почти такой же компромисс, как между set::multiset а также std::vector с std::sort: priority_queue поддерживает свой порядок в любое время. Это остается весьма эффективным, даже если вы смешиваете вставки и удаления более или менее произвольно. С std::vector а также std::nth_elementобычно вы хотите вставить все элементы, затем позвоните nth_element, а затем рассмотрим верхние позиции. Если вы собираетесь смешать два (вставьте некоторые элементы, затем удалите несколько лучших, вставьте еще несколько, удалите еще несколько и т. Д.), Вам нужно будет позвонить nth_element каждый раз, когда вы переходите от вставки к удалению, это может довольно быстро убить эффективность.