«

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 <rui.mac...@gmail.com> 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

On Apr 6, 4:55 pm, "Leigh Johnston" <le...@i42.co.uk> wrote:
> "Leigh Johnston" <le...@i42.co.uk> wrote in message
> > "Kai-Uwe Bux" <jkherci...@gmx.net> wrote in message
> >news:hpg532$snl$...
> >> Leigh Johnston wrote:
>
> >>> "Keith H Duggar" <dug...@alum.mit.edu> wrote in message
> >>>news:601b47ca-0120-492b-ae63-...
> >>>> On Apr 6, 6:46 am, Rui Maciel <rui.mac...@gmail.com> 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

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

On Apr 6, 8:15 pm, Kai-Uwe Bux <jkherci...@gmx.net> 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

On Apr 6, 5:51 pm, Juha Nieminen <nos...@thanks.invalid> 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

On Apr 6, 11:24 pm, Ian Collins <ian-n...@hotmail.com> 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

On Apr 6, 11:26 pm, "Leigh Johnston" <le...@i42.co.uk> wrote:
> "Leigh Johnston" <le...@i42.co.uk> wrote in message

> news:TL2dnXDP0tN-...

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

On Apr 6, 5:55 pm, "Leigh Johnston" <le...@i42.co.uk> wrote:
> "Kai-Uwe Bux" <jkherci...@gmx.net> wrote in message
> > Leigh Johnston wrote:
> >> "Leigh Johnston" <le...@i42.co.uk> wrote in message
> >>news: om...
>
> >>> "Kai-Uwe Bux" <jkherci...@gmx.net> wrote in message
> >>>news:hpg532$snl$...
> >>>> Leigh Johnston wrote:
>
> >>>>> "Keith H Duggar" <dug...@alum.mit.edu> wrote in message
> >>>>> news:601b47ca-0120-492b-ae63-
> > b93967460...@x7g2000vbc.googlegroups.com...
> >>>>>> On Apr 6, 6:46 am, Rui Maciel <rui.mac...@gmail.com> 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

Leigh Johnston wrote:

>
>
> "Keith H Duggar" <> wrote in message
> news:4be295e6-b63f-4876-a796-...
>>
>> 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

la 04/07/2010 12:45 AM James Kanze skribis:
> On Apr 6, 8:15 pm, Kai-Uwe Bux <jkherci...@gmx.net> 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