Re: STL set with custom data type
cata.1...@hotmail.com wrote:
Hi,
I have structure representing a 2 dimesional point:
struct K2dCoords
{
K2dCoords(void):m_x(0), m_y(0){};
K2dCoords(double x, double y):m_x(x), m_y(y){};
K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
double getX() const {return m_x;}
double getY() const {return m_y;}
double m_x;
double m_y;
};
I want to store pointers to instances of this in a STL set.
So I define the sorting criterion, such that two points are considered
equal
if the distance between them is negligeble (less than a tolerance):
struct eq
As others have pointed out std::set needs a "strict weak order"-
predicate.
Also, why do you go through the trouble of using pointers? Is there a
need for pointers here?
stlMap.insert(new K2dCoords(xSp, ySp));
You know that you could also write
set<K2dCoords> myset;
myset.insert(K2dCoords(3.14,23.0));
Right?
The problem you want to solve is to detect whether a new point is
"close enough" to another point that's already in the data structure
("set") and if not, to add the point to the data structure, right?
This usually calls for something like a kd-tree:
http://en.wikipedia.org/wiki/Kd-tree
http://en.wikipedia.org/wiki/Nearest_neighbour_search
The alternative is to use a lexical ordering and to compare the new
point with every other point of the set's relevant subrange. Of
course a NNS won't be as fast as with a kd-tree but for 2D it's
probably still ok to do it that way (assuming the number of points is
not too big). You could write a functions like this:
/// any simple p-metric for p=1...infinity
double distance(const K2dCoords& a, const K2dCoords& b);
/// checks whether the set contains a point q with
/// distance(q,pnew) < epsilon
bool has_neighbour(const set<K2dCoords>& points,
const K2dCoords& pnew, double epsilon)
{
typedef set<K2dCoords>::const_iterator iter_t;
const K2dCoords corner1 (pnew.getX()-epsilon, pnew.getY()-
epsilon);
const K2dCoords corner2 (pnew.getX()+epsilon, pnew.getY()
+epsilon);
iter_t beg = points.lower_bound(corner1);
iter_t end = points.upper_bound(corner2);
while (beg!=end) {
if (distance(pnew,*beg) < epsilon) return true;
++beg;
}
return false;
}
This should work for a lexical ordering and an epsilon>0. I didn't
test it, though. You get the idea.
Cheers!
SG