C++ Logo

std-proposals

Advanced search

Container.iterator_to for getting an iterator form the reference to value

From: Antony Polukhin <antoshkka_at_[hidden]>
Date: Thu, 13 Aug 2020 16:57:01 +0300
There are useful functions container.iterator_to in Boost.Intrusive
containers that could be adopted by the Standard Library.

Assuming that the `value` is in the `container`, the call
`container.iterator_to(value)` returns an iterator to that `value` in
the container.

Consider a sample of code from LRU implementation with intrusive list
and unordered_map

void Lru::ReplaceLastUsed(Key&& key, Value&& value)
      auto last_used_it = intrusive_list_.begin();
      auto node = map_.extract(last_used_it->GetReferenceToKeyInMap());
      // ...
}

In the sample above `GetReferenceToKeyInMap` returns a reference to
the value that is known to be in `map_`. Unfortunately, `map_.extract`
will do the hashing and search in the map. With iterator_to we can
avoid that:

void Lru::ReplaceLastUsed(Key&& key, Value&& value)
      auto last_used_it = intrusive_list_.begin();
      auto map_it = map_.iterator_to(last_used_it->GetReferenceToKeyInMap());
      auto node = map_.extract(map_it);
      // ...
}

Such optimization on toy examples gives x2 performance boost even for
trivial keys.

Another sample, were otherwise we are forced to use more complex
containers, or to do linear search, or to store iterators in the
object:

void ObjectInRegistry::MoveToEnd() {
    auto it = g_list_of_objects_.iterator_to(*this);
    g_list_of_objects_.splice(g_list_of_objects_.end(), g_list_of_objects_, it);
}

ObjectInRegistry::~ObjectInRegistry() {
    auto it = g_list_of_objects_.iterator_to(*this);
    g_list_of_objects_.erase(it);
}


Is there interest in such functionality?

-- 
Best regards,
Antony Polukhin

Received on 2020-08-13 09:00:36