Data Structures for Counting Duplicates and using std::vector::erase

Question

Problem

Dupe detection for a vector of ints. I simply want a count of the unique input characters that occurred at least twice. The goal is to count a dupe only once and ignore that input character if another dupe of it is seen in the future. A test input could look something like this vector<int> test = { 4,5,9,6,9,9,6,3,4 };

Looking for Feedback on

Looking for basic feedback on the data structures I'm using and the possibility of using the vector erase method to iterate and take advantage of the space allocated to my numbers vector instead of using a map to not count dups more than once. Any C++ 11 or 17 features I can take advantage of here too?

int countDuplicates(vector<int> numbers) {
    int dups = 0;
    set<int> s;
    map<int, int> m;
    for (int n : numbers) {
      if (s.insert(n).second == false && m.find(n) == m.end()) {
          dups++;
          m.insert(pair<int, int>(n,0));
          // better to remove from vector than increase space with the map?
          // numbers.erase(remove(numbers.begin(), numbers.end(), n), numbers.end());          
        } else {
          s.insert(n);
        }
    }

    return dups;
}

Answer 1

Basic Algorithm

At least if I understand the intent correctly, you simply want a count of the unique input characters that occurred at least twice.

In that case, I think I'd do something like this:

int count_dupes(std::vector<int> const &inputs) { 
    std::map<int, int> counts;

    for (auto i : inputs)
        ++counts[i];

    return std::count_if(counts.begin(), counts.end(),
                         [](auto const &p) { return p.second >= 2; });
}

I'd also consider using an array instead of a map, as outlined in an answer to an earlier question: https://codereview.stackexchange.com/a/208502/489 --but this can depend on the range of values you're dealing with. With a 16-bit int, it's no problem at all on most machines. With a 32-bit int (and no other constraints on values) it's still possible on many machines, but probably impractical. For arbitrary 64-bit int, an array won't be practical.

Parameter Passing

Right now, you're passing the input by value. This means when you call the function with some vector, a copy of the original vector will normally be made and passed to the function. As a general rule, something like a vector that's potentially large and slow to copy should be passed by reference to const, as shown in the code above.

Logical Comparisons

Comparing a Boolean value to true or false is generally a poor idea. if (x==true) is equivalent to if (x) and if (x == false) is equivalent to if (!x). Normally, if it's Boolean in nature, a variable should be given a name that reflects that nature, and should be used directly rather than being compared to true or false. For example, s.insert(n).second == false wold be better written as: if (!s.insert(n).second).

Some people (understandably, I guess) prefer to use the written form: if if (not s.insert(n).second). I've written C and C++ long enough that I have no difficulty with reading ! as meaning "not", but especially if it may be read by people less accustomed to programming, it may make more sense to use the words instead of symbols.

Formatting/Indentation

At least to me, this indentation looks a bit odd:

  if (s.insert(n).second == false && m.find(n) == m.end()) {
      dups++;
      m.insert(pair<int, int>(n,0));
      // better to remove from vector than increase space with the map?
      // numbers.erase(remove(numbers.begin(), numbers.end(), n), numbers.end());          
    } else {
      s.insert(n);
    }

If you use indentation like that consistently, I guess it's not necessarily terrible, but I think more people are accustomed to something more like this:

  if (s.insert(n).second == false && m.find(n) == m.end()) {
      dups++;
      m.insert(pair<int, int>(n,0));
      // better to remove from vector than increase space with the map?
      // numbers.erase(remove(numbers.begin(), numbers.end(), n), numbers.end());          
  } else {
      s.insert(n);
  }

...where each closing brace is vertically aligned with the beginning of the block it closes. As a side-note, there are almost endless debates about the efficacy of various bracing styles. I'm not going to advocate for or against any of the well known styles, but I think there's a fair amount to be gained from using a style that's well known, and then using it consistently. I don't see much to gain from style that's different from what almost anybody else uses.

Answer 2

I don't agree with @JerryCoffin on two accounts: algorithm and paramater passing, the latter being a consequence of the former. That's why I submit this extra review, even if @JerryCoffin's has already been accepted, and even if I agree with the other points he made.

When you design an algorithm, especially in C++, you want it to be as efficient as possible, in as many situations as possible. It's a good idea to take a look at existing algorithms in the standard library to see how it can be achieved, all the more when there is an algorithm there that is closely related to the one you're designing: std::unique, that removes all but the first of consecutive equivalent elements. What's interesting is 1) that it operates on a sorted range and 2) that it modifies the input sequence: thus it makes it optimal when the input sequence is already sorted, and also when it's disposable. Can we benefit from std::uniques interface in our largely similar problem? I would say so:

#include <algorithm>

template <typename Iterator>
int count_duplicates(Iterator first, Iterator last) {
    // requires a sorted range
    int count = 0;
    while (true) {
        first = std::adjacent_find(first, last);
        if (first == last) return count;
        first = std::adjacent_find(++first, last, std::not_equal_to<>());
        ++count;
    }
}

Let's now compare with @JerryCoffin's proposed solution, which allocates memory for a std::map and then has in all cases a complexity of O(n*log(n)) for populating it + O(n) for counting elements with a frequency higher than 1:

• if the input range is already sorted, this algorithm has O(n) complexity, which is better

• if the input range is disposable but not sorted, this algorithm has the same complexity (O(n*log(n)) for prior sorting and O(n) for counting), but doesn't allocate memory and has better cache locality

• if the input is neither sorted nor disposable, we have the same complexity and memory requirements (we need to copy the input range) but we keep the better cache locality

On the other hand it lacks the possibility of relying on a more efficient structure to count the occurrences of each element, such as an array or a hash table. We could then theoretically go from O(n*log(n)) to O(n) when looking for duplicates. But I'm still unconvinced because those data structures would be oversized if the input range has a small alphabet.

EDIT: I think I've read the submitted code and the question a bit too fast. If what we need is not only to count elements appearing at least twice, but erasing other elements of the vector, then the solution is different, even if most building blocks remain:

#include <vector>
#include <algorithm>
#include <iostream>

template <typename Iterator>
Iterator one_of_duplicates(Iterator first, Iterator last) {
    // requires a sorted input
    auto current = first;
    while (true) {
        // find a duplicated element, move it behind 'first' 
        // and find the next different element
        current = std::adjacent_find(current, last);
        if (current == last) return first;
        *first++ = std::move(*current);
        std::cerr << *current << std::endl;
        current = std::adjacent_find(current, last, std::not_equal_to<>());
    }
}


int main() {

    std::vector<int> data = { 0, 1, 2, 3, 4, 5, 1, 2, 2, 3, 5, 5, 5 };
    std::sort(data.begin(), data.end());
    data.erase(one_of_duplicates(data.begin(), data.end()), data.end());
    for (auto i : data) std::cout << i << ',';

}