Algorithm advice needed for std::map

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?

re: Algorithm advice needed for std::map

"Michael Klatt" <mdklatt@ou.edu> wrote in message
news:2cb75565.0404191024.2994a4f0@posting.google.c om...[color=blue]
> 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?[/color]

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

re: Algorithm advice needed for std::map

Michael Klatt wrote:[color=blue]
> 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?[/color]

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.

re: Algorithm advice needed for std::map

"Michael Klatt" <mdklatt@ou.edu> wrote[color=blue]
> 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?[/color]

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

re: Algorithm advice needed for std::map

"Dave" <better_cs_now@yahoo.com> wrote in message news:<10888m8gs5dma50@news.supernews.com>...[color=blue]
> "Michael Klatt" <mdklatt@ou.edu> wrote in message
> news:2cb75565.0404191024.2994a4f0@posting.google.c om...[color=green]
> > 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?[/color]
>
> Can you just do a find() of your key first and, if found, tell the user that
> a replacement is about to occur?
>[/color]

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++)
}

re: Algorithm advice needed for std::map

Buster <noone@nowhere.com> wrote in message news:<c617vv$n3p$1@news6.svr.pol.co.uk>...
[color=blue][color=green]
> > I think this will have a complexity approaching O(log N), meaning that
> > this is as efficient as I can hope for, correct?[/color]
>
> 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;
> }[/color]

I guess I wasn't clear enough in my original post. I need to alter
both the key and data values.

re: Algorithm advice needed for std::map

Michael Klatt wrote:[color=blue]
> Buster <noone@nowhere.com> wrote:
> I guess I wasn't clear enough in my original post.[/color]
Perfectly clear.[color=blue]
> I need to alter both the key and data values.[/color]
No, you don't.
--
Regards,
Buster.

re: Algorithm advice needed for std::map

Buster wrote:[color=blue]
> Michael Klatt wrote:
>[color=green]
>> Buster <noone@nowhere.com> wrote:
>> I guess I wasn't clear enough in my original post.[/color]
>
> Perfectly clear.
>[color=green]
>> I need to alter both the key and data values.[/color]
>
> No, you don't.[/color]

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.

re: Algorithm advice needed for std::map

Buster <noone@nowhere.com> wrote in message news:<c64ckc$9qp$1@newsg3.svr.pol.co.uk>...
[color=blue]
> 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;
> }[/color]

Of course; I don't know why I didn't think of that. Thank you.