map vs. set (stl)

[Qwavel]

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.
But I feel as though I have really strayed far from the idea of a
set. For example, the key part of my value is constant, but the whole
value is not.

Should I really be using a set like this?

 

[Fei Liu]

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.
But I feel as though I have really strayed far from the idea of a
set. For example, the key part of my value is constant, but the whole
value is not.

Should I really be using a set like this?

Sounds like you just need a vector...

F

 

[John Harrison]

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.
But I feel as though I have really strayed far from the idea of a
set. For example, the key part of my value is constant, but the whole
value is not.

Should I really be using a set like this?

I think it's always worth refining your design so that it's natural, so
it feels right. You seem to be thinking about the value class solely in
terms of it's role within the set. Try thinking about the value class
independently instead of how you might be using it in a map or set.

You might find that a custom comparator for a set is the way to go.

john

 

[Markus Schoder]

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. But
I feel as though I have really strayed far from the idea of a set. For
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 the
set.

 

[Qwavel]

Sounds like you just need a vector...

F

But the set will be sorted so it (like the map) has faster random
lookup then the vector.
OP.

 

[Qwavel]

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 the
set.

Yes, that is what you would expect.

However, in my STL, the set::find function returns a non-const
iterator, so I can modify the elements of the set. 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.

 

[Markus Schoder]

Yes, that is what you would expect.

However, in my STL, the set::find function returns a non-const iterator,
so I can modify the elements of the set. 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.

The current wording of the standard surprisingly _requires_ this behavior
but there is a defect report pending (103) that proposes to change this
and make keys in associative containers immutable.

 

[Qwavel]

The current wording of the standard surprisingly _requires_ this behavior
but there is a defect report pending (103) that proposes to change this
and make keys in associative containers immutable.

Yikes! That change would break some of my code.

Does that mean that the best solution for me is to use
std::map<key,value>, in spite of the fact that I would then have two
copies of the key (since 'value' contains the key)?

It would not be efficient for me to erase and re-add the value just to
modify it.

Qwavel (OP)

 

[James Kanze]

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]

The current wording of the standard surprisingly _requires_ this behavior
but there is a defect report pending (103) that proposes to change this
and make keys in associative containers immutable.

The wording in the original standard required [multi]set::find()
on a non-const object to return a type [multi]set::iterator. It
did NOT require that you be able to modify the object through
the (non-const) iterator, and early implementations varied, some
using exactly the same type for iterator and const_iterator.

The discussions on this subjet were quite long, but the final
decision is that trying to modify the element through the
iterator, even if it was non-const, is undefined behavior. The
current draft has been modified to reflect this---I think it is
also in TC1 (and thuse the 2003 version of the standard).

 

[James Kanze]

On May 23, 7:39 pm, Markus Schoder <[email protected]> wrote:

[...]

Yikes! That change would break some of my code.

It's not so much a change as a clarification.

Does that mean that the best solution for me is to use
std::map<key,value>, in spite of the fact that I would then have two
copies of the key (since 'value' contains the key)?

It depends. If key isn't expensive to duplicate, why not? It
has the advantage that you can look up with just a key; you
don't have to construct a complete value.

The alterative would be a set of pointers:
std::set< value*, ValueKeyCmp >
where ValueKeyCmp is something like:

struct ValueKeyCmp
{
bool operator()( value const* a, value const* b ) const
{
return a->name() < b->name() ;
}
} ;

This would also allow using const members for the elements in
the key.

 

[Qwavel]

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.)


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.


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:[email protected]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Thanks for the detailed reponse. Very helpful and interesting.

 

[Markus Schoder]

The current wording of the standard surprisingly _requires_ this
behavior but there is a defect report pending (103) that proposes to
change this and make keys in associative containers immutable.

The wording in the original standard required [multi]set::find() on a
non-const object to return a type [multi]set::iterator. It did NOT
require that you be able to modify the object through the (non-const)
iterator, and early implementations varied, some using exactly the same
type for iterator and const_iterator.

The current wording in the standard says that X::iterator is an iterator
pointing to T and X::const_iterator is an iterator pointing to const T
where X is the container and T its value_type. This implies that
implementations where X::const_iterator and X::iterator are the same type
are non-conforming. Also modifications through X::iterator are possible
since the value_type T must also be assignable.

The discussions on this subjet were quite long, but the final decision
is that trying to modify the element through the iterator, even if it
was non-const, is undefined behavior. The current draft has been
modified to reflect this---I think it is also in TC1 (and thuse the 2003
version of the standard).

It is not in the 2003 version.

 

[Branimir Maksimovic]

But the set will be sorted so it (like the map) has faster random
lookup then the vector.
OP.

You will be surprised that sorted vector and lower_bound
are almost always better choice. Lower memory footprint
and faster lookup.
Only if there are many inserts/updates/removes on big vector
set/map is better choice.

Greetings, Branimir.