I'm looking for a collection that would suit my scenario:I will be inserting key-value pairs (both integers) of ID and timestamp. The ID must be unique.At some interval I will be checking that collection for expired items (as in the timestamp + X < current_timestamp) and will need to both remove the key-value pair and act on the key.I stated that I'm looking for sorted collection, because I think with the collection sorted by value (descending order) I could break the loop over the collection at the point I reach first not expired timestamp (that would mean rest of them is active too).I predict that 95% of my entries will not be expired at the time I loop over them.There will be way more inserts/modifications than reads.I couldn't find anything that would match this scenario, the closest one is SortedMap.Is there anything that would be more suitable? Perhaps completely other approach?I think it's also important to point out it will hold up to 10000 keys (pairs).If there's anyone with JavaScript (node) background then providing some links to implementations would also be great.
Javascript queue-like key-pair sorted collection
data structures;sorting;map
It is not necessary to have a single collection that satisfies your requirements. Instead, you can combine two collections to get the required properties. You then only modify these collections through an interface that ensures that the two collections are kept in sync.for uniqueness, keep a Set of IDs.for ordering, keep a Queue of Timestamps.Deleting old entries requires that you can remove the IDs from the Set, so you need to find the ID from a Queue-item. We could therefore implement this as a Map from IDs to Timestamps, and a Queue of IDs, sorted by corresponding timestamp.Pseudocode:queue: min-priority queue for map[entry]insert(map, queue, ID):  map[ID] = now()  queue.insert(ID)delete-expired(map, queue):  while map[queue.first] is expired:    delete map[queue.first]    queue.unqueue()Ah, but what about updating the timestamp? If memory is not the limiting factor, I would leave the old entries in the queue but mark them as invalid. This defers their removal until they are dequeued.queue: min-priority queue for entry.timestampinsert(map, queue, ID):  if ID in map:    map[ID].valid = false  entry = { timestamp: now(), id: ID, valid: true }  map[ID] = entry  queue.insert(entry)delete-expired(map, queue):  while queue is not empty:    entry = queue.first    if entry.valid and entry.timestamp is not expired:      return    delete map[entry.id]    queue.unqueue()Alternatively, you can delete the entry from the middle of the queue. However, queue-removal generally requires you to scan or move all elements in the queue, and is therefore a very time-intensive operation. This might be the correct choice if you are memory-constrained.The priority queue can in general be implemented as a heap.Since you only insert newer elements, an array-like data structure would also be a good choice. But dynamic arrays (the lists JavaScript gives you by default) are not desirable since the elements have to be regularly moved into the space freed up at the front by dequeuing entries. An alternative that doesn't have to move elements is a ring buffer, which could be made self-resizing like a dynamic array.