Re: Sets in C++
On Dec 28, 5:46 pm, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
Aaron Gray wrote:
I want to represent a set in C++ that is indexed by number.
Indexed? Do you mean that the elements of the set are
integers?
I need to be able to do unions and stuff between two
existing sets forming a new set. I have looked at 'bitset'
but its a bit lame then theres vector<bool> but I cannot
find ant good documentation on either.
The standard documents both.
But finding where isn't always that obvious:-).
Help and suggestions most welcome,
There is a fundamental difference between sets of
(comparatively small) known maximum size and sets of arbitrary
large size. The container std::bitset<> is for the former,
the container std::vector<bool> is of questionable value, and
std::set<int> is the standard choice when the size is unknown.
I think it's just a wording issue, and maybe I'm
misunderstanding your English, but don't you mean that the
difference depends on the cardinality of universe over which the
sets are formed. Even if the maximum size of the set is 10,
std::bitset<> won't work without a lot of external support if it
is a set of cities in the world.
Generally, if the universe is that of small natural numbers, or
can easily be mapped to small natural numbers (countries in the
European Union, for example), then something like std::bitset<>
is appropriate. Note, however, that this requires that the
upper bound be known at compile time. I still use my
pre-standard BitVector and DynamicBitVector classes (which
support the set operations as overloaded operators); the latter
has no fixed upper bound, but the internal implementation is
still that of a bit vector. I find it useful for things like
parser states, etc. where realistically, you have a small set of
natural numbers, but you don't know the actual upper bound until
you're finished. For more general use, of course, either
std::set or a sorted std::vector are the answer. (I find my use
split more or less evenly between the two.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34