Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL set with custom data type

Reply
Thread Tools

STL set with custom data type

 
 
cata.1972@hotmail.com
Guest
Posts: n/a
 
      02-24-2009
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
{
bool operator() (const K2dCoords* p1, const K2dCoords* p2) const
{
const double tol = 0.25 / 1E3;
return sqrt((p1->getX() - p2->getX()) * (p1->getX() - p2->getX
()) + (p1->getY() - p2->getY()) * (p1->getY() - p2->getY())) > tol;
}
};

The problem is that after I've inserted some point in my set, I cannot
find them:

// some initialisation data
const double inc = 0.25;
const double deckLength = 1.0;
const double deckWidth = 0.48;
double x = 0;
double y = 0;
const double PI = 3.1415926;
std::set<K2dCoords*, eq> stlMap;

// create some points and add them to my set
while (x <= deckLength)
{
while (y <= deckWidth)
{
const double xSp = x * cos(30.0 * PI / 180.0) - y * sin
(30.0 * PI / 180.0);
const double ySp = x * sin(30.0 * PI / 180.0) + y * cos
(30.0 * PI / 180.0);
stlMap.insert(new K2dCoords(xSp, ySp));
y += inc;
}
x += inc;
y = 0;
}

// check if I've got them; the test point are created in the same
way as they were created for insertion
x = 0;
y = 0;
while (x <= deckLength)
{
while (y <= deckWidth)
{
const double xSp = x * cos(30.0 * PI / 180.0) - y * sin
(30.0 * PI / 180.0);
const double ySp = x * sin(30.0 * PI / 180.0) + y * cos
(30.0 * PI / 180.0);
std::set<K2dCoords*, eq>::iterator it = stlMap.find(new
K2dCoords(xSp, ySp));
if (it == stlMap.end())
{
ASSERT(FALSE); // suerly this should not assert, but
it does (when x=0.25 and y=0)!!!
}
y += inc;
}
x += inc;
y = 0;
}

What am I doing wrong? Thanks.
 
Reply With Quote
 
 
 
 
joecook@gmail.com
Guest
Posts: n/a
 
      02-24-2009
On Feb 24, 7:16*am, (E-Mail Removed) wrote:
> Hi,
>
> I have structure representing a 2 dimesional point:


> 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
> {
> * * bool operator() (const K2dCoords* p1, const K2dCoords* p2) const
> * * {
> * * * * const double tol = 0.25 / 1E3;
> * * * * return sqrt((p1->getX() - p2->getX()) * (p1->getX() - p2->getX
> ()) + (p1->getY() - p2->getY()) * (p1->getY() - p2->getY())) > tol;
> * * }


> What am I doing wrong? Thanks.


Your sorting criteria doesn't allow for proper sorting. It just
returns if two elements are near each other. std::set relies on a
strict weak ordering. Your function therefore should never return A
< B is true as well as B < A is also true.
For elements that you want to consider equal, operator(A,B) and
operator(B,A) should both return false. For elements not equal,
operator(A,B) _must_ return the logically opposite value of operator
(B,A).

HTH,
Joe


 
Reply With Quote
 
 
 
 
Bart van Ingen Schenau
Guest
Posts: n/a
 
      02-24-2009
On Feb 24, 1:16*pm, (E-Mail Removed) 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):
>

<snip>
> What am I doing wrong? Thanks.


You are using a sorting criterion that std::set<> can't handle.
std::set<> does not care about the equality of two points, it wants to
know if P1 comes before P2 or not. Only if neither P1 comes before P2
nor P2 comes before P1, then P1 and P2 are considered to be equal.

Another problem is your use of tolerances. std::set<> also requires
that the following equation holds:
if P1 == P2 && P2 == P3 then P1 == P3
When using tolerances, there is a big chance that this equation does
not hold for all points in the set, and that is bad.

Bart v Ingen Schenau
 
Reply With Quote
 
SG
Guest
Posts: n/a
 
      02-24-2009
(E-Mail Removed) 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
 
Reply With Quote
 
cata.1972@hotmail.com
Guest
Posts: n/a
 
      02-24-2009
On 24 Feb, 14:31, SG <(E-Mail Removed)> wrote:
> (E-Mail Removed) 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- Hide quoted text -
>
> - Show quoted text -


Thank you all.
That's right, I want a data structure able to return me a point that's
close enough to a given point. I see now why the STL set won't work
and this problem is a lot more complicated than I initially thought.
There's no chance of getting one of this data structure into STL or
Boost in future, is there?
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
If I want to talk about the design of a custom non-STL data structurein c++ liam_herron C++ 1 04-08-2008 03:01 AM
stl container for interval data type alex.fishman@gmail.com C++ 3 07-04-2006 08:37 AM
stl hash_map and user defined data type update anjangoswami06@gmail.com C++ 1 06-02-2006 07:46 PM
Using STL map and set on large amount of data Eric C++ 13 07-13-2005 09:40 PM
The conversion of a char data type to a datetime data type resulted in an out-of-range datetime value. luna ASP .Net 1 02-13-2004 01:15 PM



Advertisments