Search code examples
c++algorithmdata-structures

Efficient Interval Storage Using C++ Standard Library

I am working on a problem where each pair represents a closed interval, and I need a data structure to store a collection of these pairs. This data structure should support two operations: insert(pair) and delete(idx). The insert operation needs to check if the interval to be inserted overlaps with any existing intervals in the collection; if there is an overlap, the insertion should fail and return -1. The delete operation should remove the idx-th largest pair in the collection.

My goal is to implement this using only the C++ Standard Library, while keeping the code as minimal as possible. Additionally, it is crucial that both the insert and delete methods have a time complexity smaller than O(log n).

I would greatly appreciate any suggestions or ideas you might have on how to achieve this efficiently, without the need for coding. Thank you very much for your assistance! So far, the only solution I have come up with is using a B+ tree, but it requires a little much of code.

class CustomDataStructure {
// some underlying private data structures
public:
    bool insert(const pair<int ,int>& interval);
    pair<int ,int> delete(unsigned int idx); // return deleted interval
}

Here is an example workflow of this class:

original intervals: original intervals call insert({4,10}); after insert call delete(2); enter image description here

Solution

  • There is no container in std that can satisfy your requirements.

    None of the sequence containers can insert into arbitrary positions in less than O(size()). vector, deque and inplace_vector have O(size) insert. list and forward_list have O(size) lookup.

    None of the associative or unordered associative containers can find the ith index in less than O(i). std::advance et.al. are O(i) unless the iterator satisfies RandomAccessIterator, which isn't the case for those containers.

    None of the container adaptors help, because they still have the insertion characteristics of the underlying container.

    You'd need to implement your own container to reach your complexity requirements. Something like an Indexable Skip List would work.