# Fastest way to get a range of value from a std::map

This topic is 3960 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

now i have a stucture called "coordinate" as my key of map. now i have struct array1 which stored sX sY sZ bX bY bZ: array1.sX=smallest X array1.sY=smallest Y array1.sZ=smallest Z array1.bX=biggest X array1.bY=biggest Y array1.bZ=biggest Z so now i have a range. My map is well ordered but with uncountable gap as follow. first order by x then order by y then order by z base_array[coordinate(1,1,1)]=2342; base_array[coordinate(1,1,3)]=345; base_array[coordinate(1,2,1)]=4353; base_array[coordinate(1,2,3)]=3453; base_array[coordinate(2,6,4)]=34; base_array[coordinate(2,6,5)]=2342; ....... how can i get value from the map faster than mine as follow which using a big "for" loop? For example: if i only want (1<=x<=2) && (2<=y<=3)&&(2<=z<=4) base_array[coordinate(1,1,1)]=2342; base_array[coordinate(1,1,3)]=345; base_array[coordinate(1,1,4)]=453; base_array[coordinate(1,2,1)]=4353; base_array[coordinate(1,2,3)]=3453;<------ this one match the requirement base_array[coordinate(1,3,6)]=45; base_array[coordinate(2,2,3)]=435; <------- this one match the requirement base_array[coordinate(2,4,6)]=4353; base_array[coordinate(2,6,1)]=3453; base_array[coordinate(2,6,2)]=436354; base_array[coordinate(2,6,3)]=234; base_array[coordinate(2,6,4)]=34; base_array[coordinate(2,6,5)]=2342; result: base_array[coordinate(1,2,3)]=3453; base_array[coordinate(2,2,3)]=435;
struct coordinate {
int x, y, z;
coordinate(int x, int y, int z): x(x), y(y), z(z) {}
};

struct compare
{
bool   operator()(coordinate   k1,coordinate   k2)  const
{  if (k1.x   !=   k2.x)
return   k1.x   <   k2.x;
else
if (k1.y   !=   k2.y)
return   k1.y   <   k2.y;
else
return   k1.z   <   k2.z;
}
};


for (int jx=array1.sX; jx<=array1.bX;jx++)
{
for (int jy=array1.sY; jy<=array1.bY;jy++)
{
space_mapping::iterator iters= base_array.find(coordinate(jx, jy, array1.sZ));
space_mapping::iterator itere= base_array.find(coordinate(jx, jy, array1.bZ));
for (space_mapping::iterator it = iters; it != base_array.end(); ++it)
{
triangle_list& current_triangles = it->second;
std::copy(current_triangles.begin(), current_triangles.end(), std::back_inserter(all_triangles));
if (it==itere) break;
}
}
}


THX~~ [Edited by - vic2005 on March 19, 2008 9:12:28 AM]

##### Share on other sites
You'd be better off implementing a spatial partitioning structure such as an octree. Or maybe use boost::multi_index_container<> to index and order the points along three different axes.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 9
• 9
• 34
• 16
• ### Forum Statistics

• Total Topics
634123
• Total Posts
3015656
×