Repeated elements in a std::vector

Question

I have a std::vector and I want to check all the elements in it. If a certain element appears more than once, I signal an error.

This is how I did it:

std::vector<std::string> test;
test.push_back("YES");
test.push_back("YES");

for(int i = 0; i < test.size(); i++)
{
    if(test[i] > 1)
    {
        DCS_LOG_DEBUG("ERROR WITH COUNT")
    }
}

This did not work though I know how to count using the std::vector::count() method. But I want to get the count for each element, as opposed to counting everything... any ideas?

Answer 1

The simplest way is to std::sort the vector and then use std::adjacent_find.

---

However, if you don't want to sort the vector, you can do something like this in C++11:

#include <unordered_map>
#include <functional> // For std::hash<std::string>.
#include <string>
#include <iostream>

int main() {

    // Test data.
    std::vector<std::string> v;
    v.push_back("a");
    v.push_back("b");
    v.push_back("c");
    v.push_back("a");
    v.push_back("c");
    v.push_back("d");
    v.push_back("a");

    // Hash function for the hashtable.
    auto h = [](const std::string* s) {
        return std::hash<std::string>()(*s);
    };

    // Equality comparer for the hashtable.
    auto eq = [](const std::string* s1, const std::string* s2) {
        return s1->compare(*s2) == 0;
    };

    // The hashtable:
    //      Key: Pointer to element of 'v'.
    //      Value: Occurrence count.
    std::unordered_map<const std::string*, size_t, decltype(h), decltype(eq)> m(v.size(), h, eq);

    // Count occurances.
    for (auto v_i = v.cbegin(); v_i != v.cend(); ++v_i)
        ++m[&(*v_i)];

    // Print strings that occur more than once:
    for (auto m_i = m.begin(); m_i != m.end(); ++m_i)
        if (m_i->second > 1)
            std::cout << *m_i->first << ": " << m_i->second << std::endl;

    return 0;

}

This prints:

a: 3
c: 2

I didn't actually benchmark it, but this has a chance for being rather performant, for following reasons:

• Assuming the actual vector elements do not produce pathologically lopsided hashes, this is actually an O(n) algorithm, as opposed to O(n*log(n)) for sorting.
• We are using the hashtable of pointers to strings, not strings themselves, so there is no unnecessary copying taking place.
• We can "pre-allocate" hashtable buckets (we pass v.size() when constructing m), so hashtable resizes are minimized.

Answer 2

Specific element

Count is the standard way to go:

#include <algorithm>
...

    if (count (test.begin(), test.end(), "YES") > 1)
        std::cerr << "positive\n";

If you need more performance, you can do it the classic way:

bool exists = false;
for (auto const& v : test) {
    if (v == "YES") {
        if (exists) {
            std::cerr << "positive\n";
            break;
        }
        else exists = true;
    }
}

Any element multiple times

For large vectors, try std::set:

std::set<std::string> exists;
for (auto const &v : test) {
    if (!exists.insert(v).second)
        std::cerr << "positive\n";
}

In this approach, if you also want to be able to recognize whether you already mentioned its non-uniqueness, you may want to use std::multiset:

const std::multiset<std::string> counts (test.begin(), test.end());
for (auto const &v: test)
    if (counts.count (v) == 2) std::cerr << "meh\n";

If the container is small, and you just want to see if any element is there more than once:

auto multitimes = [&test] (std::string const &str) {
    return count(test.begin(),test.end(),str)>1;
};
if (any_of (test.begin(), test.begin(), multitimes))
    std::cerr << "something was there more than once\n";

Answer 3

You can use std::map and define a mapping from a key (string) to a count (int):

#include <map>
#include <string>
/* ... */
std::map<std::string, int> count_map;

/* ... */

count_map[key]++;

Answer 4

use std::count to count elements: http://www.cplusplus.com/reference/algorithm/count/

http://en.cppreference.com/w/cpp/algorithm/count

Answer 5

The easiest way to do what you want is to sort the array and then see which elements are met more than once. If you do not want to modify the array itself, you will have to create a copy. This is an O(n * lg n) solution with no extra space if you don't care about the order, and with O(n) extra space if you do.

sort(test.begin(), test.end());

// If you only care if there is a repeated element, do this:
int size = test.size();
unique(test.begin(), test.end());
if (test.size() != size) {
  cout << "An element is repeated.";
}

// If you do care which elements are repeated, do this:
for (unsigned index = 1; index < test.size(); ++index) {
  if (test[index] == test[index - 1] && (index == 1 || test[index - 2] != test[index])) {
     cout << test[index] << " is repeated.";
  }
}

I have provided two solutions: The first is when you only care if a string is repeated, and the second is when you care exactly which strings are repeated.

Answer 6

If you don't mind extra space, try pushing the elements into a map. Whenever you find your element already in the map, you can signal the error directly.

map<string, int> occurrences;

for (vector<string>::const_iterator cit = test.begin(); cit != test.end(); ++cit)
    if ((++occurrences[*cit]) == 2)
        cout << "ERROR"; // You can even signal which element is repeated here easily, using *cit.

Note that this code correctly issues the message only once per repeated item (even if the item is repeated many times), as per the clever amendment by Tony Delroy. Though this way correctly counts the occurrence of every string in the entire collection (which may be something required), this way is subject to overflowing an int if there are 2³¹ copies of the same element (or more). You can use a long long int instead if this is the case and you really want the count of every string.

If you're not interested in the count of every string, an even more efficient way is using a set, as smerlin suggests (because it maintains the string only, not a pair of string and int as the map does), thus reducing space requirements... and issuing the error message whenever you find the item in the set:

set<string> occurrences;

for (vector<string>::const_iterator cit = test.begin(); cit != test.end(); ++cit)
    if (false == occurrences.insert(*cit).second)
        cout << "ERROR"; // You can even signal which element is repeated here easily, using *cit.

If you want to eliminate the problem before it happens, insert the elements into a set instead. It automatically removes duplicates. But take care that elements in a set are sorted, so you'll not preserve the insertion order. If you don't mind it, a set is much better, since searching into it and reading the elements out in sorted order are much more efficient.

Answer 7

One solution could be using two for loops.... i think it will be simple..

For example:

std::vector<std::string> test;
test.push_back("YES");
test.push_back("YES");

for(int i = 0; i < test.size(); i++)
{
    for(int j = 0; j < test.size(); j++)
    {
         if(i != j)
         {
              if(test[i] == test[j])
              {
                   DCS_LOG_DEBUG("ERROR WITH COUNT")
              }
         }
    }
}