Topic: bool is_a_subset_of( const std::set<T>& superset, const std::set<T>& subset ) function, did anyone meet one?


Author: "Ilya Besov" <bes@ultersys.ru>
Date: Wed, 28 Aug 2002 12:58:57 CST
Raw View
Hi,

I've spent some time today trying to find an algorithm to get whether all
the elements of one set are included into another one. I found nothing
and had to do it manually then. It seems to be strange though that a
function
like that does not exist. I would appreciate any leads.

Thanks in advance.
Regards
Ilya


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: "Ken Alverson" <Ken@Alverson.net>
Date: Wed, 28 Aug 2002 14:05:06 CST
Raw View
"Ilya Besov" <bes@ultersys.ru> wrote in message
news:aki9bb$vjk$1@gavrilo.mtu.ru...
> Hi,
>
> I've spent some time today trying to find an algorithm to get whether
all
> the elements of one set are included into another one. I found nothing
> and had to do it manually then. It seems to be strange though that a
> function
> like that does not exist. I would appreciate any leads.

You can approximate it with:

set_difference(
    Subset.begin(),Subset.end(),
    Superset.begin(),Superset.end(),
    inserter(resultset,resultset.begin())
    );

If Subset is a subset of Superset, resultset will be empty, otherwise it
will contain the elements preventing it from being a subset.  If Subset
actually is a subset of Superset, this should be approximately as
efficient as a dedicated routine.  If Subset is not a subset, it is
potentially slower since (a) it cannot early-out and (b) time will be
spent building the resultset which will just be discarded.  If you do go
this route, you should probably use a vector for the result set, as it
will have the least overhead.  In that case the whole process is
amortized linear time over the sizes of the input sets.

Ken


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: "Ken Alverson" <Ken@Alverson.net>
Date: Wed, 28 Aug 2002 16:27:22 CST
Raw View
"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:1030562487.727262@master.nyc.kbcfp.com...
> Ilya Besov wrote:
> > It seems to be strange though that a function
> > like that does not exist.
>
> It does exist. It's called std::includes.

Huh...there it is.  Why doesn't it have a "set_" prefix like all the
other set algorithms?

Ken


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: "Ilya Besov" <bes@ultersys.ru>
Date: Thu, 29 Aug 2002 06:34:45 CST
Raw View
> It does exist. It's called std::includes.
>

Thanks a lot, includes() must be exactly what I need,
Mark Nelson book describes it so at least. I was confused by the
lexicographical_compare-order-like example from MSDN. Sorry about a dummy
question.

Thanks again
Regards
Ilya


P.S. MSDN July 2000 example
Program Output is:
CartoonVector { Aladdin, Goofy, Jasmine, Mickey, Minnie,  }
CartoonDeque { Aladdin, Goofy, Jasmine,  }
CartoonVector includes CartoonDeque





---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]