Повторяющиеся элементы в std :: vector

Question

У меня есть std::vector, и я хочу проверить все элементы в нем. Если определенный элемент появляется более одного раза, я сообщаю об ошибке.

Вот как я это сделал:

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")
    }
}

Это не сработало, хотя я знаю, как считать, используя метод std::vector::count(). Но я хочу получить количество для каждого элемента, а не для подсчета всего ... есть идеи?

Answer 1

Самый простой способ - std::sort вектор, а затем использовать std::adjacent_find.

---

Однако, если вы не хотите сортировать вектор, вы можете сделать что-то подобное в 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;

}

Это печатает:

a: 3
c: 2

Я на самом деле не тестировал его, но у него есть шанс быть довольно производительным по следующим причинам:

• Предполагая, что фактические векторные элементы не производят патологически односторонние хэши, на самом деле это алгоритм O (n), а не O (n * log (n)) для сортировки.
• Мыиспользуют хеш-таблицу указателей на строки, а не на сами строки, поэтому ненужное копирование не происходит.
• Мы можем «предварительно выделить» сегменты хеш-таблицы (мы передаем v.size(), когдаm), поэтому размеры хеш-таблиц сведены к минимуму.

Answer 2

Конкретный элемент

Счет - это стандартный путь:

#include <algorithm>
...

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

Если вам нужно больше производительности, вы можете сделать это классическим способом:

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

Любой элемент несколько раз

Для больших векторов попробуйте std::set:

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

В этом подходе, если вы также хотите иметь возможность узнать, упомянули ли вы уже его неединственность, вы можете использовать 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";

Если контейнер маленький, и вы просто хотите увидеть, есть ли какой-либо элемент более одного раза:

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

Вы можете использовать std :: map и определить отображение из ключа (строки) в число (int):

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

/* ... */

count_map[key]++;

Answer 4

Если вы не возражаете против дополнительного пространства, попробуйте вставить элементы в map.Всякий раз, когда вы найдете свой элемент на карте, вы можете напрямую сообщить об ошибке.

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.

Обратите внимание, что этот код правильно выдает сообщение только один раз для повторяющегося элемента (даже если элемент повторяется много раз),согласно умной поправке Тони Делрой .Хотя этот способ правильно подсчитывает вхождение каждой строки во всей коллекции (что может быть чем-то обязательным), этот путь может быть переполнен int, если имеется 2 ³¹ копий одного и того же элемента (илиБольше).Вместо этого вы можете использовать long long int, если это так, и вы действительно хотите счетчик каждой строки.

Если вам не интересен счетчик каждой строки, еще более эффективный способ - использоватьset, как предлагает smerlin (поскольку он поддерживает только строку, а не пару строк и int, как map), тем самым уменьшая требования к пространству ... и выдает сообщение об ошибкевсякий раз, когда вы находите предмет в наборе:

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.

Если вы хотите устранить проблему до того, как она возникнет, вставьте элементы в set.Он автоматически удаляет дубликаты.Но позаботьтесь о том, чтобы элементы в set были отсортированы, чтобы вы не сохранили порядок вставки.Если вы не возражаете, set намного лучше, поскольку поиск в нем и чтение элементов в отсортированном порядке намного эффективнее.

Answer 5

Самый простой способ сделать то, что вы хотите, это отсортировать массив и посмотреть, какие элементы встречаются более одного раза.Если вы не хотите изменять сам массив, вам придется создать копию.Это решение O (n * lg n) без лишних пробелов, если вы не заботитесь о порядке, и с O (n) лишними пробелами, если вы делаете.

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.";
  }
}

Я предоставил дварешения: во-первых, когда вам нужно только, если строка повторяется, а во-вторых, когда вам важно, какие именно строки повторяются.

Answer 6

используйте std :: count для подсчета элементов: http://www.cplusplus.com/reference/algorithm/count/

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

Answer 7

Одним из решений может быть использование двух для циклов .... я думаю, что это будет просто ..

Например:

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")
              }
         }
    }
}