stl::map: return default value without inserting a new element?

[Rui Maciel]

When using STL's map container, if operator[] is used to access the value associated with a
given key which wasn't inserted then a new key:value pair will be created and a reference to
the value will be returned. This means that, although operator[] is a convenient way to add
new key:value pairs to a map, it may end up needlessly adding useless key:value pairs into the
map.

In order to avoid wasting resources populating a map with useless key:value pairs, is there a
clean, unencumbered way to get the value associated with a given key without being forced to
insert new elements or even resort to multiple lines of code? The closest thing I saw was the
map::find() method, but I believe that ends up forcing to write code to compare the given
iterator to map::end() and, if it matches, return a default value.

Is there a simpler way to do this?


Rui Maciel

 

[Kai-Uwe Bux]

When using STL's map container, if operator[] is used to access the value
associated with a given key which wasn't inserted then a new key:value
pair will be created and a reference to
the value will be returned. This means that, although operator[] is a
convenient way to add new key:value pairs to a map, it may end up
needlessly adding useless key:value pairs into the map.

In order to avoid wasting resources populating a map with useless
key:value pairs, is there a clean, unencumbered way to get the value
associated with a given key without being forced to
insert new elements or even resort to multiple lines of code? The closest
thing I saw was the map::find() method, but I believe that ends up forcing
to write code to compare the given iterator to map::end() and, if it
matches, return a default value.

Is there a simpler way to do this?

Not really. You can, of course, wrap this little thing into a dictionary
class, which internally uses a map and find(). But that is not provided by
the standard. Here is what I use:


template < typename KeyType, typename MappedType >
class dictionary {

typedef std::map< KeyType, MappedType > map_type;

map_type the_map;
MappedType the_default;

public:

typedef KeyType key_type;
typedef MappedType mapped_type;

dictionary ( mapped_type const & val = mapped_type() )
: the_map ()
, the_default ( val )
{}

dictionary & insert ( key_type const & key,
mapped_type const & val ) {
the_map[ key ] = val;
return ( *this );
}

dictionary & erase ( key_type const & key ) {
the_map.erase( key );
return( *this );
}

mapped_type const &
operator() ( key_type const & key ) const {
typename map_type::const_iterator iter =
the_map.find( key );
if ( iter == the_map.end() ) {
return ( the_default );
}
return ( iter->second );
}

};


The insert() and erase() method allow for chaining.


Best

Kai-Uwe Bux

 

[Joshua Maurice]

When using STL's map container, if operator[] is used to access the value associated with a
given key which wasn't inserted then a new key:value pair will be created and a reference to
the value will be returned.  This means that, although operator[] is a convenient way to add
new key:value pairs to a map, it may end up needlessly adding useless key:value pairs into the
map.

In order to avoid wasting resources populating a map with useless key:value pairs, is there a
clean, unencumbered way to get the value associated with a given key without being forced to
insert new elements or even resort to multiple lines of code?  The closest thing I saw was the
map::find() method, but I believe that ends up forcing to write code to compare the given
iterator to map::end() and, if it matches, return a default value.

Is there a simpler way to do this?

Exactly what kind of interface do you want? You want it in one line,
and this seems kind of short for error handling, including errors such
as "entry not found". If you want to simply take a default action on
"entry not found" (such as die), you could write a simple helper
function yourself which returns map::find after doing the error
checking. If you don't want error checking, then just use
std::map::find directly. The only functions in std::map which do a
default action are operator[] and insert, which insert a new entry if
it's not already present.

 

[Kai-Uwe Bux]

Rui Maciel ha scritto:

In order to avoid wasting resources populating a map with useless
key:value pairs, is there a clean, unencumbered way to get the value
associated with a given key without being forced to insert new elements
or even resort to multiple lines of code?

But shouldn't you rather view it as an error to access an element which
does not exist? Perhaps what you should do is access elements with a
function like this:

template <class KeyType, class MappedType>
MappedType const &get(std::map<KeyType, MappedType> const &map, KeyType
const &key)
{
std::map<KeyType, MappedType>::const_iterator find_iter =
map.find(key);

assert(find_iter != map.end());
return find_iter->second;
}

(Note how this, in contrast to operator[], can be used with a const
std::map as well.)

Then make sure outside code accesses only those elements which exist. It
seems a more robust solution to me than relying on default values being
returned in case the key does not exist. Otherwise, what happens when
the default value happens to be one of the actual values in the map? You
won't be able to distinguish between legitimate access and error cases.

Hitting a value not stored in the table does not always indicate an error. I
recently had an interactive program that was mainly table driven. The key
data structure had the type:

dictionary< char, action >

and the default action was null_op. The main loop would just wait until the
user presses a key and execute the corresponding action. Only keys that
actually do something need to be stored, and all others default to null_op.

In short: whether asking for a non-stored value is an error depends on the
context.


Best

Kai-Uwe Bux

 

[Rui Maciel]

But shouldn't you rather view it as an error to access an element which
does not exist?

Not necessarily. In this case it would be nice if it behaved just as operator[] minus the
new key:value insertion, which means returning the value if a key:value pair was found and
otherwise return a default value.

Perhaps what you should do is access elements with a
function like this:

template <class KeyType, class MappedType>
MappedType const &get(std::map<KeyType, MappedType> const &map, KeyType
const &key)
{
std::map<KeyType, MappedType>::const_iterator find_iter =
map.find(key);

assert(find_iter != map.end());
return find_iter->second;
}

(Note how this, in contrast to operator[], can be used with a const
std::map as well.)

That's not quite it. I was looking for a STL way to do something such as:

<source lang=cpp>
template <class KeyType, class MappedType>
MappedType const &get(std::map<KeyType, MappedType> const &map, KeyType
const &key)
{
std::map<KeyType, MappedType>::const_iterator find_iter =
map.find(key);
if(find_iter == map.end())
return MappedType();
else
return find_iter->second;
}

Then make sure outside code accesses only those elements which exist. It
seems a more robust solution to me than relying on default values being
returned in case the key does not exist. Otherwise, what happens when
the default value happens to be one of the actual values in the map?

In my case there's no problem with that.

You
won't be able to distinguish between legitimate access and error cases.

In my case those aren't errors, which means this is a non-issue.


Rui Maciel

 

[Keith H Duggar]

In order to avoid wasting resources populating a map with
useless key:value pairs, is there a clean, unencumbered way
to get the value associated with a given key without being
forced to insert new elements or even resort to multiple
lines of code? The closest thing I saw was the map::find()
method, but I believe that ends up forcing to write code to
compare the given iterator to map::end() and, if it matches,
return a default value.

Is there a simpler way to do this?

I find these two functions (including their general semantics)
and variants of them exceedingly useful

template < class K, class V, class C, class A>
V
getOrZero (
std::map<K,V,C,A> const & m
, K const & k
) {
typename std::map<K,V,C,A>::const_iterator i = m.find(k) ;
return i != m.end() ? i->second : V() ;
}

template < class K, class V, class C, class A>
V &
getOrMake (
std::map<K,V,C,A> & m
, K const & k
) {
return m[k] ;
}

for all types of containers including STL and custom ones.

KHD

 

[Rui Maciel]

If you are not happy with maps' interface then you can augment its
interface through derivation, see
http://www.i42.co.uk/stuff/mutable_set.htm

I was trying to avoid that. I assumed that this sort of stuff was already provided. Oh
well...


Thanks for the help,
Rui Maciel

 

[Rui Maciel]

Not really. You can, of course, wrap this little thing into a dictionary
class, which internally uses a map and find(). But that is not provided by
the standard. Here is what I use:

<snip code/>

That's exactly what I was looking for. Even the use of operator() matches what I expected
from std::map. Is there a reason why this feature isn't already implemented?


Thanks for the help,
Rui Maciel

 

[Kai-Uwe Bux]

<snip code/>

That's exactly what I was looking for.

That's nice to hear.

Even the use of operator() matches what I expected
from std::map. Is there a reason why this feature isn't already
implemented?

I can only offer conjectures. First, storing the default value is an
overhead unnecessary for most applications of std::map<>. Second, and
probably more serious a consequence: It would be somewhat cumbersome to use
the modified map<> template with value_types that don't support default
construction because, in those cases, you would have to designate a
not_found_value manually.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

In order to avoid wasting resources populating a map with
useless key:value pairs, is there a clean, unencumbered way
to get the value associated with a given key without being
forced to insert new elements or even resort to multiple
lines of code? The closest thing I saw was the map::find()
method, but I believe that ends up forcing to write code to
compare the given iterator to map::end() and, if it matches,
return a default value.

Is there a simpler way to do this?

I find these two functions (including their general semantics)
and variants of them exceedingly useful

template < class K, class V, class C, class A>
V
getOrZero (
std::map<K,V,C,A> const & m
, K const & k
) {
typename std::map<K,V,C,A>::const_iterator i = m.find(k) ;
return i != m.end() ? i->second : V() ;
}

template < class K, class V, class C, class A>
V &
getOrMake (
std::map<K,V,C,A> & m
, K const & k
) {
return m[k] ;
}

for all types of containers including STL and custom ones.

These free functions can have their uses (they certainly save typing at
least) but I feel they may detract from good iterator based design.

I am always eager to see new design ideas, but I have some trouble picturing
an iterator to iterate over keys not in the table and providing default
values for their un-tabulated value. Could you please flesh out what you
have in mind?


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Leigh Johnston wrote:



news:601b47ca-0120-492b-ae63- (e-mail address removed)...
In order to avoid wasting resources populating a map with
useless key:value pairs, is there a clean, unencumbered way
to get the value associated with a given key without being
forced to insert new elements or even resort to multiple
lines of code? The closest thing I saw was the map::find()
method, but I believe that ends up forcing to write code to
compare the given iterator to map::end() and, if it matches,
return a default value.

Is there a simpler way to do this?

I find these two functions (including their general semantics)
and variants of them exceedingly useful

template < class K, class V, class C, class A>
V
getOrZero (
std::map<K,V,C,A> const & m
, K const & k
) {
typename std::map<K,V,C,A>::const_iterator i = m.find(k) ;
return i != m.end() ? i->second : V() ;
}

template < class K, class V, class C, class A>
V &
getOrMake (
std::map<K,V,C,A> & m
, K const & k
) {
return m[k] ;
}

for all types of containers including STL and custom ones.


These free functions can have their uses (they certainly save typing at
least) but I feel they may detract from good iterator based design.

I am always eager to see new design ideas, but I have some trouble
picturing
an iterator to iterate over keys not in the table and providing default
values for their un-tabulated value. Could you please flesh out what you
have in mind?


Best

Kai-Uwe Bux

These free functions seem mainly good for saving some typing for the
use-case you describe (returning a default if element is not in a
container) and said use-case is not a particularly common use-case (not
in my code anyway)

Just a nit, but context should be given: it happens to be the use case,
about which the OP was asking.

Now why would one use them "all over your code" if the use case is not
common? It's not the tools fault to addresses a specific need.

Agreed, but if that is the main criticism, maybe you could have said so in
the first place. The way you put it and given the context, I got my hopes up
to see a new design idea for the OP's problem based on iterators :-(

To be fair I should have said "less useful" rather than not useful at all
but remember searching the unordered containers is usually linear
complexity which should be borne in mind and increased iterator usage in a
design my reduce the need for searching and increased iterator usage
should lessen the need for these free functions.

True: using iterators, one can remember information already obtained. On the
other hand, the containers differ vastly in their iterator-invalidation
rules. At the very least the free function from above can reduce development
time for prototyping (and if profiling shows that there is no performance
problem, why change it).


Best

Kai-Uwe Bux

 

[Keith H Duggar]

Leigh Johnston wrote:
In order to avoid wasting resources populating a map with
useless key:value pairs, is there a clean, unencumbered way
to get the value associated with a given key without being
forced to insert new elements or even resort to multiple
lines of code? The closest thing I saw was the map::find()
method, but I believe that ends up forcing to write code to
compare the given iterator to map::end() and, if it matches,
return a default value.
Is there a simpler way to do this?
I find these two functions (including their general semantics)
and variants of them exceedingly useful
template < class K, class V, class C, class A>
V
getOrZero (
std::map<K,V,C,A> const & m
, K const & k
) {
typename std::map<K,V,C,A>::const_iterator i = m.find(k) ;
return i != m.end() ? i->second : V() ;
}
template < class K, class V, class C, class A>
V &
getOrMake (
std::map<K,V,C,A> & m
, K const & k
) {
return m[k] ;
}
for all types of containers including STL and custom ones.
These free functions can have their uses (they certainly save typing at
least) but I feel they may detract from good iterator based design.
I am always eager to see new design ideas, but I have some trouble
picturing
an iterator to iterate over keys not in the table and providing default
values for their un-tabulated value. Could you please flesh out what you
have in mind?
Best
Kai-Uwe Bux

These free functions seem mainly good for saving some typing for the
use-case you describe (returning a default if element is not in a
container) and said use-case is not a particularly common use-case (not in
my code anyway) and writing binary functions and using them all over your
code even though one of them only addresses an uncommon use-case is not
necessarily a good thing. In other words 99% of the time you will be
calling getOrMake which on its own seems rather pointless and less useful
for the unordered containers that offer more than one way of "making"
elements (push_front, push_back, insert) rendering the claim that such
functions are useful for all the STL containers false.

To be fair I should have said "less useful" rather than not useful at all
but remember searching the unordered containers is usually linear complexity
which should be borne in mind and increased iterator usage in a design my
reduce the need for searching and increased iterator usage should lessen the
need for these free functions.

In the case of a vector, the key is the index. You do not search
it, you simply access the element in constant time (unless resize
is needed for a getOrMake). Below is one the getOrMake variants I
use for vector:

template < class V, class A>
V &
getOrMake (
std::vector<V,A> & v
, size_t const & k
) {
if ( k < v.size() ) {
return v[k] ;
} else {
v.resize(k+1) ;
return v[k] ;
}
}

Arguing about how "common" a use case is based on your personal
code is a course myopic and irrelevant.

As to detracting from iterator based designs, of course one
should not become blinded or obsessed by any particular tool
INCLUDING iterators. And I share some of your misgiving when
it comes to noobs falling astray. But, I don't see that as
sufficient reason to chill the sharing of ideas.

KHD

 

[Ian Collins]

Wow, I think I have found an interesting VC++ bug, VC++ lets you use the
"default" keyword as a variable name!

As a constant? That would make for an interesting switch statement....

 

[James Kanze]

[...]

I can only offer conjectures. First, storing the default value
is an overhead unnecessary for most applications of
std::map<>. Second, and probably more serious a consequence:
It would be somewhat cumbersome to use the modified map<>
template with value_types that don't support default
construction because, in those cases, you would have to
designate a not_found_value manually.

Most likely, it was simply that they had to choose some
behavior, and since creating a new element is what AWK, perl and
a number of other programs do... It has the disadvantage that
you can't use [] on a const map, in addition to requiring a
default constructor for the object.

My initial associative arrays (hash tables) had the same
behavior, but over time, the problems with const made me change.
My current version returns a pointer, rather than a reference,
with a null pointer if the element isn't found. Which isn't
always the best solution either---I'm fairly convinced that
there is no best solution, and whatever you choose will be less
than ideal for some applications.

 

[James Kanze]

On 04/06/2010 01:46 PM, Rui Maciel wrote:

How else do you suggest std::map would signal the calling code
that the element did not exist?

Inserting and returning a default value doesn't signal the
calling code that the element doesn't exist. There are a number
of different possible solutions:
-- Return a pointer, returning NULL if the element isn't found.
-- Return a Faillbile.
-- Throw an exception if the element isn't found.
-- Provide a "contains" function, returning true or false, and
have it as a precondition to [].
-- The current solution.

And probably others. Which one is "best" depends on the
application.

 

[James Kanze]

As a constant? That would make for an interesting switch
statement....

Since it seems to be able to distinguish between default as a
variable and default as a switch label, it might also be able to
distinguish between 'case default:' and 'default:'. (I don't
know. I haven't tried it.)

I stumbled upon the bug myself last week. Purely by accident,
in some code that's been around for a while. And which is
scheduled to be ported to Unix shortly. I thought I was
seeing things at first.

For the moment, default is the only keyword I've seen with this
characteristic.

 

[James Kanze]

"Leigh Johnston" <[email protected]> wrote in message

news:[email protected]...

[...]

The VC++ compiler's tokenizer must be quite dodgy if it
doesn't treat keywords as tokens! Perhaps I am just being too
naive not ever having implemented a compiler myself (just a
basic script engine).

It's somewhat surprising, but some time in the past, Microsoft
was experimenting with context dependent keywords, as a means of
introducing new keywords without breaking existing code. I
think they even vaguely suggested something along these lines
before the committee, but drew back before the enormous
resistence displayed by other vendors (and users).

Technically, it requires some additional work, in order to make
the scanner aware of the current parser context, but it's not
that difficult. On the other hand, carried to extremes, it can
make reading the code more difficult. I once worked on a
dialect of Basic which would allow something like:
IF IF = THEN THEN THEN = ELSE ELSE ELSE = If
Personally, it's not a route I'd like to follow.

 

[Keith H Duggar]

Leigh Johnston wrote:
(e-mail address removed)...
In order to avoid wasting resources populating a map with
useless key:value pairs, is there a clean, unencumbered way
to get the value associated with a given key without being
forced to insert new elements or even resort to multiple
lines of code? The closest thing I saw was the map::find()
method, but I believe that ends up forcing to write code to
compare the given iterator to map::end() and, if it matches,
return a default value.
Is there a simpler way to do this?
I find these two functions (including their general semantics)
and variants of them exceedingly useful
template < class K, class V, class C, class A>
V
getOrZero (
std::map<K,V,C,A> const & m
, K const & k
) {
typename std::map<K,V,C,A>::const_iterator i = m.find(k) ;
return i != m.end() ? i->second : V() ;
}
template < class K, class V, class C, class A>
V &
getOrMake (
std::map<K,V,C,A> & m
, K const & k
) {
return m[k] ;
}
for all types of containers including STL and custom ones.
These free functions can have their uses (they certainly save typing
at
least) but I feel they may detract from good iterator based design.
I am always eager to see new design ideas, but I have some trouble
picturing
an iterator to iterate over keys not in the table and providing default
values for their un-tabulated value. Could you please flesh out what
you
have in mind?
Best
Kai-Uwe Bux
These free functions seem mainly good for saving some typing for the
use-case you describe (returning a default if element is not in a
container) and said use-case is not a particularly common use-case (not
in my code anyway)

Just a nit, but context should be given: it happens to be the use case,
about which the OP was asking.

Now why would one use them "all over your code" if the use case is not
common? It's not the tools fault to addresses a specific need.

Agreed, but if that is the main criticism, maybe you could have said so in
the first place. The way you put it and given the context, I got my hopes
up
to see a new design idea for the OP's problem based on iterators :-(

True: using iterators, one can remember information already obtained. On
the
other hand, the containers differ vastly in their iterator-invalidation
rules. At the very least the free function from above can reduce
development
time for prototyping (and if profiling shows that there is no performance
problem, why change it).

Not sure I can suggest an improvement using iterators however I can suggest
one minor improvement to getOrZero:

template < class K, class V, class C, class A>
const V&
getOrZero (
std::map<K,V,C,A> const & m
, K const & k
) {
static const V default;
typename std::map<K,V,C,A>::const_iterator i = m.find(k) ;
return i != m.end() ? i->second : default ;

}

We no longer have to make a (possibly RVO optimized) copy of the container
element if we don't need a copy and if getOrZero is called many times we
only ever create one default element.

However it also makes thread-safety more difficult for
clients of getOrZero and therefore IMO is not appropriate
for such a library function. Instead I use an overload of
getOrZero which follows the Tao of POSIX reentrant support:

template < class K, class V, class C, class A >
V const &
getOrZero (
std::map<K,V,C,A> const & m
, K const & k
, V const & zero
) {
typename std::map<K,V,C,A>::const_iterator i = m.find(k) ;
return i != m.end() ? i->second : zero ;
}

That overload also provides some useful flexibility with
the "zero" value. For example with number I often find it
useful to use -1 or NaN instead of 0.

I've also experimented from time to time with versions of
them which take callbacks instead. For example

template < class K, class V, class C, class A, class F >
V &
getOrMake (
std::map<K,V,C,A> & m
, K const & k
, F const & f
) {
typename std::map<K,V,C,A>::iterator i = m.find(k) ;
if ( i != m.end() ) {
return i->second ;
} else {
i = m.insert(make_pair(k,f())) ;
return i->second ;
}
}

which allows for interesting things. But for the most part
I've found the simple value based versions the more useful.

KHD

 

[Kai-Uwe Bux]

Unless I am missing something obvious I am fairly sure that most
implementations of map are not thread-safe so calling find() in your
version above is also not thread-safe (one thread could modify the map
whilst the other thread is searching it) so a lock must still be acquired
making adding a zero parameter instead of using a shared static seem
pointless (assuming I am not missing something obvious).

Well, if you have variables of type map<K,V>, a straight forward way to
synchronize threads would be to have one mutex per variable and each thread
operating (e.g., via getOrZero()) on a variable locks it. Nonetheless,
several threads can concurrently execute getOrZero(), just for different
maps.


best

Kai-Uwe Bux

 

[Daniel Pfeiffer]

la 04/07/2010 12:45 AM James Kanze skribis:

Most likely, it was simply that they had to choose some
behavior, and since creating a new element is what AWK, perl and
a number of other programs do... It has the disadvantage that
you can't use [] on a const map, in addition to requiring a
default constructor for the object.

That's not true (scalar return how many slots are filled):

$ perl -e 'my %map; $_ = $map{not_there}; print scalar %map, "\n"'
0

However, if you go deeper through an inexistant ref, then it is annoyingly
autovivified:

$ perl -e 'my %map; $_ = $map{not_there}[0]; print scalar %map, "\n"; print
scalar @{$map{not_there}}, "\n"'
1/8
0

Even the array got created and stored there, but despite accessing its 1st
element, its length remains 0 as the 2nd print showed.

regards
Daniel