Initialize a std::set with keys from a std::map

[brzrkr0]

A portion of my program needs to initialize a std::set<int> to have
all the keys in a std::map<int, double>. The code I've pasted below
works, but I'm wondering if there's a more elegant way to do it (an
STL algorithm, maybe?). I'm a bit of an STL noob, so any advice
people can give would be greatly appreciated.


typedef std::map<int, double> intDoubleMap;
typedef std::set<int> intSet;

intSet v;
// map is an intDoubleMap* and has been initialized with some values
for (intDoubleMap::const_iterator it = map->begin();
it != map->end();
it++) {
int i = it->first;
v.insert(i);
}


Thanks,
Casey

 

[Andrew Koenig]

typedef std::map<int, double> intDoubleMap;
typedef std::set<int> intSet;

intSet v;
// map is an intDoubleMap* and has been initialized with some values
for (intDoubleMap::const_iterator it = map->begin();
it != map->end();
it++) {
int i = it->first;
v.insert(i);
}

Looks reasonable to me. If I were being picky, I'd change it++ to ++it
(because there is no reason to copy the iterator and then throw the original
value away) and I'd collapse

int i = it-> first;
v.insert(i);

into

v.insert(it->first);

but aside from that, I can't think offhand of a way of doing it that
wouldn't be much harder to understand (and without any obvious compensating
gain).

I might be missing something -- it wouldn't be the first time -- but there
is virtue in being straightforward.

 

[Daniel T.]

A portion of my program needs to initialize a std::set<int> to have
all the keys in a std::map<int, double>. The code I've pasted below
works, but I'm wondering if there's a more elegant way to do it (an
STL algorithm, maybe?). I'm a bit of an STL noob, so any advice
people can give would be greatly appreciated.

transform( map->begin(), map->end(), inserter( v, v.begin() ),
select1st<intDoubleMap::value_type>() );


Note, "select1st" is part of the STL, but not part of the standard
library. It's easy to implement though and is generally useful:

template <typename Pair>
struct select1st : unary_function<Pair, typename Pair::first_type>
{
const typename Pair::first_type& operator()(const Pair& x) const {
return x.first;
}
};


Or you can use the boost lambda library:

transform( map->begin(), map->end(), inserter( v, v.begin() ),
bind(&intDoubleMap::value_type::first, _1 ) );

 

[Jerry Coffin]

A portion of my program needs to initialize a std::set<int> to have
all the keys in a std::map<int, double>.

Why? Is there a reason you can't just leave the data in the map, and
temporarily ignore the associated data?

The code I've pasted below
works, but I'm wondering if there's a more elegant way to do it (an
STL algorithm, maybe?). I'm a bit of an STL noob, so any advice
people can give would be greatly appreciated.

Andrew Koenig has already pointed out a couple of minor changes. In
theory, I think you could probably create a special iterator type that
returns whatever.first when you dereference it, but (quite frankly) I
think that's more trouble than it's worth unless you're doing things
like this in quite a few different places. If memory serves, boost has
some iterators that can do that sort of thing for a boot tuple, and
similar (maybe even identical) code would probably work for std:air as
well (though I haven't looked at it, so I'm not sure -- for that matter,
my memory may just be bad, and no such thing exists at all...)

 

[LBCninja]

Why? Is there a reason you can't just leave the data in the map, and

temporarily ignore the associated data?

I was just thinking about that. I know the set is used in a
std::set_union algorithm downstream, so I'll have to figure if that
algorithm works with maps (and hash_maps) tomorrow. I checked the
set_union docs on sgi.com, but it's cryptic enough that I can't really
tell.

Daniel, your suggestion looks neat. If I can't avoid making the set
altogether I'll give that a try.

 

[James Kanze]

I was just thinking about that. I know the set is used in a
std::set_union algorithm downstream, so I'll have to figure if
that algorithm works with maps (and hash_maps) tomorrow.

First, it won't work at all with a hash_map, because it requires
its input to be ordered, and hash_map isn't. And it won't work
with a map unless you provide a special comparison function,
because by default, comparison of the pair will involve both
elements. On the other hand, Jerry's suggestion involving the
special iterator sounds like just the ticket here: you pass the
special iterator to set_union, and it only sees the keys.

I checked the set_union docs on sgi.com, but it's cryptic
enough that I can't really tell.

I checked in the standard, and it isn't really clear either. I
think some of the requirements are missing: what happens if the
two input iterators have different value_type, for example?

 

[Daniel T.]

I was just thinking about that. I know the set is used in a
std::set_union algorithm downstream, so I'll have to figure if that
algorithm works with maps (and hash_maps) tomorrow. I checked the
set_union docs on sgi.com, but it's cryptic enough that I can't really
tell.

Well, for set_union, the SGI docs say:

InputIterator1 and InputIterator2 [must] have the same value type.

So it depends on what the other input iterator is. If it's two maps then
you are OK with using set_union on them.

 

[James Kanze]

Well, for set_union, the SGI docs say:

InputIterator1 and InputIterator2 [must] have the same value type.

That makes sense, of course---I don't see how the algorithm
could work otherwise. But I can't find this requirement in the
standard.

So it depends on what the other input iterator is. If it's two
maps then you are OK with using set_union on them.

Really? I think you mean if it's two instantiations of the same
map type. I've sure that using a map< string, int > for the
first, and a map< int, string > for the second won't work. And
even if the two containers are the same map type, unless you
provide a custom comparison function, you're likely to end up
with duplicate entries: the default comparison for the
value_type of the map iterators takes both the key and the
mapped value into consideration.

 

[Daniel T.]

Why? Is there a reason you can't just leave the data in the map, and
temporarily ignore the associated data?
I was just thinking about that.  I know the set is used in a
std::set_union algorithm downstream, so I'll have to figure if that
algorithm works with maps (and hash_maps) tomorrow.  I checked the
set_union docs on sgi.com, but it's cryptic enough that I can't really
tell.

Well, for set_union, the SGI docs say:
InputIterator1 and InputIterator2 [must] have the same value type.

That makes sense, of course---I don't see how the algorithm
could work otherwise.  But I can't find this requirement in the
standard.

So it depends on what the other input iterator is. If it's two
maps then you are OK with using set_union on them.

Really?  I think you mean if it's two instantiations of the same
map type.  I've sure that using a map< string, int > for the
first, and a map< int, string > for the second won't work.

Of course.

And even if the two containers are the same map type, unless you
provide a custom comparison function, you're likely to end up
with duplicate entries: the default comparison for the
value_type of the map iterators takes both the key and the
mapped value into consideration.

Well, you aren't likely to end up with duplicate entries because map
can't do duplicate entries. However, if both maps contain a value with
the same key, then it is probably undefined which one is going to find
its way into the union.

 

[brzrkr0]

It sounds like the risk of introducing a new bug into the program
isn't worth changing from the current implementation (aside from
Andrew's style suggestions), considering that I'm relatively
inexperienced with custom iterators and custom comparison functions.

Though I am curious about the performance impact of skipping the
std::set creation and performing the set_union on a map instead - and
whether any performance increase from doing so would outweigh the
requirement that I use a std::map instead of a hash_map.

If I do manage to implement one of the techniques suggested here, I'll
profile it and report the results.

Thanks for the help,
Casey

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
says...

[ ... ]

I checked in the standard, and it isn't really clear either. I
think some of the requirements are missing: what happens if the
two input iterators have different value_type, for example?

It is a bit strange. I'm tempted to move this part of the discussion
over to comp.std.c++. There are really two outstanding questions, at
least in my mind. The first is what is really required in the current
standard. The second, and perhaps more important point, is whether any
omissions can be fixed for the next standard. Its description of
set_union doesn't seem to have changed a lot from the current one.