BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List

Difference (from prior major revision) (author diff)

Changed: 21,34c21
bool next_SubSet?(SubSet?& s)
if (s._cont_iter.size() == s._L - s._F)
return false;
SubSet?::Iter it = s._F;
if (s.cont.size() == 0 || s.cont[0] != it)
SubSet?::Iter it2 = it;
int i = 0;
while (it2++ == s.cont[i++]);
s.cont.erase(0, i);//erase [it..it2)
return true;
bool next_SubSet?(SubSet?& s);

power set algorithm
Hmm, what kind of interface would you suggest here?
I think it should be like std::next_permutation, or even [SuperSets iterator]? Maybe like that
template<class Iter, class ContIter = std::vector<Iter> >//maybe std::set
class SubSet
   SubSet(Iter F, iter L);//empty superset of container [F..L)
   SubSet(list<Iter>);//superset from set of iterators
//there is some ambiguity so, maybe it must be make_superset, 
//make_superset_from_iterators, make superset_from_sorted_iterators
   bool contains_iter(Iter x);
//bool contains(typename Iter::value_type x); //don't know if set was sorted, maybe require that?
   ContIter::const_iterator begin() const;//allow iterating
   ContIter::const_iterator end() const;//allow iterating
bool next_SubSet(SubSet& s);
//of course there must be something like SubSet, based on bitset,
//as a separate class or as specialization for small sets
While writing I got idea: we need SubSet? class, not SuperSet? :) However interface is still very blurry :)
Or like that bool next_subset(_F1, _L1, _F2&, _L2&);
 Where [F1, L1) - Set
 [F2, L2) - SubSet?, i.e. container of Set::const_iterator
 F2 must be insert_iterator
 [_F2 _L2) is sorted
 true iff next after 2 in lexicographical order subset of 1 exists
 if result==true [F2 L2) is next subset, else F2==L2

But still i don't think it very usefull, it's always easier to use bit-mask to represent subset, and iterate from 0 to 2^size - 1 to get all subsets.

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited January 10, 2007 4:15 pm (diff)
Disclaimer: This site not officially maintained by Boost Developers