Calculate frequency of triples in a C array for indexing

Question

I have an array of integers (possibly thousands), like

int p[] = {0, 0, 0, 1, 0, 1, 2, 0, 2, 1, 0, 1, 0, 0, 0, 3, 0, 3, 5, 1, 7, ...

from which I want to generate a set of indices for each unique triple; for the list above, something like:

0, 1, 2, 1, 0, 3, 4, ...

I've coded up a simple C++ implementation (though a plain C or Obj-C implementation would do just as well or better), but am sure there's room for improvement:

for (int i = 0; i < 24*3; i++) {
    std::ostringstream sstr;
    sstr << p[3*i] << "," << p[3*i + 1] << "," << p[3*i + 2];
    freq[sstr.str()] += 1;
}

for (auto i = freq.begin(); i != freq.end(); i++) {
    std::cout << i->first << " => " << i->second << std::endl;
}

This just counts the frequencies of each triple, but could be trivially adapted to assign the desired indices. My question is, how can this be made more time/space efficient (bearing in mind that the runtime target is a mobile device)? Specifically,

1) What might be a better data structure than std::map for this purpose? I'd like to avoid introducing new dependencies (e.g. boost, unless it's header-only) 2) Is there a better key to use than a string? I thought about using a number for space efficiency, such as 5^a * 3^b * 2^c, but was concerned about exceeding numerical limits 3) Is there a better algorithm/approach than the one outlined here?

Answer 1

Agreed with Armen that it's generally OK. I would probably make a map with triples as keys and a set of indices as values:

typedef std::set<size_t> index_set;
typedef std::tuple<int,int,int> triple;
typedef std::map<triple, index_set> frequency_map;

And then:

const auto t = std::make_tuple(p[i], p[i+1], p[i+2]);
freqs[t].insert(i);

Then every i in freqs[t] is such that (p[i], p[i+1], p[i+2]) equals t.