вставка элемента в отсортированный вектор и сохранение сортированных элементов
Итак, у меня есть вектор, и я хочу, чтобы элементы сортировались всегда. Как я должен идти о вставке элемента в этот вектор и сохранении элементов отсортированными, когда я вынимаю их. Я смотрел в std::lower_boundОднако это дало противоположность того, что я хотел.
Например, это то, что я хочу: когда я выталкиваю все элементы в векторе, это должно быть:
1 2 3 4 5. Это означает, что вектор должен хранить их как 5 4 3 2 1. Если используется нижняя граница, вектор сохраняет их как 1 2 3 4 5, и он отображается как 5 4 3 2 1. Также, функтор сравнения будет передан так, чтобы lower_bound Функция использует функтор сравнения. Есть ли способ взять противоположность функтору сравнения?
Решение
Чтобы ваш вектор постоянно сортировался, вы всегда должны вставлять новые элементы в правильное положение. Поскольку вы хотите извлекать элементы в порядке возрастания, а вектор предоставляет только метод pop_back (), вы должны сортировать элементы в порядке убывания. поэтому сначала нужно найти правильное положение, а затем вставить туда:
typedef std::vector<int> ints;
void insert( ints &cont, int value ) {
ints::iterator it = std::lower_bound( cont.begin(), cont.end(), value, std::greater<int>() ); // find proper position in descending order
cont.insert( it, value ); // insert before iterator it
}
Другие решения
Других решений пока нет …