Hi,

Pseudocode plus description of my problem.

I have a long array of structs, each containing three unsigned integers x, y, and z, and a variable that we'll use later.

struct A { unsigned int x,y,z; int index; }; //... struct A* long_array; //has thousands of elements, most are repeats

I need to know how many unique triplets there are.

After this is known, a new array is allocated, containing a new struct corresponding to each unique triplet. Then, in the original array, set each structure's index variable to the location of the unique struct in the new array.

int num_unique = /*what goes here*/; struct A* unique_array = new struct A[num_unique]; /* Now execute some algorithm that solves the following: for each element "elem" of long_array: unique_array[elem.index] has the same triplet as elem. */

C++11 is available, and everything else is fair game. I'm having trouble figuring out a good way.

I should note that the above isn't a prescriptive definition of an algorithm. I just need the end result--each struct in the original array points to its unique struct in the new array. For example, combining the two operations of counting and setting the index into one pass is perfectly fine.

As suggested in the title, there is an additional constraint: the algorithm needs to run in strictly O(n) time. This means that memory allocations of the std containers need to be taken into account. For example, one might cruftily try to solve the problem with a:

unordered_map<unsigned int,unordered_map<unsigned int,unordered_map<unsigned int,struct A*>>>

. . . that is constructed in a linear pass through the original array, but this doesn't work since the amortized allocations that must happen sum up to O(n^2) unless they are precomputed.

Bungling around with the std containers isn't exactly amenable to chance, so I'm asking for advice. Anyway, as above, any suggestions that solve the problem cleanly and quickly would be appreciated!

Thanks,

-G