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