0

I would like to implement a map whose number of elements never exceeds a certain limit L. When the L+1-th element is inserted, the oldest entry should be removed from the map to empty the space.

I found something similar: Data Structure for Queue using Map Implementations in Java with Size limit of 5. There it is suggested to use a linked hash map, i.e., a hash map that also keeps a linked list of all elements. Unfortunately, that is for java, and I need a solution for C++. I could not find anything like this in the standard library nor in the boost libraries.

Same story here: Add and remove from MAP with limited size

A possible solution for C++ is given here, but it does not address my questions below: C++ how to mix a map with a circular buffer?

I would implement it in a very similar way to what is described there. An hash map to store the key-value pairs and a linked list, or a double-ended queue, of keys to keep the index of the entries. To insert a new value I would add it to the hash map and its key at the end of the index; if the size of the has at this point exceeds the limit, I would pop the first element of the index and remove the entry with that key from the has. Simple, same complexity as adding to the hash map.

Removing an entry requires an iteration over the index to remove the key from there, which has linear complexity for both linked lists and double-ended queue. (Double-ended queues also have the disadvantage that removing an element has itself linear complexity.) So it looks like the remove operation on such a data structure does not preserve the complexity as the underlying has map.

The question is: Is this increase in complexity necessary, or there are some clever ways to implement a limited map data structure so that both insertion and removal keep the same complexity?

Ooops, just posted and immediately realized something important. The size of the index is also limited. If that limit is constant, then the complexity of iterating over it can also be considered constant.

Well, the limit gives an upper bound to the cost of the removal operation.

If the limit is very high one might still prefer a solution that does not involve a linear iteration over the index.

Spiros
  • 2,156
  • 2
  • 23
  • 42
  • So you just need an extra data structure that maps a key to an iterator into the linked list in constant time on average? – T.C. Jul 11 '18 at 07:10
  • I think you can do it like this: `using Age = int;` you have a first map : `std::map>` (or `unordered_map`, as you prefer), and a second map: `std::map` where `using I = std::map>::iterator`. An age counter is initialized to 0, incremented when an element is inserted, and the element uses that age. Then you have O(log n) insertion and deletion – Olivier Sohn Jul 11 '18 at 07:43
  • sounds like a job for boost::multi_index? – Richard Hodges Jul 11 '18 at 07:47
  • 1
    There are tradeoffs with each container. You can't have o(1) complexity for all the operations. If there was a way then that's the only container we would need. – Ron Jul 11 '18 at 08:43

2 Answers2

1

I would still use an associative container to have direct access and a sequential one to allow easy removal of the older item. Let us look at the required access methods:

  • access to an element given its key => ok, the associative container allows direct access
  • add a new key-value pair
    • if the map is not full it is easy: push_back on the sequence container, and simple addition to the associative one
    • if the map is full, above action must happen, but the oldest element must be removed => front on the sequence container will give that element, and pop_front and erase will remove it, provided the key is contained in the sequence container
  • remove an element given by its key => trivial to remove from an associative container, but only list allows for constant time removal of an element provided you have an iterator on it. The good news is that removing or inserting an element in a list does not invalidate iterators pointing on other elements.

As you did not give any requirement for keeping keys sorted, I would use an unordered_map for the associative container and a list for the sequence one. The additional requirements is that the list must contain the key, and that the unordered_map must contain an iterator to its corresponding element in the list. The value can be in either container. As I assume that the major access will be the direct one, I would store the value in the map.

It boils down to:

  • a list<K> to allow identification of the oldest key
  • an unordered_map<K, pair<V, list<K>::iterator>>

It doubles the storage for key and adds an additional iterator. But keys are expected not to be too big and list::iterator normally contains little more than a pointer: this changes a small amount of memory for speed.

That should be enough to provide constant time

  • key access
  • insertion of a new item
  • key removal of an item
Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
  • What about one more way: to keep data in deque> and map K to data in unordered_map. V* is a pointer to V in deque (is not invalidated by front and back operations in deque)? – wtom Jul 11 '18 at 09:12
  • 1
    No, you need a pointer (iterator) on the list item to be able to remove it. And as I assumed that the major access will be a key access you add an indirection for that (major) access. – Serge Ballesta Jul 11 '18 at 09:16
0

You may want to take a look at Boost.MultiIndex MRU example.

Joaquín M López Muñoz
  • 5,243
  • 1
  • 15
  • 20