|  | std::map<> or std::set<> as interval search tree | | |
| | | Rune Allnor |  |
|  Posted: Sun Aug 31, 2008 10:58 pm Post subject: std::map<> or std::set<> as interval search tree |  |
| |  | |
Hi all.
I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
------------+---------+--------+---------+--------
a x b c d
Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map<>
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.
However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a>
and a value x > d returns a value indicating [d,inf>.
Any suggestions?
Rune
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Alberto Ganesh Barbati | |
| | Posted: Mon Sep 01, 2008 7:04 am Post subject: Re: std::map<> or std::set<> as interval search tree | |
| | | |
Rune Allnor ha scritto:
| Quote: | Hi all.
I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
------------+---------+--------+---------+--------
a x b c d
Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.
However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a
and a value x > d returns a value indicating [d,inf>.
Any suggestions?
|
Looks like a job for the member function equal_range.
Ganesh
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | LR | |
| | Posted: Mon Sep 01, 2008 7:06 am Post subject: Re: std::map<> or std::set<> as interval search tree | |
| | | |
Rune Allnor wrote:
| Quote: | Hi all.
I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
------------+---------+--------+---------+--------
a x b c d
Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.
However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a
and a value x > d returns a value indicating [d,inf>.
|
How many intervals do you have?
Are they all fixed width?
Do they change during the course of the program's execution?
How many searches will you have to do?
Depending on how many you have and how often they change, perhaps
storing the numbers in a vector and doing a modified binary search that
returns a std::pair that indicates where the number you're searching for
might fit.
If there are only a few numbers that change during execution then this
might still be acceptable.
This seems like a simple solution and might at least get you an
interface, you can always change the underlying code later if
performance is unacceptable.
However, if there are very many of your numbers or the numbers are very
likely to change during execution, then perhaps some sort of map of maps
of maps... might better fit the bill.
std::map<coarse_key, std::map<less_coarse, std::map<fine_key, value> > >
or maybe something like
class ValueOrMap {};
class Value : public ValueOrMap {};
class Map : public ValueOrMap {};
class ValueOrMapPointerWrapper {
ValueOrMap *p_;
....
};
std::map<coarse_key, ValueOrMapPointerWrapper>
I offer these suggestions as a point of departure, not a solution.
Also, it seems to me that in someways, your problem is not a C++ problem
and you might have better luck in an algorithms group.
LR
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | David Abrahams | |
| | Posted: Mon Sep 01, 2008 7:14 am Post subject: Re: std::map<> or std::set<> as interval search tree | |
| | | |
on Sun Aug 31 2008, Rune Allnor <allnor-AT-tele.ntnu.no> wrote:
| Quote: | Hi all.
I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
------------+---------+--------+---------+--------
a x b c d
Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.
However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a
and a value x > d returns a value indicating [d,inf>.
Any suggestions?
|
There's something called an "interval tree." IIRC it stores each
interval by its start position and annotates each node additionally with
the maximum end position of all its descendant nodes. I implemented one
years ago with minor modifications of STLPort's rbtree implementation
that underlay its associative containers. Ah, yes:
LINK
On the other hand, that's allows overlapping intervals, and it looks
like your example doesn't have overlaps. If not, you could use one of
the std associative containers (or a sorted vector) with a key that is
the beginning of each interval, and use upper_bound to find the position
where x falls in the sequence. I leave dealing with the endpoints as an
exercise for the reader ;-)
--
Dave Abrahams
BoostPro Computing
LINK
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Tony Delroy | |
| | Posted: Mon Sep 01, 2008 7:20 am Post subject: Re: std::map<> or std::set<> as interval search tree | |
| | | |
On Sep 1, 7:58 am, Rune Allnor <all...@tele.ntnu.no> wrote:
| Quote: | However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
|
Read up on lower_bound() and upper_bound(). Note: there're both stand-
alone algorithm versions and container member function versions.
| Quote: | Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a
and a value x > d returns a value indicating [d,inf>.
|
Might have to special-case one or both of these, but no big deal.
HTH, Tony
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Scott McMurray | |
| | Posted: Mon Sep 01, 2008 10:18 am Post subject: Re: std::map<> or std::set<> as interval search tree | |
| | | |
On Aug 31, 6:58 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
| Quote: | I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
[...]
Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a
and a value x > d returns a value indicating [d,inf>.
Any suggestions?
|
Do you need to store interval objects?
If not, it seems to me like you can do this perfectly by adding -
numeric_limits<T>::infinity(), numeric_limits<T>::infinity(), and all
the "fenceposts" (a, b, c, and d, here) to a set<T>. You can then
find the high end of the range using upper_bound, and the low end is
the previous iterator.
(You don't need the infinities either, but they save some special-
casing for getting end() and begin() from upper_bound, on the
assumption that the input is finite. Since you specified
[closed,open) ranges, upper_bound is used instead of lower_bound so
that the input-is-a-fencepost case works correctly.)
HTH,
~ Scott
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Rune Allnor | |
| | Posted: Mon Sep 01, 2008 10:58 am Post subject: Re: std::map<> or std::set<> as interval search tree | |
| | | |
On 1 Sep, 09:06, LR <lr...@superlink.net> wrote:
| Quote: | Rune Allnor wrote:
Hi all.
I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
------------+---------+--------+---------+--------
a x b c d
Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.
However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a
and a value x > d returns a value indicating [d,inf>.
How many intervals do you have?
|
Unknown. Possibly as few as tens; maybe as many as tens of thousands.
| Quote: | Are they all fixed width?
|
No.
| Quote: | Do they change during the course of the program's execution?
|
Yes. The structure will be very dynamic; intervals will
change after every search. Each new x will split an existing
(internal) interval, and depending on other factors
surrounding intervals might be merged.
| Quote: | How many searches will you have to do?
|
(Tens of) millions.
| Quote: | Depending on how many you have and how often they change, perhaps
storing the numbers in a vector and doing a modified binary search that
returns a std::pair that indicates where the number you're searching for
might fit.
|
Somebody mentioned the upper_bound / lower_bound functions.
They seem to be good starting points.
Rune
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Maxim Yegorushkin | |
| | Posted: Mon Sep 01, 2008 7:45 pm Post subject: Re: std::map<> or std::set<> as interval search tree | |
| | | |
On Aug 31, 11:58 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
| Quote: | Hi all.
I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
------------+---------+--------+---------+--------
a x b c d
Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.
However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
|
Here is a sketch:
~/src/test $ cat test.cpp
#include <set>
#include <cstdio>
struct interval
{
double start, end; // [start, end]
interval(double s, double e) : start(s), end(e) {}
};
bool operator<(interval const& a, interval const& b)
{
return a.start < b.start;
}
typedef std::set<interval> interval_set;
interval const* find(interval_set const& s, double point)
{
interval_set::const_iterator i = s.lower_bound(interval(point,
point));
if(i == s.end() || point < i->start) {
if(i == s.begin())
return NULL;
--i;
return point <= i->end && point >= i->start ? &*i : NULL;
}
return &*i;
}
void check(interval_set const& s, double point)
{
if(interval const* i = find(s, point))
printf("%f belongs to [%f,%f]\n", point, i->start, i->end);
else
printf("%f does not belong to any interval\n", point);
}
int main()
{
interval_set s;
s.insert(interval(0, 1));
s.insert(interval(3, 4));
for(double i = -1; i < 5; i += .5)
check(s, i);
}
~/src/test $ g++ -Wall -Wextra -o test test.cpp
~/src/test $ ./test
-1.000000 does not belong to any interval
-0.500000 does not belong to any interval
0.000000 belongs to [0.000000,1.000000]
0.500000 belongs to [0.000000,1.000000]
1.000000 belongs to [0.000000,1.000000]
1.500000 does not belong to any interval
2.000000 does not belong to any interval
2.500000 does not belong to any interval
3.000000 belongs to [3.000000,4.000000]
3.500000 belongs to [3.000000,4.000000]
4.000000 belongs to [3.000000,4.000000]
4.500000 does not belong to any interval
--
Max
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | kalman | |
| | Posted: Thu Sep 18, 2008 9:28 pm Post subject: Re: Is self assignment test valid? | |
| | | |
On Sep 4, 3:58 am, Martin T <0xCDCDC...@gmx.at> wrote:
| Quote: | Maciej Sobczak wrote:
On 2 Wrz, 06:40, gmr...@o2.pl wrote:
-----------------------
Is this example valid and have well defined behavior?
Yes (provided that "operations" make sense), but it is debatable
whether it is a good idiom.
The argument goes that if the reliability of the assignment operator
depends on the existence of the self-assignment-test, then the
operator most likely has some deeper design problems.
It is impossible to assert this for the code above, since the crucial
part ("operations") is not shown, but in practice this is very often
true - if you need this test, then you just try to protect something
that is inherently broken and even this protection is usually not
enough (hint: exception safety).
Examples would be nice.
I remember reading before that self assignemnt protection very often
hides some flaws, but I really fail to see the "very often".
For any object where it makes sense to use e.g. a memcpy in the
copy-ctor the self assignment test would tend to make the copying code
simpler and not only faster, no?
Performance optimization is the only potentially valid motivation for
such a test, but it actually improves the performance of a use case
that never happens (why assign to same object?) and therefore it does
not make any sense to optimize it.
Now that's quite a strong assumtion, is it not? "Never happens" is just
something that's bound to happen sooner or later :-)
Anyway - we (I) build redundancy into my code so that even with the
inevitable bugs it may just continue to run.
|
Both of you have a point here, what I'm used to using GCC is the usage
of likely/unliley macros
in order to give your compiler a branch prediction information, so you
operator becomes:
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
T& T::operator=(T const& rhs) {
if (likely(&rhs != this))
// operations
return *this;
}
Regards
Gaetano Mendola
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
|
|
