Algorithm advice needed for std::map

[Michael Klatt]

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?

 

[Dave]

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

 

[Buster]

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;
}

 

[Claudio Puviani]

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

 

[Michael Klatt]

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]

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.

 

[Buster]

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.

 

[Buster]

Perfectly clear.


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;
}

 

[Michael Klatt]

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.