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

    On Wednesday, 7 May 2014 02:38:34 UTC+3, wrote:
    > 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::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

    On Wednesday, 7 May 2014 06:31:37 UTC+3, Öö Tiib wrote:
    > if (i != m.end())
    > {
    > m[22] = value;


    I meant here:

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

    On Wed, 2014-05-07, Öö Tiib wrote:
    > On Wednesday, 7 May 2014 02:38:34 UTC+3, wrote:
    >> I read that swapping keys using a std::map isn't exactly efficient:


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

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


    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 <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, May 7, 2014
    #4
  5. On 2014-05-06 20:31, Öö Tiib wrote:
    >
    > 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.

    --
    Seungbeom Kim
     
    Seungbeom Kim, May 7, 2014
    #5
  6. Öö Tiib Guest

    On Wednesday, 7 May 2014 23:35:55 UTC+3, Seungbeom Kim wrote:
    > On 2014-05-06 20:31, Öö Tiib wrote:
    > >
    > > 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
     
    Öö Tiib, May 7, 2014
    #6
    1. Advertisements

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.
Similar Threads
  1. Dan
    Replies:
    1
    Views:
    602
    Philipp Sumi
    Jul 23, 2003
  2. Guadala Harry

    Swapping Image Url

    Guadala Harry, Aug 13, 2004, in forum: ASP .Net
    Replies:
    5
    Views:
    5,929
    Toby Mathews
    Aug 13, 2004
  3. Tony
    Replies:
    1
    Views:
    867
    Robbe Morris [C# MVP]
    Mar 31, 2006
  4. sandeep Kanwal

    serial keys/validation keys

    sandeep Kanwal, Oct 29, 2004, in forum: C++
    Replies:
    1
    Views:
    819
    Mike Wahler
    Oct 29, 2004
  5. Harry George
    Replies:
    9
    Views:
    1,032
    sonal
    Jun 13, 2006
  6. Replies:
    10
    Views:
    1,079
    Daniel T.
    Feb 3, 2006
  7. alan
    Replies:
    3
    Views:
    665
    Victor Bazarov
    Nov 28, 2007
  8. A. Farber
    Replies:
    10
    Views:
    545
    A. Farber
    Jun 12, 2004
Loading...