Структура данных теории множеств - PullRequest
Новая
       28

Структура данных теории множеств

2 голосов
/ 10 декабря 2011

Я пришел из довольно функционального программирования, и я не привык к (эффективным) структурам данных C ++.Мне нужна структура данных, которая содержит несколько элементов, как показано в struct element.В коллекции идентификатор поля должен быть уникальным.

Я хочу выполнить очень быстрое сравнение множеств, как в теории множеств, например, при сравнении множеств {x1,x2,x3} и {x4,x5} Я хочу определить множество пересечений {x5} (или {x2}, которыеравным в данном случае) и вычитают наборы из других наборов, например, например {x1,x2,x3} \ {x5} = {x1,x3}.

Существует ли ... "теоретическая" структура данных во вселенной C ++? 

struct element {
int id;
float value;
};

struct element x1 = {1, 1.0};
struct element x2 = {2, 2.0};
struct element x3 = {3, 3.0};

struct element x4 = {3, 3.1};
struct element x5 = {2, 2.0};

Ответы [ 3 ]

5 голосов
/ 10 декабря 2011

Есть std::set, который реализует динамические наборы (динамические элементы могут быть вставлены или удалены). Чтобы заставить его работать с вашей структурой element, вам нужна пользовательская функция сравнения, которая смотрит только на id. В качестве альтернативы вы можете использовать std::map<int, float>, что может лучше соответствовать вашей проблеме.

Чтобы найти пересечение двух множеств, используйте алгоритм std::set_intersection. Для этого нужны отсортированные диапазоны, которые включают диапазоны итераторов в std::set или std::map. Для разницы используйте std::set_difference.

1 голос
/ 10 декабря 2011 
struct element {
    int id;
    float value;

    element(int id_=0, float value_=0.0) : id(id_), value(value_) {}

    bool& operator==(const element& e) const
    {
        return id==e.id && value==e.value;
    }
};

element e1(1,1.0);

std::set<element> set_;
set_.insert(e1);

Оформить алгоритм std для операций, которые вы можете выполнять.http://www.cplusplus.com/reference/algorithm/

1 голос
/ 10 декабря 2011

Просто хочу упомянуть об этом, поскольку при работе с наборами существует действительно отличная структура данных, но она не соответствует всем вашим потребностям,

Но, тем не менее, вы можете помнить об этом, если у вас есть такие требования, как,

1) Запрос к какому набору принадлежит элемент

2) Союз разных комплектов

Оба в сублогарифмическом времени, т.е. почти постоянны. Это называется несвязанной структурой данных. http://en.wikipedia.org/wiki/Disjoint-set_data_structure

...