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 ]