Help answer threads with 0 replies.
Go Back > Forums > Non-*NIX Forums > Programming
User Name
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.


  Search this Thread
Old 12-24-2007, 08:23 AM   #1
LQ Newbie
Registered: Nov 2007
Posts: 26

Rep: Reputation: 15
A data structure problem

Dear All:

I want to build a 3D Euclidean space by using an index accessible class like
3DSpace<T*> my_space[1000][1000][1000];
my_space[100][50][25] = ....;
The space should be able to contain more than 1 million gridpoints although most of them will be NULL. Here I am looking for a method which can allocate memory for the gridpoints with content and meantime do not allocate memory for those gridpoints which are NULL. As this is probably the only way to hold such a large data space. For example:

T* grid_point;
my_space[100][50][25] = grid_point;
T* get_point = my_space[0][0][0];
// here get_point should give a NULL pointer. As (0,0,0) is not given a value.
I tried the STL library hash_map, but the drawback of the hash_map is:
hash_map<int, float> my_hash;
my_hash[0] = 10.5;
cout << "size of my_hash=" << my_hash.size() << endl;
// This gives: size of my_hash=1;
float get_number = my_hash[10];
// obviously this should throw an exception as my_hash[10] is not given a value. 
// But the hash_map doesn't throw an exception and increases the size of the container
cout << "size of my_hash=" << my_hash.size() << endl;
// this gives: size of my_hash=2;
This is a really bizarre behaviour which is definitely not what I wanted.
Does anyone have any idea to help me with this problem please?

Merry Christmas!!!


Last edited by Asuralm; 12-24-2007 at 08:26 AM.
Old 12-24-2007, 08:49 AM   #2
Senior Member
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,186

Rep: Reputation: 346Reputation: 346Reputation: 346Reputation: 346
1) Look at "sparse matrix" libraries.
2) Consider using a tree list where the "leaf" is your data and the address your coordinates, and your "look up" process process does a search in the tree for the coordinate token. If you keep the tree sorted, or hashed, or both, the look-up should be fairly fast.


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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 Off
HTML code is Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Linked list data structure in PHP? ivanatora Programming 6 08-24-2007 08:09 PM
c++ data structure libraries kpachopoulos Programming 2 01-16-2007 05:22 PM
Data structure trie spank Programming 7 05-21-2006 08:21 AM
data structure with variable capacity shivaligupta Programming 2 01-31-2005 12:54 PM
Wait Free Data Structure neo_119 Programming 0 11-27-2004 02:44 AM > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 03:02 PM.

Main Menu
Write for LQ is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration