В документации указано, что
Rank
должен быть моделью ReadWritePropertyMap
с целочисленным типом значения и типом ключа, равным типу элемента набора.
Parent
должен быть моделью ReadWritePropertyMap
, а тип ключа и значения должен совпадать с типом элемента набора.
На ваш предыдущий вопрос я разместил в комментарии следующий пример кода:
Посмотрев на (новые для меня) disjoint_set_*
классы, я не думаю, что они позволяют повторять элементы наборов. Они действуют как однонаправленное отображение от элемента к представителю набора. Если вам это поможет: http://paste.ubuntu.com/8881626 – sehe 9 часов назад а>
Вот он, переработанный для воображаемого типа dataum
:
struct dataum {
int x,y;
bool operator< (const dataum& o) const { return tie(x,y) < tie(o.x,o.y); }
bool operator==(const dataum& o) const { return tie(x,y) == tie(o.x,o.y); }
bool operator!=(const dataum& o) const { return tie(x,y) != tie(o.x,o.y); }
};
Вот как я могу увидеть объявление disjoint_set
для него:
std::map<dataum,int> rank;
std::map<dataum,dataum> parent;
boost::disjoint_sets<
associative_property_map<std::map<dataum,int>>,
associative_property_map<std::map<dataum,dataum>> > ds(
make_assoc_property_map(rank),
make_assoc_property_map(parent));
Механизм этого можно найти в документации для Boost PropertyMap — очень мощный уровень абстракции общей структуры данных, в основном используемый с библиотекой Boost Graph. Он невероятно мощный, но я не могу сказать, что он удобен для пользователя.
Вот полная демонстрация Live On Coliru¹
#include <boost/pending/disjoint_sets.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <iostream>
#include <map>
#include <cassert>
using namespace boost;
struct dataum {
int x,y;
bool operator< (const dataum& o) const { return tie(x,y) < tie(o.x,o.y); }
bool operator==(const dataum& o) const { return tie(x,y) == tie(o.x,o.y); }
bool operator!=(const dataum& o) const { return tie(x,y) != tie(o.x,o.y); }
};
int main() {
std::vector<dataum> S { {0,0}, {0,1}, {0,2} };
std::map<dataum,int> rank;
std::map<dataum,dataum> parent;
boost::disjoint_sets<
associative_property_map<std::map<dataum,int>>,
associative_property_map<std::map<dataum,dataum>> > ds(
make_assoc_property_map(rank),
make_assoc_property_map(parent));
for(auto i=0ul; i<S.size(); i++)
ds.make_set(S[i]);
assert((ds.count_sets(S.begin(), S.end()) == 3));
assert((ds.find_set(dataum{0,2}) == dataum{0,2}));
assert((ds.find_set(dataum{0,1}) == dataum{0,1}));
ds.union_set(dataum{0,2},dataum{0,1});
assert((ds.count_sets(S.begin(), S.end()) == 2));
assert((ds.find_set(dataum{0,2}) == dataum{0,1}));
assert((ds.find_set(dataum{0,1}) == dataum{0,1}));
std::cout << "done";
}
¹ Coliru по-прежнему не сотрудничает
person
sehe
schedule
08.11.2014