4
\$\begingroup\$

I've been writing code to get the frequencies of elements of an array. The code works, but it uses a lot of "old style" C constructs, some of which I feel should be changed to more C++-like features, but I don't know exactly which way would be best. In general, I feel that a lot of the code could be improved to be more elegant.

The first two functions, remdups and freq, are helper functions for getFrequencies, which is "facade" of the API.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>

template <class T> void remdups(T *arr, size_t *n)
{
    for (size_t i = 1; i < *n; ) {
        if (arr[i] == arr[i-1]) {
            memmove(arr + i - 1, arr + i, (*n-i) * sizeof (T));
            --*n;
        } else
            ++i;
    }
}

int *freq(const int *arr, size_t n, size_t *outN)
{
    int *freq = new int[n], cnt;

    for (size_t i = *outN = 0; i < n; ++i) {
        freq[i] = -1;
        cnt = 1;
        for (size_t j = i + 1; j < n; ++j) {
            if (arr[i] == arr[j]) {
                ++cnt;
                freq[j] = 0;
            }
        }
        if (freq[i] != 0) {
            freq[i] = cnt;
            ++*outN;
        }
    }

    // remove duplicate frequency entries
    remdups<int>(freq, outN);
    return freq;
}

std::vector<std::pair<int, size_t>> getFrequencies(std::vector<int> arr)
{
    size_t n = arr.size(), newSize;
    int *freqs = freq(&arr[0], n, &newSize);

    // remove duplicate values from the array
    remdups(&arr[0], &newSize);

    std::vector<std::pair<int, size_t>> ret;

    for (size_t i = 0; i < newSize; ++i)
        ret.push_back(std::pair<int, size_t> { arr[i], freqs[i] });

    delete []freqs;
    return ret;
}

Example driver code:

int main()
{
    std::vector<int> v = { 5, -3, -3, -3, -2, 0, 0 };
    auto freqs = getFrequencies(v);

    printf("%8s %8s\n", "Elem.", "Freq.");
    for (auto it = freqs.cbegin(); it != freqs.cend(); ++it)
        printf("%8d %8zu\n", it->first, it->second);
}
\$\endgroup\$
1
  • \$\begingroup\$ templates and std::vector are not part of C and will not compile in a strict C compiler. You might want to loose the old C I/O and use std::cin and std::cout. \$\endgroup\$
    – pacmaninbw
    Commented Feb 17, 2020 at 22:13

1 Answer 1

5
\$\begingroup\$

This seems over-complicated. A simpler solution would use a std::map or std::unordered_map for the counting:

std::unordered_map<int, std::size_t> counts;
for (auto const &element: container) {
     ++counts[element];
}

Instead of being tied to std::vector<int>, we could make the code much more flexible as a template, taking a pair of iterators (or, from C++20, a std::range) with any appropriate element type. The signature might look something like:

template<typename Iter>
auto getFrequencies(Iter begin, Iter end)
   -> std::unordered_map<decltype(*Iter), std::size_t>;

We might use constraints or SFINAE to choose whether to return an ordered or unordered map, based on whether *Iter is ordered and/or hashable.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ typename std::iterator_traits<Iter>::difference_type? That's what std::count returns. Also, should we give the user to specify the template arguments to std::unordered_map to enable usage with types for which something other than std::equal_to or std::hash has to be used? \$\endgroup\$
    – L. F.
    Commented Feb 18, 2020 at 10:18
  • 1
    \$\begingroup\$ Yep @L.F. makes sense. Perhaps easiest if the user just specifies the entire type of the map. Anyway, this answer was just a loose sketch to suggest a simpler approach, rather than a full worked example (more learning value that way, plus I'm busy IRL ATM). \$\endgroup\$ Commented Feb 18, 2020 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.