CODEWITHSUNDEEP
c++algorithmdata-structures
Thomas W.
Thomas W.

Reputation: 2224

Efficient C++ data structure to search for intervals in sets of integer values

I'm looking for a data structure (and an C++ implementation) that allows to search (efficiently) for all elements having an integer value within a given interval. Example: say the set contains:

3,4,5,7,11,13,17,20,21

Now I want to now all elements from this set within [5,19]. So the answer should be 5,7,11,13,17

For my usage trivial search is not an option, as the number of elements is large (several million elements) and I have to do the search quite often. Any suggestions?

Upvotes: 1

Views: 888

Answers (2)

leemes
leemes

Reputation: 45675

For this, you typically use std::set, that is an ordered set which has a search tree built on top (at least that's one possible implementation).

To get the elements in the queried interval, find the two iterators pointing at the first and last element you're looking for. That's a use case of the algorithm std::lower_bound and upper_bound to consider both interval limits as inclusive: [x,y]. (If you want to have the end exclusive, use lower_bound also for the end.)

These algorithms have logarithmic complexity on the size of the set: O(log n)

Note that you may also use a std::vector if you sort it before applying these operations. This might be advantageous in some situations, but if you always want to sort the elements, use std::set, as it does that automatically for you.

Live demo

#include <set>
#include <algorithm>
#include <iostream>

int main()
{
    // Your set (Note that these numbers don't have to be given in order):
    std::set<int> s = { 3,4,5,7,11,13,17,20,21 };

    // Your query:
    int x = 5;
    int y = 19;

    // The iterators:
    auto lower = std::lower_bound(s.begin(), s.end(), x);
    auto upper = std::upper_bound(s.begin(), s.end(), y);

    // Iterating over them:
    for (auto it = lower; it != upper; ++it) {
        // Do something with *it, or just print *it:
        std::cout << *it << '\n';
    }
}

Output:

5
7
11
13
17

Upvotes: 4

Adithya Upadhya
Adithya Upadhya

Reputation: 2385

For searching within the intervals like you mentioned, Segment trees are the best. In competitive programming, several questions are based on this data structure.

One such implementation could be found here: http://www.sanfoundry.com/cpp-program-implement-segement-tree/

You might need to modify the code to suit your question, but the basic implementation remains the same.

Upvotes: 0

Related Questions