I am trying to work with ranges, as in ranges of numbers. By that I mean integer intervals, in maths speak. And I want to store a set of them. I also want this set to naturally merge (or coalesce) ranges I insert.
Let's go for a simple example, I start with an empty set: { }
- I insert the range [0,5], now I have { [0,5] }
- I insert the range [10,15], now I have { [0,5], [10,15] }
- I insert the range [5,7], now I have { [0,7], [10,15] }
- I insert the range [12,17], now I have { [0,7], [10,17] }
- I insert the range [6,13], now I have { [0,17] }
I found out thanks to a similar question that this exists in Java as a Google Guava library and is called a RangeSet.
I was initially thinking of using a std::set
of std::pair
s that would be sorted on the lower bound (so the first element of each pair). Then after each insertion I would have to manually merge any overlapping sets.
As this seems a common problem, is a good implementation I couldn't find due to the noise with all the synonyms of "range" in C++ ? Or does anyone care to share his own? I only want to print the final ranges but bonus points for generality if you have other set operations.
Aucun commentaire:
Enregistrer un commentaire