 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Diego Martins
Guest
|
 Posted: Tue Aug 15, 2006 12:43 am Post subject: What is the best way to iterate over a map? (or any paired c |
 |
|
When iterating over the elements of a map, frequently I only need the
map "value" (the second element of the pair).
Since I use STL algorithms a lot, I'd like to share with you two
particular versions of for_each and copy I implemented recently:
/** performs an operation in a range of any container of pair objects
* for each second element of the pairs.
* Usually, it is done in a map since the second element is the one
that contains the useful data.
* @param start first iterator of the range
* @param end last iterator of the range
* @param oper a pointer to a function or a function object that
implements the operator().
* @note oper class must have operator() with one parameter compatible
with the second element of the pairs
* @return copy of the functor or the pointer to the function
*/
template<class InputIterator, class Functor>
inline Functor for_each_second(InputIterator start, InputIterator end,
Functor oper)
{
for( ; start != end; ++start ) {
oper((*start).second);
}
return oper;
}
/** copy the second value from a range of any container of pair objects
* Usually, it is done in a map since the second element is the one
that contains the useful data.
* @param start first iterator of the range
* @param end last iterator of the range
* @param output output iterator
* @return copy of output iterator pointing to the next value to be
written
*/
template<class InputIterator, class OutputIterator>
inline OutputIterator copy_second(InputIterator start, InputIterator
end, OutputIterator output)
{
for( ; start != end; ++start ) {
*output++ = (*start).second;
}
return output;
}
These functions are pretty useful on my code, since I use a lot of maps
:)
But recently I had the need of a transform algorithm to use in a map.
It is a piece of cake implementing a "transform_second()" function
(*output++ =oper((*start).second) BUT I don't want to reimplement
every STL algorithm I may need :-(
In the case of transform, I quickly solved the problem using
for_each_second (many STL algorithms can be simulated with for_each),
but I think it was a deselegant solution
:-(
However, in the bath tube, I though of a wierd solution: can we
implement a generic iterator wrapper for containers of std::pair<> that
returns only the .second when dereferencing? How?
If yes, no need for for_each_second() and the similars
something like:
myFunction(int);
....
std::map<string,int> map;
....
std::for_each(SecondWrap(map.begin()),SecondWrap(map.end()),myFunction);
What do you think about that?
Diego Martins
HP Researcher
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
Maxim Yegorushkin
Guest
|
|
| Back to top |
|
|
Diego Martins
Guest
|
| Posted: Tue Aug 15, 2006 11:10 pm Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
{ consider more aggressive snipping of irrelevant quoted parts. -mod }
Earl Purple wrote:
| Quote: | Diego Martins wrote:
However, in the bath tube, I though of a wierd solution: can we
implement a generic iterator wrapper for containers of std::pair<> that
returns only the .second when dereferencing? How?
There is a boost transform_iterator which does what it suggests it does
- it transforms the iterators whilst acting as an iterator itself. So
operator++ effectively increments your iterator whilst operator*
performs the transform on the way.
You can look up the detail of boost transform_iterator but the basis
would be something like this. (Note this is for illustration only).
template < typename FwdIter, typename Oper
class transform_iterator_type
{
FwdIter iter;
Oper op;
// this traits class will get type that *iter produces
typedef typename iter_traits<FwdIter>::reference_type
reference_type;
public:
transform_iterator_type( FwdIter it, Oper o ) : iter (it), op(o)
{
}
transform_iterator_type operator++() { ++iter; return *this; }
// do the other operator++ and comparisons etc.
reference_type operator*() { return *iter; }
};
|
I appreciate your quick answers, but all of them were boost related and
I can't use boost in my software due to project policies.
Anyway, I want to learn how to build an iterator wrapper.
according to example above, can you explain the reason of "Oper op"
member?
| Quote: | // now write function transform_iterator() to produce one
|
I can't figure out why we need an aux function
what is wrong with:
SecondIteratorWrapper wrap(map.begin());
| Quote: | If yes, no need for for_each_second() and the similars
something like:
myFunction(int);
...
std::map<string,int> map;
...
std::for_each(SecondWrap(map.begin()),SecondWrap(map.end()),myFunction);
What do you think about that?
No need to rewrite the algorithm but we will need a transformer to
convert pair into
2nd even for the above. So
struct pair2nd
{
template <typename F, typename S > S operator() ( const std::pair
F, S > & pair )
{
return pair.second;
}
};
With the new standard once we get auto we can cut out some of the work
above. No need for the traits template to determine the type of *Iter.
And the pair2nd can be simplified to just take one template parameter
and return auto type.
Anyway, with the above, use whatever algorithm calling the
transform_iterator with pair2nd as the transformer.
|
sounds good, but I am still not getting the whole picture. Can you
gimme an example of your transform_iterator with this transformer,
please?
Diego Martins
HP
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Wed Aug 16, 2006 7:31 am Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
"Diego Martins" <jose.diego (AT) gmail (DOT) com> writes:
| Quote: | I appreciate your quick answers, but all of them were boost related and
I can't use boost in my software due to project policies.
Anyway, I want to learn how to build an iterator wrapper.
|
If you can't use Boost, then study the standard iterator requirements
very, very carefully. It's very easy to write "iterators" that seem
to work in your tests but don't meet the standard's definition of
iterators, so they fail in subtle ways when used where a standard
iterator is expected.
Good luck,
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Thu Aug 17, 2006 6:43 am Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
In article <1155735438.282116.35110 (AT) 74g2000cwt (DOT) googlegroups.com>, Diego
Martins <jose.diego (AT) gmail (DOT) com> wrote:
| Quote: | Carl Barron wrote:
[snip]
template <class Iter
struct second_iter_base
{
typedef boost::iterator_adaptor
second_iterator<Iter>,
Iter,
typename std::iterator_traits<Iter>::value_type::second_type
type;
};
I am going a little bit off-topic, but I have to ask the following
question:
Is the code snippet above used to simulate the "template typedef"?
It is written to make the code more readable and less likely to |
contain typos. It is a meta function the purpose is to define the base
class in a more readable manner than writing it out two or three times
in this case. It is an idiom I use when creating custom iterators. I
guess that is what 'template typedef's are supposed to do.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Thu Aug 17, 2006 7:31 pm Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
David Abrahams wrote:
| Quote: | "Diego Martins" <jose.diego (AT) gmail (DOT) com> writes:
I appreciate your quick answers, but all of them were boost
related and I can't use boost in my software due to project
policies. Anyway, I want to learn how to build an iterator
wrapper.
If you can't use Boost, then study the standard iterator
requirements very, very carefully. It's very easy to write
"iterators" that seem to work in your tests but don't meet the
standard's definition of iterators, so they fail in subtle
ways when used where a standard iterator is expected.
|
Been there, done that. I'm actually pretty good at writing
non-conformant iterators... that work most of the time (and pass
all of my own tests).
What I've found useful in such cases is to compiler with a
concept checking version of the library. A recent version of
g++, with -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG
-D_GLIBCXX_DEBUG_PEDANTIC can find a lot of errors.
--
James Kanze GABI Software
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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Guest
|
| Posted: Fri Aug 18, 2006 6:41 am Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
{ please try to include at least some context (e.g. by quoting the
original posting) when replying in such abbreviated manner. -mod }
use two containers, a map and a list.
the list contain the values and the map contain the keys and the list's
iterators.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Earl Purple
Guest
|
| Posted: Fri Aug 18, 2006 6:08 pm Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
kanze wrote:
| Quote: | Been there, done that. I'm actually pretty good at writing
non-conformant iterators... that work most of the time (and pass
all of my own tests).
What I've found useful in such cases is to compiler with a
concept checking version of the library. A recent version of
g++, with -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG
-D_GLIBCXX_DEBUG_PEDANTIC can find a lot of errors.
|
How does it know though if the class is intended to be an iterator? Is
it because you try to pass it to any standard algorithm? Or does merely
calling it iterator or returning it from a begin() function suddenly
turn it into one?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Fri Aug 18, 2006 10:44 pm Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
Earl Purple wrote:
| Quote: | kanze wrote:
Been there, done that. I'm actually pretty good at writing
non-conformant iterators... that work most of the time (and
pass all of my own tests).
What I've found useful in such cases is to compiler with a
concept checking version of the library. A recent version of
g++, with -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG
-D_GLIBCXX_DEBUG_PEDANTIC can find a lot of errors.
How does it know though if the class is intended to be an iterator? Is
it because you try to pass it to any standard algorithm? Or does merely
calling it iterator or returning it from a begin() function suddenly
turn it into one?
|
It checks arguments to the standard algorithms, to ensure that
they meet the requirements for those arguments. Some standard
algorithms have a requirement that the argument meet the
requirements of e.g. forward iterator. G++ verifies that any
type you pass as a parameter to those algorithms meets *all* of
the stated requirements (and thus, all of the requirements of a
forward iterator, if that's what the algorithm says it
requires), even if some of the characteristics aren't used in
the actual implementation.
Although the problems it detected in my code all had to do with
iterators, I presume that it also verifies other types of
arguments, e.g. Predicate, etc. I also suppose that it isn't
perfect; I'd be very surprised, for example, if it detected that
your ordering predicate didn't specify a complete ordering.
Still, it's definitly worth using.
--
James Kanze GABI Software
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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Sat Aug 19, 2006 12:04 am Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
"Earl Purple" <earlpurple (AT) gmail (DOT) com> writes:
| Quote: | kanze wrote:
Been there, done that. I'm actually pretty good at writing
non-conformant iterators... that work most of the time (and pass
all of my own tests).
What I've found useful in such cases is to compiler with a
concept checking version of the library. A recent version of
g++, with -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG
-D_GLIBCXX_DEBUG_PEDANTIC can find a lot of errors.
How does it know though if the class is intended to be an iterator? Is
it because you try to pass it to any standard algorithm?
|
Essentially, yes, as long as you pass it where an iterator is expected.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Earl Purple
Guest
|
| Posted: Mon Aug 21, 2006 4:33 pm Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
kanze wrote:
| Quote: |
It checks arguments to the standard algorithms, to ensure that
they meet the requirements for those arguments. Some standard
algorithms have a requirement that the argument meet the
requirements of e.g. forward iterator. G++ verifies that any
type you pass as a parameter to those algorithms meets *all* of
the stated requirements (and thus, all of the requirements of a
forward iterator, if that's what the algorithm says it
requires), even if some of the characteristics aren't used in
the actual implementation.
|
In some ways then it is turning the algorithms from a library feature
to a language feature.
I guess that given the algorithms are part of the standard, they are
allowed to do that.
| Quote: | I also suppose that it isn't
perfect; I'd be very surprised, for example, if it detected that
your ordering predicate didn't specify a complete ordering.
Still, it's definitly worth using.
|
I tried that once with a collection of a "scissors/paper/rock" type
where scissors<rock<paper<scissors and then tried doing a sort on it. I
was slightly surprised that I did actually get a partition so all the
instances of paper were together although obviously it was random
whether or not paper turned up as the lowest or highest value of the
three.
Similarly if you sorted a collection of doubles or floats that
contained scattered NaN values, would these NaN values appear randomly
in the result set or would they all be grouped together? As any
comparison with a NaN always returns false, it would be equivalent to
saying that these NaNs are "equal" to anything and therefore could
appear anywhere.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Mon Aug 21, 2006 8:48 pm Post subject: Re: What is the best way to iterate over a map? (or any pair |
|
|
"kanze" <kanze@gabi-soft.fr> writes:
| Quote: | Earl Purple wrote:
kanze wrote:
Been there, done that. I'm actually pretty good at writing
non-conformant iterators... that work most of the time (and
pass all of my own tests).
What I've found useful in such cases is to compiler with a
concept checking version of the library. A recent version of
g++, with -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG
-D_GLIBCXX_DEBUG_PEDANTIC can find a lot of errors.
How does it know though if the class is intended to be an iterator? Is
it because you try to pass it to any standard algorithm? Or does merely
calling it iterator or returning it from a begin() function suddenly
turn it into one?
It checks arguments to the standard algorithms, to ensure that
they meet the requirements for those arguments. Some standard
algorithms have a requirement that the argument meet the
requirements of e.g. forward iterator. G++ verifies that any
type you pass as a parameter to those algorithms meets *all* of
the stated requirements
|
Just a nit: not quite. It only (and can only) check the structural
requirements, but not the semantic ones. For example, such
requirements as
a == b implies b == a
go unchecked.
Although not particularly important for just checking concepts, this
point is actually more important than it looks in general. A type may
model concept A but exhibit all the structural requirements of a
refined concept, B. If you start dispatching to different algorithm
implementations based on structure you can cause yourself no end of
grief.
| Quote: | (and thus, all of the requirements of a
forward iterator, if that's what the algorithm says it
requires), even if some of the characteristics aren't used in
the actual implementation.
Although the problems it detected in my code all had to do with
iterators, I presume that it also verifies other types of
arguments, e.g. Predicate, etc. I also suppose that it isn't
perfect; I'd be very surprised, for example, if it detected that
your ordering predicate didn't specify a complete ordering.
|
Exactly. No semantic checks.
| Quote: | Still, it's definitly worth using.
|
Definitely.
And I should point out that this concept checking work originated in
Boost and has recently undergone several improvements:
http://lists.boost.org/Archives/boost/2006/08/109383.php
Cheers,
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Tue Aug 22, 2006 12:40 am Post subject: Re: What is the best way to iterate over a map? (or any pai |
|
|
Earl Purple wrote:
| Quote: | kanze wrote:
It checks arguments to the standard algorithms, to ensure that
they meet the requirements for those arguments. Some standard
algorithms have a requirement that the argument meet the
requirements of e.g. forward iterator. G++ verifies that any
type you pass as a parameter to those algorithms meets *all* of
the stated requirements (and thus, all of the requirements of a
forward iterator, if that's what the algorithm says it
requires), even if some of the characteristics aren't used in
the actual implementation.
In some ways then it is turning the algorithms from a library
feature
to a language feature.
|
I don't think so. What is an iterator, other than something you
can use in an algorithm. The standard defines iterators, but
only as an abstract concept. It then states that 1) the
algorithms require something which conforms to this concept, and
2) the standard containers fournish something which conforms to
this concept. There is no way (at present) to say that a class
is an iterator. What the concept checks in g++ test is that any
class used in an instantiation of a templated component of the
standard library conforms to the concepts (the constraints) of
the template argument involved. (Only the structural
constraints, as David Abrahams correctly pointed out. They
don't do the impossible.) Unless you use your iterator in a
context which requires an iterator, the compiler has no way of
knowing that it is meant to be an iterator.
| Quote: | I guess that given the algorithms are part of the standard, they are
allowed to do that.
I also suppose that it isn't perfect; I'd be very surprised,
for example, if it detected that your ordering predicate
didn't specify a complete ordering. Still, it's definitly
worth using.
I tried that once with a collection of a "scissors/paper/rock"
type where scissors<rock<paper<scissors and then tried doing a
sort on it. I was slightly surprised that I did actually get a
partition so all the instances of paper were together although
obviously it was random whether or not paper turned up as the
lowest or highest value of the three.
|
Can you prove that it will work, for all initial orderings, and
for all legal implementations of std::sort, or was it just luck.
| Quote: | Similarly if you sorted a collection of doubles or floats that
contained scattered NaN values, would these NaN values appear
randomly in the result set or would they all be grouped
together?
|
You have undefined behavior. For all the standard cares, it may
format your hard disk.
| Quote: | As any comparison with a NaN always returns false, it would be
equivalent to saying that these NaNs are "equal" to anything
and therefore could appear anywhere.
|
--
James Kanze GABI Software
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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
