swapping keys

[cpisztest]

I read that swapping keys using a std::map isn't exactly efficient:

iterator i = m.find(33);

if (i != m.end())
{
value = i->second;
m.erase(i);
m[22] = value;
}

and it is suggested that one might look at using another container if the key is expected to be swapped. What container might one look at? I don't seem to be able to find any where key swapping is part of some built in method.

 

[Öö Tiib]

I read that swapping keys using a std::map isn't exactly efficient:

Does working with map, particularly such swapping take significant
percentage of application's work? Then deal with it. Otherwise deal
with what actually slows it down. Performance works without actual
performance issues are thrown away effort. Just like adding features
to program that no one will ever use. More code, more defects, no
actual benefits.

iterator i = m.find(33);

if (i != m.end())
{
value = i->second;
m.erase(i);
m[22] = value;
}

Why there is that temporary "value"? That seems to do same thing shorter:

if (i != m.end())
{
m[22] = value;
m.erase(i);
}

and it is suggested that one might look at using another container if the
key is expected to be swapped. What container might one look at? I don't
seem to be able to find any where key swapping is part of some built in
method.

Who suggested? Where? Why do not you ask from the suggesters?
For me it looks ungrounded answer to theoretical question.

It may be enough if to use 'boost::fast_pool_allocator' with 'std::map'. It
may be better to use 'std::unordered_map' instead of 'map'. It may be a case
where something else entirely like 'std:riority_queue' or sorted
'std::vector' or even 'std::list' is better than 'map'. It may be worth to use
'boost::intrusive' containers. One can only *lie* without knowing actual
data and actual problems.

 

[Öö Tiib]

if (i != m.end())
{
m[22] = value;

I meant here:

m[22] = i->second;

 

[Jorgen Grahn]

[He means keeping the value in the map, but "filed" under a new,
different key]

Does working with map, particularly such swapping take significant
percentage of application's work? Then deal with it. Otherwise deal
with what actually slows it down. Performance works without actual
performance issues are thrown away effort.

Yes.

Also I'd like to see the bigger picture -- what's the complete usage
pattern for this container? There are always tradeoffs -- you cannot
buy fast key swapping without sactificing something else.

....
I cannot think of a "silver bullet" here (I'm not very familiar
with e.g. Boost) so I think the answer would depend on your specific
needs.

std::unordered_map is somewhat better at insert/delete, if you don't
need the extra features std::map gives you (e.g. an ordering of the
elements).

/Jorgen

 

[Seungbeom Kim]

Why there is that temporary "value"? That seems to do same thing shorter:

if (i != m.end())
{
m[22] = value;
m.erase(i);
}

If the mapped_type is an expensive-to-copy type (e.g. requires dynamic
allocation, like std::string or std::vector), it should support move:

if (i != m.end()) {
m[22] = std::move(i->second);
m.erase(i);
}

If the mapped_type is not such a type, you shouldn't need to worry.

std::map is based on nodes, and reusing the same node with just the
key changed could be made to work (on an extension maybe), but
unfortunately std::map doesn't provide the interface necessary for it.

 

[Öö Tiib]

Why there is that temporary "value"? That seems to do same thing shorter:

if (i != m.end())
{
m[22] = value;
m.erase(i);
}

If the mapped_type is an expensive-to-copy type (e.g. requires dynamic
allocation, like std::string or std::vector), it should support move:

if (i != m.end()) {
m[22] = std::move(i->second);
m.erase(i);
}

If the mapped_type is not such a type, you shouldn't need to worry.

std::map is based on nodes, and reusing the same node with just the
key changed could be made to work (on an extension maybe), but
unfortunately std::map doesn't provide the interface necessary for it.

It is tricky because the nodes (and properties of nodes like size and
alignment) are not exposed in 'map's interface. What is exposed is
'pair' but node has more stuff in it.

There has been some work. Alan Talbot proposed 'splice's and Howard
Hinnant suggested 'remove' and 'insert's with new flavor. It is
issue 839 now closed with "revisit in future":
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839