473,325 Members | 2,342 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

Sparse arrays in C++

I want to implement a sparse tree in C++, using a vector; and by using the COW features of Linux, to minimize the number of physical page frames actually held.

See http://en.wikipedia.org/wiki/Copy_on_write

Since the tree is sparse, some large number of pages will be initialized to zero and never written to since only a few of the array cells are used. But under linux COW, pages allocated in the VM are never actually allocated as physical pages until a write occurs on the page in question.

Compare this with a Unix file w/ "holes" in it.

So the array may have a VM usage of 10**8 pages but only 10**4 page frames ever are allocated.

I know I can use this linux feature to implement a sparse array in C.

I am not so sure about C++.

Can anyone tell me if there is a way to achieve the same transparent allocations in C++?


P.S.
For whom it may concern:

IMPLEMENTATION DETAILS

The structs actually stored in the vector looks like this:

struct foo
{
long int payload[15]
char flags;
string label;
}

The root of the tree will have offset 0 in the array, and will be labeled "1".

Subtracting one from a label give the physical index of the corresponding array cell. Hence node 1 is stored at index 0, node 10 is stored at index 1, node 11 is stored at index 2, etc.

The address of the left child of some node labeled "X" is derived by shifting X << 1. Hence the left child of node 1 is labeled "10".

The address of the right child of some node labeled "X" is derived by shifting X << 1 and adding 1 . Hence the right child of node 1 is labeled "11".

The parent of some node "X" is derived by right shifting X >> 1. Hence the of the parent of node 10 is labeled "1".

All these operations are invariant throughout, and also reversible.

The flags variable of struct foo can be used to indicate status, as for example, if a node has any children and if so, how many.

Left shifts are zero filled on the right; right shifts are zero-filled on the left.
Aug 17 '10 #1
1 3198
weaknessforcats
9,208 Expert Mod 8TB
You might try an array of foo*. No need to actually create the struct variable until you need it. Use 0 to indicate a vacant array element.

The C code should work in C++ as well.
Aug 18 '10 #2

Sign in to post your reply or Sign up for a free account.

Similar topics

34
by: Christopher Benson-Manica | last post by:
If an array is sparse, say something like var foo=; foo=4; foo='baz'; foo='moo'; is there a way to iterate through the entire array? --
6
by: Michael Gray | last post by:
VS 2003 VB.net Win2000 SP4 The System.Array class seems to be limited to 32 bit addresses, meaning that one can only assign 2^32 elements. Is there any way that I can have an array that...
38
by: djhulme | last post by:
Hi, I'm using GCC. Please could you tell me, what is the maximum number of array elements that I can create in C, i.e. char* anArray = (char*) calloc( ??MAX?? , sizeof(char) ) ; I've...
15
by: skr13 | last post by:
Hi, I am implementing an aggregation model to compute data cubes. I have implemented the multiway array aggregation statically. That is if there are, say, 4 dimensions each of cardinality 16 and...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.