I have a fixed size container containing ordered elements. In the constructor, I pass to it its maximum size and comparison function. When adding an element, the container uses the comparison function and adds a new element to other elements so as to keep the order from best to worst and, if the limit is reached, throws out the worst element.

Does such a container have a canonical name (English and Russian terms)?

    5 answers 5

    In my opinion, such a structure does not have a canonical name. Depending on the task, it may have different names. As examples:

    • LRU Cache : in this structure, the data is ordered by the frequency of calls to them, the least used are deleted when the specified cache size is reached.
    • MRU Cache: the same principle, but unlike LRU, the last used element is supplanted.
    • EvictingQueue : a data structure from Guava, the first element of the queue is deleted if the queue is full. There is also a MinMaxPriorityQueue .
    • CircularFifoQueue : data structure from Apache Commons, replaces the oldest item if the queue is full.

    I think, depending on the semantics of the data structure and the principle of its implementation (based on the queue, hash table, or any other underlying structure), the name may vary.

      For a start, I would not call such a data structure a container. From the container it is expected that it will store all the elements and not only those that he needs.

      As for the name - such a structure is encountered infrequently (for the reason stated above), and it does not have a well-known name. I would call it the best element buffer.

      • You want to say that if the insert implies the replacement of one of the old elements it is no longer a container? And if there are no additions at all, but only a replacement (for example, std :: array) is also not a container? - αλεχολυτ
      • @alexolut if there are no additions at all, this is a normal container. Because it satisfies the condition "added elements do not disappear by themselves". - Pavel Mayorov
      • So the repression due to the addition of a new one is, IMHO, not "by itself." - αλεχολυτ

      In C++ this kind of container is called a “priority queue” std::priority_queue . True, the automatic crowding out mentioned in the question does not occur when the maximum size is reached. This functionality can be quite easily implemented independently. The final version could be called the "Fixed-size queue with priority" ( fixed_size_priority_queue ).

      • one
        I will say more, everything has already been implemented, it's just the name :-) - Kromster
      • @KromStern, imho priority_queue is implemented via heap (pyramid). Mb and you also? - avp

      May be Circular buffer

      • With the ring buffer, only the fact that it has a fixed size matches. By default, it does not have a sort when inserted. Also in my case, the loopback is not claimed and would only complicate the container. - Kromster

      I would use the usual multi_set .

      Something like this:

       multi_set <int> best; if (best.size() < lim || x > *best.begin()) { best.insert(x); if (best.size() > lim) best.erase(best.begin()); }
      • The question of the name, and not about the possible implementation. - αλεχολυτ
      • Re-read the question please. It is not about how to do this (everything is done and works fine), but how such a structure is called a container (if it has a canonical name). - Kromster
      • @KromStern, something I doubt that she has a name. It is impossible for each individual task to come up with a unique common name. - Qwertiy ♦
      • Then you have 2 options, either write the answer that there is no name, or, like me, hope that it is and will be known. - Kromster