468,456 Members | 1,647 Online

# stl container for interval data type

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

Jul 2 '06 #1
3 6251
al**********@gmail.com wrote:
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

Jul 2 '06 #2
<al**********@gmail.comwrote:
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, intInterval;
std::list<Interval MyIntervals;

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.

modification; fast insertion, deletion.

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

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

typedef std::pair<int, intInterval;
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.

// ======= 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/
Jul 4 '06 #3
al**********@gmail.com wrote:
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
Jul 4 '06 #4

### This discussion thread is closed

Replies have been disabled for this discussion.