在std :: vector中重复的元素 [英] Repeated elements in a std::vector

问题描述

我有一个 std :: vector ，我想检查其中的所有元素。如果某个元素出现多次，我会发出一个错误。

这是我怎么做的：

  std :: vector< std :: string>测试; 
 test.push_back（YES）; 
 test.push_back（YES）; 
 
 for（int i = 0; i  {
 if（test [i]> 1）
 
 DCS_LOG_DEBUG（ERROR WITH COUNT）
} 
} 
  

这没有工作，虽然我知道如何计数使用 std :: vector :: count（）方法。但是我想得到每个元素的计数，而不是计数一切...任何想法？

解决方案

是 std :: sort 的向量，然后使用 std :: adjacent_find 。

但是，如果你不想对向量进行排序，你可以在C ++ 11中做这样的操作：

  #include< unordered_map> 
 #include< functional> // For std :: hash< std :: string> ;. 
 #include< string> 
 #include< iostream> 
 
 int main（）{
 
 //测试数据。 
 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）; 
 
 //散列表的哈希函数。 
 auto h = []（const std :: string * s）{
 return std :: hash< std :: string>（）（* s）; 
}; 
 
 //散列表的平等比较器。 
 auto eq = []（const std :: string * s1，const std :: string * s2）{
 return s1-> compare（* s2）== 0; 
}; 
 
 //散列表：
 //键：指向v元素的指针。 
 //值：发生次数。 
 std :: unordered_map< const std :: string *，size_t，decltype（h），decltype（eq）> m（v.size（），h，eq）; 
 
 //计数发生。 
 for（auto v_i = v.cbegin（）; v_i！= v.cend（）; ++ v_i）
 ++ m [&（* v_i）]; 
 
 //打印多次出现的字符串：
 for（auto m_i = m.begin（）; m_i！= m.end（）; ++ m_i）
 if（m_i-> second> 1）
 std :: cout<< * m_i->第一<< ：<< m_i->第二< std :: endl; 
 
 return 0; 
 
} 
  

打印：

  a：3 
c：2 
  

我没有对其进行基准测试，但由于以下原因，这有机会表现出色：

• 向量元素不产生病理性偏心散列，这实际上是一个O（n）算法，而不是排序的O（n * log（n））。


• 我们使用散列表


• 我们可以预先分配哈希表桶（我们传递<$ 当构建 m ）时，c $ c> v.size（），因此hashtable调整大小被最小化。





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?

解决方案

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.

这篇关于在std :: vector中重复的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！