Quote:Original post by gohkgohk
But when i use std::map,
if i have 10000 element with a custom key,
will it access directly to a selected element
or
it will search the whole array to find that element(which will be time-consuming with large size map)?

Quote:Original post by gohkgohk
will it access directly to a selected element or
it will search the whole array to find that element(which will be time-consuming with large size map)?

Quote:Original post by _fastcall

Quote:Original post by gohkgohk
will it access directly to a selected element or
it will search the whole array to find that element(which will be time-consuming with large size map)?

Neither. It won't search the *whole* map for the element, but rather in a deterministic search, like a binary search tree would (not implying that it does).

My question is, for what reason do you need to use a std::map over a regular array?

EDIT:
I type too slow :)

Quote:Original post by Zahlman
A basic approach (not tested):

struct coordinate {  int x, y, z; // ranging 0..6 each in base array, anything in triangles  coordinate(int x, int y, int z): x(x), y(y), z(z) {}};typedef std::vector<coordinate> triangle_list;typedef std::map<coordinate, triangle_list> space_mapping;space_mapping base_array;// set uptriangle_list& t = base_array[coordinate(3, 5, 5)];t.push_back(coordinate(100, 250, 300));t.push_back(coordinate(200, 100, 219));// don't need to do anything special to start adding triangles to an empty location// remove everything from a location:base_array.erase(coordinate(4, 1, 4));// Copy all triangles in order to a single vector:triangle_list all_triangles;for (space_mapping::iterator it = base_array.begin(); it != base_array.end(); ++it) {  triangle_list& current_triangles = it->second;  std::copy(current_triangles.begin(), current_triangles.end(), std::back_inserter(all_triangles));}// Or if you just want to draw them in order, and you don't have to copy them to// a vertex buffer or anything, you could use std::for_each instead of std::copy// to call some function on each coordinate.

Or, just have one triangle list, and store indices in the map instead of triangle coordinates. But then you are responsible for updating everything if you try to insert an index in the middle. It will probably get very messy :)

Quote:Original post by qebab
Assuming that the implementation of std::map is relatively sane, you should have lookup times of O(lg n), which basically means that in a map with 1024 keys it will only have to perform (at MOST) 10 steps before returning to you the value. With modern day computers that's unlikely to be noticeably slow. Why don't you try the map first (I can imagine it would make things simpler for you), and if that's simply too slow, use an array instead?

Maps or hashtables are in general a pretty nifty idea in a lot of cases, and can make things a lot simpler for you. I'm not sure about your case (I didn't read too carefully), but I use them a lot, it's one of the most useful datastructures in widespread use.

space_mapping::iterator iter = base_array.find(coordinate(x,y,z));if (iter != base_array.end()) {    // x,y,z points to an occupied cube        // let's assign a reference to the triangle list...    triangle_list& t = iter->second;        // ...use t here...}else {    // x,y,z points to an empty cube}