Finding a distinct values from a pointer array

I have got a program from Google which exactly meets one of my demand of obtaining the distinct values count from an array.
I will be using this as a small function in my 3D reconstruction program.
I have to define a dynamic array instead of static array in order to resolve memory issues.
Since my program is computationally demanding, I want to give this step as minimum execution time as possible.
I am compiling this program with ECLIPSE CDT in 64 bit Ubuntu 12.04 LTS with 8GB RAM.
Here is a sample of code I am using.
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <algorithm>
#include <set>

class Solution {
public:
	template<size_t N>
	static size_t distinct(unsigned int (&a)[N]) {
		std::cerr << "DEBUG: size of array: " << N << " elements" << std::endl;
		return std::set<unsigned int>(a, a + N).size();
	}

	template<size_t N>
	static size_t distinct_optim(unsigned int (&a)[N],unsigned int* result) {
		std::sort(a, a + N);
		unsigned int* newend = std::unique(a, a + N);
		result=newend;
		return newend - a;
	}
};
int main() {

	unsigned int* result;
	unsigned int distinctcount;
	/// using static array
	//  case I
	unsigned int data[] = { 19415, 2611, 12092, 3942, 2535, 12105, 21079, 4660, 3,
	        27131, 13647, 24428, 15159, 9029, 24827, 979, 17194, 25102, 3631,
	        20914, 3223, 25801, 6652, 26208, 77, 15606, 8764, 1896, 7430, 24323,
	        152, 23805, 4259, 11243, 13367, 23559, 19293, 18581, 1639, 15671,
	        7929, 18386, 5168, 13816, 465, 15801, 16750, 3340, 202, 10412, 11068,
	        13458, 24304, 14814, 6530, 1178, 974, 12882, 757, 583, 4897, 24541,
	        12490, 119, 2240, 4833, 569, 24700, 24522, 8708, 9760, 26837, 26060,
	        20914, 3223, 25801, 6652, 26208, 77, 15606, 8764, 1896, 7430, 24323,
	        3377, 6972, 25689, 2334, 1567, 21670, 23233, 14711, 4650, 4703, 25057,
	        16057, 19488, 14575, 18936, 13346, 2779, 5644, 17165, 4526, 4390,
	        9616, 2413, 14459, 1070, 4079, 22126, 9063, 4362, 8182, 24439, 23625,
	        7929, 18386, 5168, 13816, 465, 15801, 16750, 3340, 202, 10412, 11068,
	        4184, 25930, 24767, 2785, 17361, 18033, 12366, 20548, 3831, 4101,
	        16841, 193, 23217, 6351, 19077, 23565, 10482, 4100, 27488, 15956,
	        2577, 7161, 20943, 25708, 2877, 7900, 4564, 3647, 12008, 1648,
	        10533 };

	//  case II
	/*unsigned int data[2093999];
	for (int i=0;i<1000000;i++)
	     data[i]=i;
	for (int i=500000;i<900000;i++)
	      data[i]=i;
	}*/


	/// using pointer array
	/*unsigned int* data;
	 data = (unsigned int*) malloc(472571 * sizeof(unsigned int*));
	 for (int i=0;i<50000;i++)
	 data[i]=i;*/



// using std::set (max O(n) additional storage)
std::cout << Solution::distinct(data) << std::endl;

// using std::unique (inplace mutation; no additional storage)
distinctcount=Solution::distinct_optim(data,result);
std::cout << distinctcount << std::endl;
//delete (data);
for (int i=0;i<distinctcount;i++)
std::cout<<result[i]<<std::endl;
}


I have faced the following problems.
I would be really grateful if someone can give me solution to these problem.
Problem No.1
If I declare static array as shown in Case I & Case II in the example, the count is displayed correctly. But, when I used the pointer array, the program terminate with the following error:
Invalid arguments 'Candidates are:
unsigned long int distinct_optim(unsigned int (&)[#0], unsigned int *)'
TEST.cpp /TEST/src line 75 Semantic Error

I tried to do some modification but all went in vain due to lack of proper knowledge about pointer arrays.

Problem No.2
I tried to display the unique values but the result does shows garbage values.

Problem No.3
There is always limitation for the no of elements of the input array. For this example, I found the value to be around 2093999. I have no idea which factors affected this value.
Last edited on
Topic archived. No new replies allowed.