4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Not really enough for a full answer, but m.insert(pair<int, int>(n, 0)) can be replaced with simply m.emplace(n, 0) saving you from writing out the pair constructor. \$\endgroup\$ – Kyle Nov 29 '18 at 8:04
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If my understanding is correct, count_if iterates over counts and increments p when it finds a unique input that occurred at least twice. ++counts[i] is a very clean map update, I've not seen this before and took me a moment to understand, but both the key and value are updated. Agree on logical comparison feedback. I've gone back and fort with false and !, I've used false more often for readability, but I'm at the point in my life we're brevity and speed are becoming more important. Brace indent was a paste error, but good catch and raised my awareness of this detail. \$\endgroup\$ – greg Nov 29 '18 at 0:04
  • 1
    \$\begingroup\$ Yes, ++counts[i] will insert a new record for i if it hasn't been inserted yet. That newly inserted record will have its count at 0. The ++ will then increment the current count. count_if just counts the number of elements in a collection that meet the specified criteria, so it basically just counts and returns the number of items for which your predicate returned true. \$\endgroup\$ – Jerry Coffin Nov 29 '18 at 1:39
  • 2
    \$\begingroup\$ It would also be quite easy to do with the original version, as it makes a copy. One could then sort copied vector, apply std::unique and get std::distance between begin and returned iterator. It is not really certain which version is better though. I've written this comment with relation to the one above, but it seems to be deleted now. \$\endgroup\$ – Incomputable Nov 29 '18 at 11:37
  • \$\begingroup\$ You might want to attach a caveat to the suggestion to use an array, since int has a much wider range of values than char (so we're not in quite the same context as that other question). \$\endgroup\$ – Toby Speight Nov 29 '18 at 11:49
  • 1
    \$\begingroup\$ @Incomputable: yes, it was my comment, I had some doubts about its validity after reading the original question again. It might have been justified. / sadly std::unique doesn't do the job if what we need to count is the number of elements appearing at least twice \$\endgroup\$ – papagaga Nov 29 '18 at 11:57
5
\$\begingroup\$

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 << ',';

}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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