stl container for interval data type

A

alex.fishman

Hi,

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?

-Alex
 
L

Luke Meyers

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?

It sounds vaguely like homework, but not necessarily, so...

....actually, would be a great interview question, too. But anyway...

....I don't think any of the standard library containers are a
particularly good fit for this problem. However, I can see
representing this quite nicely as a binary tree. I actually
implemented something very similar a few months ago. Basically think
of the tree as a bitset, where if a bit is set it means the
corresponding integer is in the interval. When a whole subtree is the
same, you don't actually need nodes for it -- just interpret null
children as being all the same as their parent. The neat part (though
a bit tricky to implement) is that you can flip a whole subtree by
toggling a single bit. The reason it's tricky is worrying about all
those possibly-flipped bits when interpreting the contents of the tree.
I've done it, it's workable, it's not the only approach but it's an
interesting one. I suspect that most practical solutions to this
problem will revolve in some way around a binary tree.

Luke
 
R

Robbie Hatley

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?


I'm not sure what you mean by "interval for intersection"; can you
elaborate?

I do have a couple of ideas for you, though:


// ======= APPROACH #1: =======================================

// Make a list of ordered pairs of integers:
typedef std::pair<int, int> Interval;
std::list<Interval> MyIntervals;

// Add elements to list:
MyIntervals.push_back(Interval(1,3));
MyIntervals.push_back(Interval(7,32));
MyIntervals.push_back(Interval(13, -74));

// Remove all instances of (7,32) from list:
MyIntervals.remove(Interval(7,32));

I can't swear as to the exact speed of this, but it's fast.
Insertions and deletions will be quite fast.

Drawbacks: it allows intervals such as (13,-74) which are mal-formed
according to usual mathematical convention. You'd have to manually
disallow adding such intervals to the container if you don't want
that. There may also be an issue trying to do MyIntervals.sort()
if a suitable version of "<" is not available; you'd have to look
into that.

Advantages: ultra-simple; ready to go out of the box with no
modification; fast insertion, deletion.

Research "std::list" and "std::pair" for more info.


// ======= Approach #2: =========================================

If you want to prohibit duplicate intervals,
use a std::set instead of a std::list, like so:

typedef std::pair<int, int> Interval;
std::set<Interval> MyIntervals;

Advantages: Uniqueness of elements (if that's what you want);
blazing-fast lookup (uses binary trees).

Disadvantages: Might be a bit trickier to work with than lists
or other "ordinary" containers, do to the uniqueness requirement.

Research "std::set" for more info.


// ======= Approach #3: ========================================

Same as above, but using std::multiset instead of std::set.
This allows multiple copies of an interval such as (5,7),
if you want to allow that. Research "std::multiset" for more
info.


--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net
(put "[usenet]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/
 
N

n2xssvv g02gfr12930

Hi,

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?

-Alex
Most implementations of STL map use an RB, (Red Black), tree which have
an insertion and deletion operation worse case of O(log n) and a search
operation with a worse case of O(h) where h is the height of the tree.
Unless there's some other trick you can use on the data I doubt you'll
find a better solution. Hopefully you'll find this to be the best
solution, being easy with STL map and hence not requiring a lot of coding.

JB
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top