1

How can I create an array such that I could access the elements a[1000000], a[1] and a[2] and not even using the size of 1000000?

If possible please provide the answer in C++.

Rarblack
  • 4,559
  • 4
  • 22
  • 33
Sahil Silare
  • 313
  • 2
  • 3
  • 15
  • 1
    It's called sparse array, STL doesn't implement it. So either do your own or find a library. Or maybe you don't actually need it because hash map can be used the same way. – Quimby Oct 16 '18 at 05:03
  • 1
    Why? What are you trying to do? Are you filling the other elements, or is this just some kind of exercise? – Tas Oct 16 '18 at 05:09
  • See I have an array of length say N and I want to count the frequency of each element in it, where N – Sahil Silare Oct 16 '18 at 05:11
  • If you want to build a frequency association, a map (ordered or not) will likely give you *exactly* what you're looking for. If you need the association ordered as well (i.e. after building the map, you want to show the top 10 most-frequent), a partial sort will be needed, but the standard library has routines for that as well. – WhozCraig Oct 16 '18 at 05:16
  • @SahilSilare If code is `count[arr[i]]++` then **each** element of the array `count[]` needs an initial value - such as 0. So prior to any incrementing the _entire array_ is initialized/assign and _accessed_. Instead of an _array_, code could use `unsigned *count = calloc(1000000, sizeof *count);` and see [Why is malloc not “using up” the memory on my computer?](https://stackoverflow.com/q/19991623/2410359) to "save" memory. Is using a pointer to memory OK rather than using an array? – chux - Reinstate Monica Oct 16 '18 at 05:42

1 Answers1

3

Use std::unordered_map<>.

enum { N = 9 };
int arr[N] = { 0 };
std::unordered_map<int, int> m;
for (int i = 0; i < N; i++)
{
    ++m[arr[i]];
}
Sid S
  • 6,037
  • 2
  • 18
  • 24
  • What if I had 10E5 distinct elements then will you assign every element like this? – Sahil Silare Oct 16 '18 at 05:09
  • If you have 100000 elements to assign, assign 100000 elements. – Sid S Oct 16 '18 at 05:10
  • @SahilSilare Exactly the same syntax and usage you would proffer for a regular array. The point of the `operator[]` is to give key access. This is probably going to give you the best bang for he buck. If you need ordered enumeration a regular `map` will work instead. It is very usage dependent, so look at your problem(s) being solved and choose accordingly. – WhozCraig Oct 16 '18 at 05:11