LinuxQuestions.org
LinuxAnswers - the LQ Linux tutorial section.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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.

Notices

Reply
 
Search this Thread
Old 12-24-2007, 07:23 AM   #1
Asuralm
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
Code:
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:

Code:
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:
Code:
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?

Thanks
Merry Christmas!!!

[/code]

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

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
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.
 
  


Reply


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 07:09 PM
c++ data structure libraries kpachopoulos Programming 2 01-16-2007 04:22 PM
Data structure trie spank Programming 7 05-21-2006 07:21 AM
data structure with variable capacity shivaligupta Programming 2 01-31-2005 11:54 AM
Wait Free Data Structure neo_119 Programming 0 11-27-2004 01:44 AM


All times are GMT -5. The time now is 03:20 AM.

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