Эффективный способ вставки данных в отсортированный вектор
Имея отсортированный std::vector, вставку элемента по порядку можно выполнить с помощью этого кода.
После вставки одного элемента мне нужно отсортировать вектор для обработки.
template< typename T >
typename std::vector<T>::iterator
insert_sorted( std::vector<T> & vec, T const& item )
{
return vec.insert
(
std::upper_bound( vec.begin(), vec.end(), item ),
item
);
}
Этот код не очень эффективен по сравнению с вызовом emplace_back.
Есть ли лучшая реализация для вставки данных в отсортированный вектор, возможно, с использованием std::rotate, чтобы избежать перераспределения/перехода данных
NB. Я не сравниваю две вставки, а просто чтобы иметь представление о номинальном случае (т. е. вставке упорядоченных чисел).
Отвечает ли это на ваш вопрос? как вставить значение в отсортированный вектор?
У вопроса проблема XY. Не существует более быстрого способа вставки элементов в вектор. Простая вставка элемента в середину вектора имеет временную сложность O(n) (n — размер вектора). Правильный способ решить вашу проблему — перепроектировать алгоритм или структуру данных, но в вопросе нет информации об этом.
Вы должны понимать свои данные и то, какие операции вам нужны больше всего. А затем вы выбираете (или проектируете) соответствующую структуру данных. Итак, объясните немного больше о размере ваших данных, о том, как часто вы собираетесь добавлять данные, ожидаете ли вы, что локальность данных важна (кэши/непрерывная память) и т. д. Примечание: может быть даже быстрее вставлять элементы в назад, а затем вызвать сортировку O(log n). В частности, если вы собираетесь вставлять значения пакетами.
Если производительность вставки имеет решающее значение, вам нужно будет использовать другую структуру данных, например std::set, но вам нужно будет протестировать свое приложение, чтобы убедиться, что оно не окажется более дорогим в другом месте.
Да, я провел тест, и std::vector более эффективен, чем std::set.
Вы снова задаете неправильный вопрос. Вы должны описать проблему, в которой вы используете этот отсортированный вектор.
Вы узнаете это, только проведя тесты для каждого метода, но я не понимаю, почему добавление и вращение будут быстрее, чем вставка, учитывая, что вращение перемещает больше данных. Вы можете избежать перераспределения, если заранее знаете, насколько велик будет ваш вектор, и предварительно выделите его.
«Да, я провел тест, и std::vector более эффективен, чем std::set», это зависит от размера контейнера. Ожидается, что для небольших размеров вектор будет быстрым, но есть поворотный момент, после которого вставка в std::set происходит быстрее.
Естественно, показанный вами подход менее эффективен, чем emplace_back() .... потому что emplace_back() не гарантирует, что вектор будет отсортирован по завершении. Итак, ваше утверждение сравнивает яблоко с апельсином. Чтобы сделать сравнение с emplace_back() более справедливым, вам нужно отсортировать вектор, например, после vec.emplace_back(item); std::sort(vec.begin(), vec.end());
это интересный вопрос, но оптимальное решение зависит от стольких факторов, размера входных данных, шаблонов использования (сколько вставок и сколько обращений для чтения), что правильный ответ - это не просто какой-то код и утверждение «это оптимально»
поскольку вы приняли ответ, я полагаю, что ваша модель использования — это много вставок, а не столько чтений. Если это так, вы можете упомянуть об этом в вопросе.
@ 463035818_is_not_an_ai, я обработал вектор сразу после вставки (перед обработкой вектор необходимо отсортировать)
Вы имеете в виду, что после вставки одного элемента вам необходимо отсортировать вектор? Пожалуйста, уточните это в вопросе.
Ответы 2
Код, который вы показали, делает другое, чем emplace_back, нет смысла сравнивать время их выполнения.
Код, который вы показываете, должен быть как минимум асимптотически оптимальным для вставки одного произвольного значения.
Если у вас есть другой вариант использования, вы можете сделать что-то еще.
Например, если вы ожидаете, что большинство элементов будут вставлены сзади, вы можете просто сначала проверить этот случай и вставить в конце.
template< typename T >
typename std::vector<T>::iterator
insert_sorted_expect_greatest( std::vector<T> & vec, T const& item )
{
typename std::vector<T>::iterator where = item > vec.back() ? vec.end() : std::upper_bound( vec.begin(), vec.end(), item );
return vec.insert( where, item );
}
Я исправил вопрос. NB. Я не сравниваю две вставки, а просто чтобы иметь представление о номинальном случае (т. е. вставке упорядоченных чисел).
@TedZach какую операцию ты на самом деле хочешь?
Мне нужно вставить, сохраняя заказ. 90% новый элемент больше предыдущего вставленного
Прошу прощения. Все вставленные элементы
@больше, чем последний вставленный элемент, или больше, чем все элементы? Вы вставляете по одному или можете вставить диапазон?
Я вставляю по одному элементу за раз. И обработать вектор после вставки
Тогда вам не нужно вставлять в отсортированный вектор. Вы можете вставить в вектор и отсортировать позже.
Значит, вставка с помощью двоичного поиска хуже, чем emplace_back + sort?
@TedZach за некоторое количество вставок
Почему бы и нет, если в порядке [[вероятно]] emplace_back else emplace_back + sort ?
Ой, я неправильно прочитал требование. Если вам нужно обрабатывать vec после каждой вставки, то emplace_back+sort, вероятно, будет хуже, чем search+insert. Но для ваших реальных данных вы можете не увидеть большой разницы.
Попробую с помощью QuickBench, посмотрим результат
Вы можете получить почти такой же результат, используя амортизированный анализ. У вас есть всеобъемлющая структура данных, содержащая вектор. Вы помещаете_back или emplace_back в вектор и притворяетесь, что это отсортированная вставка, хотя это не так. Вы записываете внутри себя наличие новых (неотсортированных) записей.
Затем, когда в следующий раз кто-то получит доступ к данным, вы все это сортируете. std::sort действительно хорош для смежных данных. Если у вас есть много отсортированных вставок перед следующим доступом, это работает очень хорошо. И аналитически, и практически.
Этот ответ хорош, если предположить, что он вставляет несколько элементов, и после этого ему нужно их отсортировать. Если после каждой вставки одного элемента ему нужно использовать отсортированный диапазон, то его метод лучше, но все равно плох. Таким образом, по сути, ваш ответ добавляет к вопросу некоторые предположения.
@MarekR Вероятно, именно поэтому я прямо заявил, в чем заключается предостережение и явное предположение? Думаете, это недостаточно ясно?
вы сравниваете двоичный поиск, за которым следует вставка, с добавлением. Векторы, как известно, плохо справляются с вставкой или удалением элементов посередине.