Получить число элементов больше числа

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

Мой вопрос: Существуют ли стандартные контейнеры в библиотеке С++, которые могут решить проблему? Я знаю, что std::multiset может вставлять элементы в логарифмическое время, но как вы можете его запросить? Или я должен реализовать структуру данных (например, дерево двоичного поиска) для ее решения?

Ответ 1

Отличный вопрос. Я не думаю, что в STL есть что-то, что бы соответствовало вашим потребностям (при условии, что вы ДОЛЖНЫ иметь логарифмические времена). Я думаю, что лучшим решением тогда, как говорит собеседник в комментариях, является внедрение дерева RB. Вы можете посмотреть исходный код STL, особенно на stl_tree.h, чтобы узнать, можете ли вы использовать его.

Еще лучше, посмотрите на: (Ранковое дерево в С++)

Что содержит ссылку на реализацию:

(http://code.google.com/p/options/downloads/list)

Ответ 2

Вы должны использовать мультимножество для логарифмической сложности, да. Но вычисление расстояния является проблемой, поскольку итераторы set/map имеют двунаправленную, а не RandomAccess, std:: distance имеет сложность O (n):

multiset<int> my_set;
...
auto it = my_map.lower_bound(3);
size_t count_inserted = distance(it, my_set.end()) // this is definitely O(n)
my_map.insert(make_pair(3);

Ваша сложность проблемы сложна. Вот полный анализ:

Если вам нужна сложность O (log (n)) для каждой вставки, вам нужна сортированная структура как набор. Если вы хотите, чтобы структура не перераспределяла или перемещала элементы при добавлении нового элемента, вычисление расстояния точки ввода будет равно O (n). Если вы знаете размер вставки заранее, вам не нужно логарифмическое время вставки в сортированном контейнере. Вы можете вставить все отсортированные элементы, а - столько же (n.log(n)), сколько n * O (log (n)) вставки. Единственная альтернатива - использовать выделенный контейнер, например, взвешенное RB-дерево. В зависимости от вашей проблемы это может быть решение, или что-то действительно переполняющее.

Используйте multiset и distance, вы - O (n.log(n)) при вставке (да, n вставки * log (n) время вставки для каждого из них), O (nn) на расстоянии вычисление, но расчет расстояний очень быстрый.
Если вы знаете введенный размер данных (n) заранее: используйте вектор, заполните его, отсортируйте, верните свои расстояния, вы - O (n.log(n)), и его легко закодировать.
Если вы не знаете n заранее, ваше n, вероятно, будет огромным, каждый элемент будет иметь большой объем памяти, поэтому вы не сможете перераспределить O (n.log(n)): тогда у вас есть время для повторного кодирования или повторного кодирования - используйте нестандартный код, вам действительно нужно соответствовать этим ожиданиям сложности, используйте выделенный контейнер. Также рассмотрите возможность использования базы данных, вероятно, у вас будут проблемы с сохранением этого в памяти.

Ответ 3

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

vector<int> v = { 1, 2, 3, 4, 5 };
int some_value = 3;

int count = count_if(v.begin(), v.end(), [some_value](int n) { return n > some_value; } );

Изменить для исправления синтаксических проблем с помощью лямбда-функции

Ответ 4

Если весь диапазон чисел достаточно мал (порядка нескольких миллионов), эта проблема может быть решена относительно легко, используя Дерево Фенвика.

Хотя деревья Фенвика не являются частью STL, они очень просты в реализации и эффективны по времени. Сложность времени O(log N) как для обновлений, так и для запросов, а постоянные факторы низкие.

Вы упомянули в еще один вопрос, что вам нужно это для конкурса. Fenwick trees являются очень популярными инструментами в конкурентном программировании и часто полезны.