swapping keys

Discussion in 'C++' started by cpisztest@gmail.com, May 7, 2014.

  1. Guest

    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.
     
    , May 7, 2014
    #1
    1. Advertisements

  2. Öö Tiib Guest

    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.
    Why there is that temporary "value"? That seems to do same thing shorter:

    if (i != m.end())
    {
    m[22] = value;
    m.erase(i);
    }
    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::priority_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, May 7, 2014
    #2
    1. Advertisements

  3. Öö Tiib Guest

    I meant here:

    m[22] = i->second;
     
    Öö Tiib, May 7, 2014
    #3
  4. Jorgen Grahn Guest

    [He means keeping the value in the map, but "filed" under a new,
    different key]
    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
     
    Jorgen Grahn, May 7, 2014
    #4
  5. 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.
     
    Seungbeom Kim, May 7, 2014
    #5
  6. Öö Tiib Guest

    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
     
    Öö Tiib, May 7, 2014
    #6
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.