Невозможно удалить из libstdc ++ Структура данных на основе политик - PullRequest
Новая
       33

Невозможно удалить из libstdc ++ Структура данных на основе политик

0 голосов
/ 14 января 2020

В C ++ есть связанный контейнер, который на самом деле представляет собой набор (мультимножество), который может дать порядок элементов в нем.

Вот как я использую контейнер: 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,
                              tree_order_statistics_node_update>;

Проблема в том, что я не могу стереть из него элемент: 

ordered_multiset<int> s;
s.insert(0);
s.erase(0);

cout << s.order_of_key(1); // returns number of elements less than x

// Outputs: 1

Странная часть в том, что если вы замените less_equal на less, то вы сможете сделать работа без проблем, на самом деле, если вы используете контейнер как мультимножество, вы не сможете стереть из него элементы, но нет проблем, если вы используете его как набор.

  • Что является причиной проблемы?
  • Как я могу решить проблему?

Примечание: Пожалуйста, не предлагайте решение проблемы путем использования другого контейнера. Это не решение.

Ответы [ 2 ]

4 голосов
/ 14 января 2020

Используя std::less_equal, невозможно узнать, эквивалентны ли два элемента. std::set использует выражение !comp(a, b) && !comp(b, a), чтобы определить, эквивалентны ли a и b. Это работает, если вы используете строгий слабый порядок , как std::less, но не работает, когда вы используете std::less_equal. 5 и 5 эквивалентны, но !(5 <= 5) && !(5 <= 5) равен false. Таким образом, стирание завершается неудачей.

Короче говоря, вы не можете просто превратить набор в мультимножество, используя std::less_equal.

@ Caleth описал способ использования std::multiset и выполнение поиска по линейному времени. Вы можете определить порядок в логарифмическом c времени, сохранив порядок для каждого элемента. 

template <typename Value>
struct ordered_value {
  size_t order;
  Value value;
};

template <typename Value>
using ordered_multiset = std::multiset<ordered_value<Value>>;

Проблема в том, что вам нужно обновлять порядок каждый раз, когда вы вставляете или стираете (который является линейным ). Вы уверены, что используемый вами контейнер выполняет операцию в постоянное время? Мне это кажется невозможным.

Способ, которым статистика упорядочения c реализована в красно-черном дереве, на самом деле очень похож. В каждом узле есть некоторая дополнительная информация, которая обновляется при вставке или удалении. Дело в том, что это очень близко к лучшему, что вы можете сделать , не создавая при этом своего собственного красно-черного дерева.

1 голос
/ 14 января 2020

В чем причина проблемы?

Вы не предоставили Сравните с tree. Ваша программа некорректна.

Как мне решить проблему?

Использовать std::multiset<T> и 

template<typename Set, typename Key>
size_t order_of_key(const Set & set, const Key & key)
{
    return std::distance(set.begin(), set.lower_bound(key));
}
...