Я работаю над проблемой, где каждая пара представляет собой закрытый интервал, и мне нужна структура данных для хранения коллекции этих пар. Эта структура данных должна поддерживать две операции: вставку(пара) и удаление(idx). Операция вставки должна проверить, не перекрывается ли вставляемый интервал с какими-либо существующими интервалами в коллекции; если есть перекрытие, вставка должна завершиться неудачно и вернуть -1. Операция удаления должна удалить самую большую пару idx в коллекции.
Моя цель — реализовать это, используя только стандартную библиотеку C++, сохраняя при этом минимальный код. Кроме того, крайне важно, чтобы временная сложность методов вставки и удаления была меньше O(log n).
Я был бы очень признателен за любые ваши предложения или идеи о том, как добиться этого эффективно, без необходимости кодирования. Большое спасибо за вашу помощь! Пока что единственное решение, которое я придумал, — это использование дерева B+, но для этого требуется немного больше кода.
class CustomDataStructure {
// some underlying private data structures
public:
bool insert(pair<int ,int> interval);
bool delete(unsigned int idx);
}
🤔 А знаете ли вы, что...
C++ обладает возможностью шаблонного программирования, что позволяет создавать обобщенные алгоритмы и структуры данных.
На практике:
std::lower_bound, сравнивая начало интервала, чтобы найти позицию вставки (O log N).Вставьте в заданную позицию, если нет конфликта (O(1) для списка, O(N) для вектора, но во многих практических ситуациях последний все же может быть быстрее.)
Теоретически: вместо этого используйте std::map. Удовлетворяет Big-O, но для этого размера элемента он, вероятно, будет медленнее, когда Big-O начнет иметь значение.
Вы можете «удешевить» удаление, пометив интервалы как «неиспользуемые»; например, сделав их эквивалентными длине 0. Это означает, что вставка должна проверять не только непосредственного преемника, но она все еще находится где-то в районе амортизированного O (1), за исключением рабочих нагрузок в худшем случае.
В std нет контейнера, который мог бы удовлетворить ваши требования.
Ни один из контейнеров последовательностей не может вставляться в произвольные позиции менее чем за O(size()). vector, deque и inplace_vector имеют O(размер) insert. list и forward_list имеют поиск O(размер).
Ни один из ассоциативных или неупорядоченных ассоциативных контейнеров не может найти i-й индекс менее чем за O(i). std::advance и др. являются O(i), если только итератор не удовлетворяет RandomAccessIterator, что не относится к этим контейнерам.
Ни один из адаптеров контейнера не помогает, поскольку они по-прежнему имеют характеристики вставки базового контейнера.
Вам потребуется реализовать собственный контейнер, чтобы удовлетворить ваши требования к сложности. Что-то вроде Индексируемого списка пропуска подойдёт.
Это частично похоже на ответ Петерхена:
Лучшее, о чем я могу думать, это
std::set для реализации двоичного поискаleft.second < right.firstПользовательское сравнение рассматривает все пары с одинаковыми или перекрывающимися диапазонами как равные. «А» не меньше, чем «Б», и «Б» меньше, чем «А», означает, что «А» и «В» одинаковы.
Тогда вам нужно только проверить результат std::set::insert, чтобы узнать, существует ли диапазон.
Для удаления вы можете использовать std::set::reverse_iterator и цикл for. Это делает удаление O(N), но N зависит только от индекса, а не от размера std::set (если только индекс не зависит от размера std::set).
Давайте изучим теорию отношений баз данных.
Используйте std::vector для хранения данных. Это будет основной стол.
Используйте std::map<key, vector-index> в качестве индексной таблицы.
Вы ищете векторный индекс с помощью индексной таблицы, а затем используете векторный индекс для прямого доступа к данным.