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

Discussion in 'C++' started by Rui Maciel, Apr 6, 2010.

  1. Rui Maciel

    Rui Maciel Guest

    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
    Rui Maciel, Apr 6, 2010
    #1
    1. Advertising

  2. Rui Maciel

    Kai-Uwe Bux Guest

    Rui Maciel wrote:

    > 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
    Kai-Uwe Bux, Apr 6, 2010
    #2
    1. Advertising

  3. On Apr 6, 3:46 am, Rui Maciel <> wrote:
    > 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.
    Joshua Maurice, Apr 6, 2010
    #3
  4. Rui Maciel

    Kai-Uwe Bux Guest

    Christian Hackl wrote:

    > 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
    Kai-Uwe Bux, Apr 6, 2010
    #4
  5. Rui Maciel

    Rui Maciel Guest

    Christian Hackl wrote:

    > 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;
    }
    </source>

    > 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
    Rui Maciel, Apr 6, 2010
    #5
  6. On Apr 6, 6:46 am, Rui Maciel <> 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.

    KHD
    Keith H Duggar, Apr 6, 2010
    #6
  7. Rui Maciel

    Rui Maciel Guest

    Leigh Johnston wrote:

    > 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, Apr 6, 2010
    #7
  8. Rui Maciel

    Rui Maciel Guest

    Kai-Uwe Bux wrote:

    > 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
    Rui Maciel, Apr 6, 2010
    #8
  9. Rui Maciel

    Kai-Uwe Bux Guest

    Rui Maciel wrote:

    > Kai-Uwe Bux wrote:
    >
    >> 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.


    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, Apr 6, 2010
    #9
  10. Rui Maciel

    Kai-Uwe Bux Guest

    Leigh Johnston wrote:

    >
    >
    > "Keith H Duggar" <> wrote in message
    > news:...
    >> On Apr 6, 6:46 am, Rui Maciel <> 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
    Kai-Uwe Bux, Apr 6, 2010
    #10
  11. Rui Maciel

    Kai-Uwe Bux Guest

    Leigh Johnston wrote:

    >
    >
    > "Leigh Johnston" <> wrote in message
    > news:...
    >>
    >>
    >> "Kai-Uwe Bux" <> wrote in message
    >> news:hpg532$snl$...
    >>> Leigh Johnston wrote:
    >>>
    >>>>
    >>>>
    >>>> "Keith H Duggar" <> wrote in message
    >>>> news:601b47ca-0120-492b-ae63-

    ...
    >>>>> On Apr 6, 6:46 am, Rui Maciel <> 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)


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

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


    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.

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


    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 :-(

    >> /Leigh

    >
    > 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
    Kai-Uwe Bux, Apr 6, 2010
    #11
  12. On Apr 6, 4:55 pm, "Leigh Johnston" <> wrote:
    > "Leigh Johnston" <> wrote in message
    > > "Kai-Uwe Bux" <> wrote in message
    > >news:hpg532$snl$...
    > >> Leigh Johnston wrote:

    >
    > >>> "Keith H Duggar" <> wrote in message
    > >>>news:...
    > >>>> On Apr 6, 6:46 am, Rui Maciel <> 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
    Keith H Duggar, Apr 6, 2010
    #12
  13. Rui Maciel

    Ian Collins Guest

    On 04/ 7/10 10:04 AM, Leigh Johnston wrote:
    >
    > 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....

    --
    Ian Collins
    Ian Collins, Apr 6, 2010
    #13
  14. Rui Maciel

    James Kanze Guest

    On Apr 6, 8:15 pm, Kai-Uwe Bux <> wrote:
    > Rui Maciel wrote:
    > > Kai-Uwe Bux wrote:


    [...]
    > > 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.


    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
    James Kanze, Apr 6, 2010
    #14
  15. Rui Maciel

    James Kanze Guest

    On Apr 6, 5:51 pm, Juha Nieminen <> wrote:
    > On 04/06/2010 01:46 PM, Rui Maciel wrote:


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


    > 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
    James Kanze, Apr 6, 2010
    #15
  16. Rui Maciel

    James Kanze Guest

    On Apr 6, 11:24 pm, Ian Collins <> wrote:
    > On 04/ 7/10 10:04 AM, Leigh Johnston wrote:
    > > 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....


    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
    James Kanze, Apr 6, 2010
    #16
  17. Rui Maciel

    James Kanze Guest

    On Apr 6, 11:26 pm, "Leigh Johnston" <> wrote:
    > "Leigh Johnston" <> wrote in message


    > news:...


    [...]
    > 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.

    --
    James Kanze
    James Kanze, Apr 7, 2010
    #17
  18. On Apr 6, 5:55 pm, "Leigh Johnston" <> wrote:
    > "Kai-Uwe Bux" <> wrote in message
    > > Leigh Johnston wrote:
    > >> "Leigh Johnston" <> wrote in message
    > >>news:...

    >
    > >>> "Kai-Uwe Bux" <> wrote in message
    > >>>news:hpg532$snl$...
    > >>>> Leigh Johnston wrote:

    >
    > >>>>> "Keith H Duggar" <> wrote in message
    > >>>>> news:601b47ca-0120-492b-ae63-

    > > ...
    > >>>>>> On Apr 6, 6:46 am, Rui Maciel <> 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)

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

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

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

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

    >
    > > 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 :-(

    >
    > >>> /Leigh

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

    >
    > 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
    Keith H Duggar, Apr 7, 2010
    #18
  19. Rui Maciel

    Kai-Uwe Bux Guest

    Leigh Johnston wrote:

    >
    >
    > "Keith H Duggar" <> wrote in message
    > news:...
    >>
    >> 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 ;
    >> }
    >>

    >
    > 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
    Kai-Uwe Bux, Apr 7, 2010
    #19
  20. la 04/07/2010 12:45 AM James Kanze skribis:
    > On Apr 6, 8:15 pm, Kai-Uwe Bux <> wrote:


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


    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
    Daniel Pfeiffer, Apr 7, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Nick
    Replies:
    0
    Views:
    521
  2. Massimiliano Alberti

    Inserting an empty element in a list (STL)

    Massimiliano Alberti, Sep 24, 2003, in forum: C++
    Replies:
    3
    Views:
    411
  3. Replies:
    2
    Views:
    3,387
    Kai-Uwe Bux
    Nov 6, 2006
  4. Replies:
    10
    Views:
    684
    red floyd
    Apr 3, 2007
  5. Rui Maciel
    Replies:
    2
    Views:
    1,605
    Rui Maciel
    Dec 1, 2009
Loading...

Share This Page