SORU
9 Kasım 2010, Salı


::Anlayış artırmak disjoint_sets

Boost kullanmak istiyorum::disjoint_sets, ama the documentation benim için açık değil. Birisi her şablon parametresi ne demek olduğunu açıklar ve bir disjoint_sets oluşturmak için küçük bir örnek kod vermek belki misiniz?

İsteği başı olarak, disjoint_sets uygulamak için kullanıyorum Tarjan's off-line least common ancestors algorithm, ben.e - değer türü vertex_descriptor olmalıdır.

CEVAP
9 Kasım 2010, Salı


disjoint_sets<Rank, Parent, FindCompress>
  • RütbePropertyMap boyutunu saklamak için kullanılan bir dizi (- ^öğesi . ::size_t std). union by rank bkz
  • ÜstPropertyMap üst saklamak için kullanılan bir element (- ^öğesi . element). Path compression bkz
  • FindCompressİsteğe bağlı bağımsız değişken tanımlama yöntemi bulmak. find_with_full_path_compression varsayılan here (Varsayılan olmalıdır).

Örnek:

template <typename Rank, typename Parent>
void algo(Rank& r, Parent& p, std::vector<Element>& elements)
{
 boost::disjoint_sets<Rank,Parent> dsets(r, p);
 for (std::vector<Element>::iterator e = elements.begin();
      e != elements.end(); e  )
  dsets.make_set(*e);
  ...
}

int main()
{
  std::vector<Element> elements;
  elements.push_back(Element(...));
  ...

  typedef std::map<Element,std::size_t> rank_t; // => order on Element
  typedef std::map<Element,Element> parent_t;
  rank_t rank_map;
  parent_t parent_map;

  boost::associative_property_map<rank_t>   rank_pmap(rank_map);
  boost::associative_property_map<parent_t> parent_pmap(parent_map);

  algo(rank_pmap, parent_pmap, elements);
}

Not: "Boost Özelliği Göster Kütüphane içeren bir kaç adaptörleri bu dönüştürme sık kullanılan veri yapıları uygulayan bir eşleme işlemi gibi yerleşik diziler (işaretçiler), kullanımına ve std::map, özelliği harita arayüzü"

Bu adaptörler listesi (boost gibi::associative_property_map) here bulunabilir.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • funbro1

    funbro1

    11 Aralık 2007
  • SalGames2016

    SalGames2016

    17 Kasım 2012
  • ThePhestor

    ThePhestor

    22 Mart 2011