Whats the best way to update linked indices that were changed?

Dec 29, 2013 at 11:55pm
Hello, so basically I have 2 arrays where elements in array A contain some data including an index number of the other array B to "point" to the data there.

Now my question is if I want to remove elements from array B, what would be the most efficient way to do that (since I have to update the dependent indices from array A as well)?
Last edited on Dec 30, 2013 at 1:15am
Dec 30, 2013 at 12:15am
You could mark entries in B as valid/invalid. That way, you don't need to keep re-indexing A on deletion.

You'd probably need some separate re-indexing function that removes invalid entries from B, and adjusts the values in A.
Dec 30, 2013 at 12:25am
If I get your question correctly, A stores keys that give access to some elements in array B? Why not save yourself the trouble and directly access the indices of B rather than storing them in A? That way you are simply do:
B[1] = NULL;

Rather than
B[A[20]] = NULL;
Dec 30, 2013 at 12:33am
The problem is that both arrays get saved in a file and that file is being opened by another program so I can't simply change the format.

And I want to remove some elements from B to make the file smaller (because some elements from B are not present in A and useless).
However that would also involve truly removing the data from the array and thus changing the indices because otherwise I would just have to write empty data in the invalidated places which would end with the same result (unchanged file size).

edit:
I made a little code sample of how I would do it, however I'm not really sure if its the best way to do it (all the loops seem kind of expensive to me)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct{
   // some data types
   int index;    // an index number of ChildList
}ParentList;
	
struct{
   // some data types
}ChildList;

ParentList* A;
ChildList* B;

// A and B get filled here

// now remove useless entries from B
ChildList* C = new ChildList[sizeof(B)];

// first figure out what indices are not being used
bool used[sizeof(B)];
for(int i = 0; i < sizeof(B); i++)   // init with false
   used[i] = false;
for(int i = 0; i < sizeof(A); i++)   // flag used ones
   used[A[i].index] = true;
	
for(int i = 0, j = 0; i < sizeof(B); i++)  // copy used ones to C
{
   if(used[i])
      C[j++] = B[i];
}

for(int i = 0; i < sizeof(A); i++)   // update indices in A
{
   for(int j = 0; j < sizeof(C); j++)
   {
      if(B[A[i].index] == C[j])
         A[i].index = j;
   }
}
Last edited on Dec 30, 2013 at 1:05am
Dec 30, 2013 at 9:48pm
The sizeof operator does not return number of elements in said array. It returns the number of bytes...

If you want to get the number of elements in each array, you do:

sizeof Array / sizeof &Array[0]
http://ideone.com/L4Wo87
Dec 31, 2013 at 12:02am
I know, I just did that for the sake of the pseudo code to keep the code sample short and more simple.
Last edited on Dec 31, 2013 at 12:02am
Topic archived. No new replies allowed.