Re: map vs. set (stl)
On May 24, 12:29 am, Qwavel <qwa...@gmail.com> wrote:
On May 23, 4:59 pm, Markus Schoder <a3vr6dsg-use...@yahoo.de> wrote:
On Wed, 23 May 2007 12:41:18 -0700, Qwavel wrote:
Let's say I have something like this, where 'name' is a POD type, and
'value' is a class.
std::map< name, value >
But then I realize that 'name' should actually be one of the members =
of
'value' class, so I have a redundancy. I then switch and start using
std::set< value >. To make 'value' suitable for this purpose, I make=
it
look like this...
class value {
const int name;
bool operator<( const value& rhs ) const
{ return name < rhs.name; }
void operator=( const value& rhs );
...
};
This now satisfies the requirements of a set, and it works. Great. B=
ut
I feel as though I have really strayed far from the idea of a set. F=
or
example, the key part of my value is constant, but the whole value is
not.
Should I really be using a set like this?
The problem you might be facing is that you cannot (without casting)
modify the objects in the set through a set iterator. A set iterator is
basically always a const iterator to prevent breaking the ordering of t=
he
set.
Yes, that is what you would expect.
It depends on where you are coming from. There was extensive
discussion (and disagreement) about this in the committee;
people with a data base background tend to think of set and
multiset as a keyed table, in which case, one field is the key
(and cannot be modified), and the others are not (and can be
modified). Others see it more as an ordered set, in which any
modifications might perturbe the ordering criteria.
The final decision went with the second interpretation, probably
mainly because there was no way to specify what the fields are,
which one is the key, and to make it unmodifiable. The current
interface basically provides no way of only being able to modify
part of an element. The "official" solution for this is to
extract the element from the set (removing it), modify it, and
then reinsert it.
If I were modeling a data base, I'd probably do something along
the lines of what you propose, with an element type in which the
key fields are declared const. Of course (at least according to
the original standard), you cannot instantiate a container over
a class type with constant members (and recent versions of g++
complain if you try to do so), you have to resort to a set of
pointers---which also solves the problem of const-ness:-) (but
introduces one of lifetime management).
Most of the time, however, I'll just use map, and live with the
duplication. Especially since set or multiset require a
complete element type for find, where as map just requires the
key type. I'm not adverse to using a set of pointers for
secondary keys, however. (In such a case, you might arrange
for the primary key to be something cheap to duplicate, like an
int, and use more expensive types, like string, for the
secondary keys.)
However, in my STL, the set::find function returns a non-const
iterator, so I can modify the elements of the set.
The fact that the iterator is non-const doesn't necessarily mean
that you can modify values through it. The only versions of the
standard I have handy are the original (1998) and the latest
draft. In the latest draft, it explicitly says that "For
associative containers where the value type is the same as the
key type, both iterator and const_iterator are constant
iterators. It is unspecified whether or not iterator and
const_iterator are the same type." I believe that this text was
already present in the 2003 revised version of the standard, but
I don't have that here to verify.
I mentionned before that this issue has been the subject of much
discussion in the committee. Regretfully, most of that
discussion was after the publication of the original standard,
in response to defect reports. The original standard says
almost nothing about this, and early implementations varied.
Today, of course, the standard says what it says, but for
implementations which originally allowed modification, given the
choice between breaking existing user code or strictly adhering
to the (from their point of view modified) standard, it's
understandable that they are not rushing to change.
Of course, I must
be careful not to change the key value.
I'm using the STL that comes with MS VC8. I don't know if this
behavior conforms to the standard or not.
If you can modify the element through an iterator returned by
find, the implementation does not conform with the proposed
draft, and I don't think it conforms with the 2003 version of
the standard. The original standard was vague enough that just
about anything conformed, however, and even the intent was not
very clear. In this case, MS implemented a very reasonable
(perhaps the most reasonable) interpretation of the original
standard, and is now hesitant about updating to the current
standard, for fear of breaking existing user code. (Or maybe
for other, less laudable reasons, but I prefer always to give
the benefit of the doubt.)
Note too that if the instantiation type has const members, the
code has always had undefined behavior, and has never been
officially supported, by MS or by anyone else, even though it
probably worked just about everywhere. This requirement has
been lifted in the latest draft, however. (The requirement
stems from the requirement in the original standard that the
instantiation type of all containers be assignable; a class with
const elements isn't assignable. In practice, assignment isn't
necessary for node based containers like set or list, however,
and the current draft removes that requirement from them.)
--
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