Algorithm advice needed for std::map

Discussion in 'C++' started by Michael Klatt, Apr 19, 2004.

  1. I need an efficient insert-or-replace algorithm based on the key_type
    of a std::map. The user needs to be notified if a replacement occurs.
    This is what I have:

    class Key;
    typedef map<Key, bool> Map;
    Map container;
    Key some_key;
    Map::value_type element(some_key, false);

    // insert 'element', replacing exisiting element if necessary
    pair<Map::iterator, bool> insertion(container.insert(element)); //
    O(log N)
    if (!insertion.second)
    {
    // replace existing element
    cout << "replacing " << it->first << " with " << some_key << "\n";
    Map::iterator it(container.erase(insertion.first)); // O(constant)
    container.insert(it, element); // O(constant)
    }

    I think this will have a complexity approaching O(log N), meaning that
    this is as efficient as I can hope for, correct?
    Michael Klatt, Apr 19, 2004
    #1
    1. Advertising

  2. Michael Klatt

    Dave Guest

    "Michael Klatt" <> wrote in message
    news:...
    > I need an efficient insert-or-replace algorithm based on the key_type
    > of a std::map. The user needs to be notified if a replacement occurs.
    > This is what I have:
    >
    > class Key;
    > typedef map<Key, bool> Map;
    > Map container;
    > Key some_key;
    > Map::value_type element(some_key, false);
    >
    > // insert 'element', replacing exisiting element if necessary
    > pair<Map::iterator, bool> insertion(container.insert(element)); //
    > O(log N)
    > if (!insertion.second)
    > {
    > // replace existing element
    > cout << "replacing " << it->first << " with " << some_key << "\n";
    > Map::iterator it(container.erase(insertion.first)); // O(constant)
    > container.insert(it, element); // O(constant)
    > }
    >
    > I think this will have a complexity approaching O(log N), meaning that
    > this is as efficient as I can hope for, correct?


    Can you just do a find() of your key first and, if found, tell the user that
    a replacement is about to occur?

    In your scheme, you do 2 inserts. The second one may not be O(1). It still
    may be O(lg N) since the "it" hint you give is not required to be used by an
    implementation. Of course, this doesn't change the complexity however since
    O(2 lg N) is still O(lg N).
    Dave, Apr 19, 2004
    #2
    1. Advertising

  3. Michael Klatt

    Buster Guest

    Michael Klatt wrote:
    > I need an efficient insert-or-replace algorithm based on the key_type
    > of a std::map. The user needs to be notified if a replacement occurs.
    > This is what I have:
    >
    > class Key;
    > typedef map<Key, bool> Map;
    > Map container;
    > Key some_key;
    > Map::value_type element(some_key, false);
    >
    > // insert 'element', replacing exisiting element if necessary
    > pair<Map::iterator, bool> insertion(container.insert(element)); //
    > O(log N)
    > if (!insertion.second)
    > {
    > // replace existing element
    > cout << "replacing " << it->first << " with " << some_key << "\n";
    > Map::iterator it(container.erase(insertion.first)); // O(constant)
    > container.insert(it, element); // O(constant)
    > }
    >
    > I think this will have a complexity approaching O(log N), meaning that
    > this is as efficient as I can hope for, correct?


    No. You're searching the tree twice. You already have an iterator to the
    position in the map where the new element should go and you can use it.

    pair <Map::iterator, bool> insertion (container.insert (element));
    if (! insertion.second)
    {
    cout << "Replacing.\n";
    insertion.first->second = element.second;
    }

    --
    Regards,
    Buster.
    Buster, Apr 19, 2004
    #3
  4. "Michael Klatt" <> wrote
    > I need an efficient insert-or-replace algorithm based on the key_type
    > of a std::map. The user needs to be notified if a replacement occurs.
    > This is what I have:
    >
    > class Key;
    > typedef map<Key, bool> Map;
    > Map container;
    > Key some_key;
    > Map::value_type element(some_key, false);
    >
    > // insert 'element', replacing exisiting element if necessary
    > pair<Map::iterator, bool> insertion(container.insert(element)); //
    > O(log N)
    > if (!insertion.second)
    > {
    > // replace existing element
    > cout << "replacing " << it->first << " with " << some_key << "\n";
    > Map::iterator it(container.erase(insertion.first)); // O(constant)
    > container.insert(it, element); // O(constant)
    > }
    >
    > I think this will have a complexity approaching O(log N), meaning that
    > this is as efficient as I can hope for, correct?


    There are other data structures that can give you better than O(log N). Well
    managed hash tables offer O(k) and tries work in O(log length(key)), for
    example.

    Claudio Puviani
    Claudio Puviani, Apr 19, 2004
    #4
  5. "Dave" <> wrote in message news:<>...
    > "Michael Klatt" <> wrote in message
    > news:...
    > > I need an efficient insert-or-replace algorithm based on the key_type
    > > of a std::map. The user needs to be notified if a replacement occurs.
    > > This is what I have:
    > >
    > > class Key;
    > > typedef map<Key, bool> Map;
    > > Map container;
    > > Key some_key;
    > > Map::value_type element(some_key, false);
    > >
    > > // insert 'element', replacing exisiting element if necessary
    > > pair<Map::iterator, bool> insertion(container.insert(element)); //
    > > O(log N)
    > > if (!insertion.second)
    > > {
    > > // replace existing element
    > > cout << "replacing " << it->first << " with " << some_key << "\n";
    > > Map::iterator it(container.erase(insertion.first)); // O(constant)
    > > container.insert(it, element); // O(constant)
    > > }
    > >
    > > I think this will have a complexity approaching O(log N), meaning that
    > > this is as efficient as I can hope for, correct?

    >
    > Can you just do a find() of your key first and, if found, tell the user that
    > a replacement is about to occur?
    >


    I don't see how this will be an improvement. In fact, if 'some_key'
    is not already in the map it will make things worse.

    map<Key, bool>::iterator it(container.find(some_key)); // O(log N)
    if (it == container.end())
    {
    // insert new element
    container.insert(element); // O(log N) again
    }
    else
    {
    // replace existing element
    container.insert(++it, element); // O(1) (at least for g++)
    }
    Michael Klatt, Apr 20, 2004
    #5
  6. Buster <> wrote in message news:<c617vv$n3p$>...

    > > I think this will have a complexity approaching O(log N), meaning that
    > > this is as efficient as I can hope for, correct?

    >
    > No. You're searching the tree twice. You already have an iterator to the
    > position in the map where the new element should go and you can use it.
    >
    > pair <Map::iterator, bool> insertion (container.insert (element));
    > if (! insertion.second)
    > {
    > cout << "Replacing.\n";
    > insertion.first->second = element.second;
    > }


    I guess I wasn't clear enough in my original post. I need to alter
    both the key and data values.
    Michael Klatt, Apr 20, 2004
    #6
  7. Michael Klatt

    Buster Guest

    Michael Klatt wrote:
    > Buster <> wrote:
    > I guess I wasn't clear enough in my original post.

    Perfectly clear.
    > I need to alter both the key and data values.

    No, you don't.
    --
    Regards,
    Buster.
    Buster, Apr 20, 2004
    #7
  8. Michael Klatt

    Buster Guest

    Buster wrote:
    > Michael Klatt wrote:
    >
    >> Buster <> wrote:
    >> I guess I wasn't clear enough in my original post.

    >
    > Perfectly clear.
    >
    >> I need to alter both the key and data values.

    >
    > No, you don't.


    Sorry.

    Two keys can be equivalent as far as the map's comparison function is
    concerned, but still distinguishable by other means. But, unless I'm
    mistaken (again) you really do have a reference to the element you want
    to replace. In that case, you know more about the situation than the
    designers of std::map assumed: you know you can replace the key without
    breaking any class invariants.

    if (! insertion.second)
    {
    std::cout << "Replacing.\n";
    const_cast <Key &> (insertion.first->first) = element.first;
    insertion.first->second = element.second;
    }

    --
    Regards,
    Buster.
    Buster, Apr 21, 2004
    #8
  9. Buster <> wrote in message news:<c64ckc$9qp$>...

    > Two keys can be equivalent as far as the map's comparison function is
    > concerned, but still distinguishable by other means. But, unless I'm
    > mistaken (again) you really do have a reference to the element you want
    > to replace. In that case, you know more about the situation than the
    > designers of std::map assumed: you know you can replace the key without
    > breaking any class invariants.
    >
    > if (! insertion.second)
    > {
    > std::cout << "Replacing.\n";
    > const_cast <Key &> (insertion.first->first) = element.first;
    > insertion.first->second = element.second;
    > }


    Of course; I don't know why I didn't think of that. Thank you.
    Michael Klatt, Apr 21, 2004
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,255
    Ivan Vecerina
    Mar 17, 2005
  2. Replies:
    1
    Views:
    401
    red floyd
    Dec 21, 2008
  3. Thomas J. Gritzan
    Replies:
    6
    Views:
    992
    James Kanze
    Dec 22, 2008
  4. James Kanze
    Replies:
    0
    Views:
    1,974
    James Kanze
    Dec 21, 2008
  5. Shriramana Sharma
    Replies:
    2
    Views:
    141
    Shriramana Sharma
    Jun 27, 2013
Loading...

Share This Page