Sign in to follow this  

array VS std::map

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Does std::map work like normal array? normal array use number as key, std:;map use "custom key" as key In normal array, if i call one element in array , the program will access directly to that element internally. i.e. int array[10000]; a=array[123]; 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)? Thx

Share this post


Link to post
Share on other sites
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)?
As you note, array elements in C++ are stored contiguously, and element access is in constant time (this applies to the vector class template as well).

The map class template, on the other hand, is usually implemented as a binary tree. As such, element access is not constant time, but it's not linear time either. Queries usually involve a binary search, and should be pretty efficient even for large numbers of objects (this depends somewhat of course on the nature of the key; string keys, for example, may result in slower searches than, say, integer keys).

Share this post


Link to post
Share on other sites
Maps and arrays are completely different beasts. An array is an ordered collection of variables. A map is an unordered collection. Keys don't have to be sequential or even integers (though they must all be the same type). The map's data will be stored in some data structure such as a tree or heap. They won't be in a flat array.

As for lookups, that depends on the implementation. There will probably be some binary search type lookup going on. It's certainly not crawling through every single pair in the map looking for a match. Lookup times will get slower as you add more pairs to the map, but not as slow as crawling an array. Of course, if your keys are sequential, arrays (or vectors) are the fastest.

If you know big O notation, the "lookup" time for an array would be O(1) as it takes only a single multiplication. Assuming a std::map uses a binary tree and the tree remains balanced, lookup time will be O(log n). Insertions are also slower, as it first has to find the proper place in the tree to create the new pair.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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 :)

i want to do a modeling system,i discussed in http://www.gamedev.net/community/forums/topic.asp?topic_id=481107
which divided a workspace as a lot of cube,
if one cube contains triangles, i will use an array to store the list of triangle for that part of workspace.
If that cube do not contain triangles, i will delete it corresponding array.
voxel

And Zahlman suggest me to use std::map to perform this,
because it allow the direct insert or delete a array(vector corresponsing to one cube)

but now i afraid the searching time for std::map will be much longer than normal array ,when i divide the workspace into 256x256x256 cubes.

So can i use an array to replace std::map for this matter?
Thx

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 up
triangle_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 :)


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.


but is it possible to replace map by array?
because i may have 16777216 keys (for 256x256x256 cubes) X.X

is it possible to use a 3D pointer array to replace map?
i.e. use them to point to the address of vector (which store a list of triangle)

Share this post


Link to post
Share on other sites
You would have 256*256*256 keys if there are no empty cubes. It only stores the ones that contain triangles. Using Zahlman's code in the other thread, looking for a chunk of triangles by (x,y,z) would go something like this:

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
}

Share this post


Link to post
Share on other sites
If you went with the 3-Dimensional array of pointers you mentioned, you're already looking at 64 megabytes of RAM for just the pointers alone on a 32bit system, or 128mb on a 64bit system.

A std::map (or hashed-equivalent, such as TR1::unordered_map) is a better fit where the 3D array would be only sparsely filled.


I know this is for a voxel-based modeler, but are you sure that a form of Binary Space Partitioning wouldn't be more suitable?

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this