   Using 3d points in std::set or std::sort / std::binary_search
  Hey Guys,I have some triangles and i am trying to come up with 2 lists..A) The unique points of all the trianglesB) A list of "triangles" which is just a struct with an index into the 1st list for points A,B,CMy algorithm is this:for each triangle{  if point A doesn't exist in the point list, add it.  Get the index of point A from the point list  if point B doesn't exist in the point list, add it.  Get the index of point B from the point list  if point C doesn't exist in the point list, add it.  Get the index of point C from the point list  Add a triangle to the triangle list made up of on Index A,B and C}  That's all well and good but i figured instead of rolling my own data structures and routines that i'd use STL.Well i'm hitting a snag with the list of unique points.  As far as i can tell i can go one of two routes and they both have issues.#1 - I can use a std::set to store my unique point list in.  This is great because it's designed to store unique items.  The problem however is there doesn't seem to be a way to index into a set by a numerical value.  IE there is no [7]th element to a set, so i cant say my triangle uses vert 7.#2 - I can use a std::vector and keep it sorted so that i can do a binary search to quickly find if an element exists in a list or not.  This is a problem because both the sort and binary search functions require a way to compare the 2 items which in this case are 3 points in space.  I can't figure out a way to compare 2 points in space such that it can build a sorted list of points Well actually, maybe for #2 i could sort them by their distance from 0,0,0?  Actually that won't work because then 2 points that were equally distant from the origin would get treated as if they were the same vector.I've thought about hashing the vectors too but am worried about hash collisions (should i be?)Anyways, what do you guys think, how is it best to go about doing something like this with STL?   
  You should be able to use lexicographical comparison for this. This should meet the 'strict weak ordering' comparator requirements for sort() and lower_bound(), meaning you can use the second option you described above. (Unless I'm overlooking something, that is.)Of course if performance isn't an issue, you could just use find().(Also, I'm assuming here that equivalent vertices are known to be exactly equal, and that floating-point precision won't be an issue.)   ;  What would that comparison look like?I tried this...if(A.x >= B.x)  return false;if(A.y >= B.y)  return false;if(A.z >= B.z)  return false;return true;but that didn't work because there are points such that A < B and B < C but A > C.also if i do the distance check, if something is equally distant it will incorrectly say that it's equal.But yeah, the verts are known to be exactly equal, so the floating point side of the battle should be fine :P   ;  I can't guarantee I'll get this right, but here's some pseudocode:if a.x < b.x    return trueelse if a.x > b.x    return falseelse    if a.y < b.y   return true    else if a.y > b.y   return false    else   return a.z < b.z    end ifend ifIf I messed anything up there, I'm sure someone will point it out.Or, if you can guarantee that the elements of your vector are contiguous in memory, you can use std::lexicographical_compare(), e.g.:return std::lexicographical_compare(&a.x, &a.x + 3, &b.x, &b.x + 3);;  Oh cool thanks Jyk (:It totally makes sense now.  essentially, you are treating the 3 numbers as a single number either by literally doing a memory comparison of the bytes using the std:: function, or by doing it by hand with < and > of the componentsThat's really cool, im going to remember that   ;  You can't index into a set, so triangles would have to store duplicate vertex data.  In this case all the set does is give you a list of unique vertices in case you need it, but doesn't actually cut down on memory usage.A vector on the other hand will allow you to use indexes and eliminate the duplicates, however it's a little more involved:1)  Iterate triangles, add all vertices -- O(N) assuming vector is conservatively resized beforehand.2)  Sort vertices with std::sort -- O(N ln(N)).3)  Remove duplicates using erase-unique idiom -- O(N).4)  Iterate triangles again to determine final indexes -- O(N ln(N)).But it's probably going to be better than trying to do it all in one pass, since for that you'd need to write your own binary search (standard library version doesn't give you an insertion location), which is deceptively difficult (someone else will post the obligatory link I can't recall off the top of my head).  Plus insertions into a vector are O(N), and there are N vertices, meaning you're looking at O(N2) right off the bat.You can try both approaches and see which one works best, though.  I'm sure that the best choice changes depending on the number of vertices and triangles you have.NOTE:  You can compare vertices on a per-coordinate basis:if(a.x == b.x)  if(a.y == b.y)    return a.z < b.z;  return a.y < b.y;return a.x < b.x;;Quote:Original post by Atrix256What would that comparison look like?if (a.x < b.x) return true;if (b.x < a.x) return false;if (a.y < b.y) return true;if (b.y < a.y) return false;return a.z < b.z;;Quote:Original post by DevFredQuote:Original post by Atrix256What would that comparison look like?if (a.x < b.x) return true;if (b.x < a.x) return false;if (a.y < b.y) return true;if (b.y < a.y) return false;return a.z < b.z;Hehe...that question has been answered three times now :) (In various forms...)Quote:Original post by Atrix256essentially, you are treating the 3 numbers as a single number either by literally doing a memory comparison of the bytes using the std:: function, or by doing it by hand with < and > of the componentsActually, std::lexicographical_compare() doesn't (in general) perform a byte-level memory comparison, but rather applies a standard lexicographical comparison relative to the input type (float, in this case) using the < operator or a custom comparator.   