Тип данных похож на вектор, но отсортирован

Question

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

Также существует простой способ удаления элементаиз вектора или очереди, если вы знаете, что это такое, без необходимости искать и находить его?

Answer 1

Звучит так, как вы хотите std::set или std::multi_set.

Answer 2

Я не знаю такого контейнера.

std::sort существует, в котором вы можете указать функцию сортировки, но зачастую даже более эффективно фактически вставлять элементы в правильное место напрямую.

Если вы всегда так делаете, единственная «проблема», которую вам нужно решить, - это добавить элемент в уже отсортированный список, что можно сделать в худшем случае за линейное время.

Обратите внимание, что std::vector<T>::insert() принимает итератор в качестве параметра, чтобы указать, где выполнить вставку. Возможно, вы захотите написать findPosition() методы, которые возвращают такой итератор. Затем написание sorted_insert() метода тривиально и становится примерно таким:

std::vector<int>::iterator findPosition(int v);
void sorted_insert(std::vector<int>& vec, int v) { vec.insert(findPosition(v), v); }

void foo()
{
  std::vector<int> vec;
  sorted_insert(vec, 4);
}

Answer 3

Звучит так, будто вы ищете set, а не вектор.Он будет отсортирован в соответствии с естественным порядком (оператор <).Чтобы удалить элемент по значению, вызовите erase.

В качестве альтернативы вы можете просто использовать sort в векторе для сортировки элементов.Если вам нужен произвольный доступ к элементам, вам понадобится такой подход;отсортированные контейнеры не обеспечивают произвольный доступ.

Чтобы найти элемент в отсортированном векторе, вы можете использовать binary_search.

Answer 4

Зависит от того, что вам нужно и зачем вам это нужно.

Нет, в стандартной библиотеке нет «отсортированного» вектора или очереди.У вас есть 2 варианта, если вы хотите использовать только стандартную библиотеку:

• сортировать контейнер (вектор или очередь) при каждой вставке / удалении
• агрегатВаша собственная вставка / удаление, реализуя сортировку вставок

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

Другой вариант - поискать стороннюю библиотеку - я думаю, у boost будет такой контейнер, но я не совсем знаю.

«Также есть простой способ удалить элемент из вектора или очереди, если вы знаете, что это такое» - что вы подразумеваете под этим?У вас есть итератор или?Или его индекс?Я буду редактировать свой ответ при обновлении (: