迭代排序列表并计数不同的数字

Question

我想遍历排序列表以获取不同数字的数量。

请在下面找到我的尝试。列表的大小是k*k。 当列表被排序时，我会比较连续的项目来识别重复项目。

int count_distinct(list<int> v) 
{ 
    int num = k*k; 
    std::list<int>::iterator it; 
    it = v.begin(); 
    for (int a=0; a<k*k-1; a++) 
    { 
     if(*it == *it+1) 
      num--; 
     it++; 
    } 

    return num; 
} 

我不能改变的列表，所以std::list::unique()是不是一种选择。制作一份清单或独特物品的副本太慢，对我来说很有用。

Answer 1

你的代码有以下问题：

1. 按值传递容器的功能。你应该通过const引用来减少速度和内存丢失。
2. 您的状况*it == *it+1始终为假（您比较n和n+1）。可能你想写*it == *(it+1)，但std::list有bidirectional iterators，你不能+1他们。

的代码应该是这样的：

size_t count_distinct(const std::list<int>& l) { 
    if (l.empty()) return 0; 

    size_t distinct = l.size(); 
    auto prev = l.begin(); 

    for (auto cur = std::next(prev); cur != l.end(); ++cur, ++prev) { 
     if (*cur == *prev) 
      --distinct; 
    } 

    return distinct; 
} 

或者你可以写std::unique算法的修改版本：

template<class ForwardIt> 
size_t unique_cnt(ForwardIt first, ForwardIt last) { 
    if (first == last) 
     return 0; 

    size_t distinct = 1;  
    ForwardIt prev = first; 

    while (++first != last) { 
     if (!(*prev == *first)) { 
      ++distinct; 
     } 
     prev = first; 
    } 
    return distinct; 
} 

，然后简单地使用它

size_t distinct = unique_cnt(l.begin(), l.end());   

还有一个std::unique_copy +自定义迭代器方法，但它看起来不够优雅。

Answer 2

如何使用std::set来抓取独特的元素数量？

size_t count_distinct(const list<int>& v) 
{  
    std::set<int> temp (v.begin(), v.end()); 

    return temp.size(); 
} 

Answer 3

假设你想找到该列表中唯一整数的数量，以及列表不排序，你可以使用一组临时或unordered_set这样的：

size_t count_distinct(list<int> v) 
{ 
    std::unordered_set<int> distinct; 
    for(auto &x : v) 
    { 
     distinct.insert(x); 
    } 
    return distinct.size(); 
} 

Answer 4

这里是一个解决方案用于提取所有唯一值 的容器（因为你说你想以后使用它们）：

的方法计独特的价值观：

template < typename T > 
size_t count_unique(const std::list<T> & input) 
{ 
    std::set<T> unique(input.begin(), input.end()); 
    return unique.size(); 
} 

的方法提取唯一值的列表：

template < typename T > 
void unique(const std::list<T> & input, std::list<T> & output) 
{ 
    std::set<T> unique(input.begin(), input.end()); 
    std::copy(unique.begin(), unique.end(), std::back_inserter(output)); 
} 

的样本程序：

int main(int argc, char** argv) 
{ 
    std::list<int> list = { 1, 3, 4, 10, 3, 1, 6, 7 }; 
    std::list<int> out; 

    std::cout << count_unique(list) << std::endl; 

    unique(list, out); 
    for (auto & x : out) 
     std::cout << x << std::endl; 
} 

Answer 5

您可以使用std::list<int>::unique()让所有不同的元素在v和size()数他们。 v必须排序。检查v是否使用函数std :: is_sorted（）进行排序。如果没有 - 对它进行分类。这也意味着count_distinct不适用于常量列表对象。

size_t count_distinct(list<int>& v) 
{ 
    if (!is_sorted(v.begin(), v.end())) 
    { 
     v.sort(); 
    } 
    v.unique(); 
    return v.size(); 
} 

Answer 6

对于排序的数据，你可能没有比你试图实现直接的方法更有效。

我更愿意沿着这行的东西，因为我觉得它更直观计数的向上而不是向下：

std::size_t count_unique_sorted(std::list<int> const& l) { 
    if (l.empty()) return 0; 
    std::size_t count = 1; 
    auto previous_value = l.front(); 
    // TODO: hope that the compiler fixes that redundant first comparison... 
    for (auto next_value : l) { 
     if (next_value != previous_value) { 
      // the value changed! increment count and update previous_value 
      ++count; 
      previous_value = next_value; 
     } 
    } 
    return count; 
} 

您也可以使std::unique_copy()算法来计算，而不是副本，通过提供一个自定义OutputIterator。但与上面介绍的方法相比，这对性能没有多大的益处。当C++ 17的算法的parallel implementations变得可用时，也许值得重温一下。

下面是一个例子：

template <typename T> 
struct counter : public std::iterator<std::output_iterator_tag, T> { 
    explicit counter(std::size_t& count) : count(count) {} 
    counter& operator*() { return *this; } 
    counter& operator++() { return *this; } 
    void operator=(T const&) { ++count; } 
private: 
    std::size_t& count; 
}; 

std::size_t count_unique_sorted2(std::list<int> const& l) { 
    std::size_t count = 0; 
    std::unique_copy(l.begin(), l.end(), counter<int>(count)); 
    return count; 
} 

注意，在这两种情况下，你想要通过列表为const引用，而不是作为一个进入副本功能。

如果你觉得这个还是要慢，感觉自由探索并行的乐趣。这样做的好处可能取决于数据量和分布。所以你应该开始一些系统的分析。

除非你需要重新排序值很多，考虑到你的数据转储到std::vector<int>摆在首位。具有随机访问迭代器简化了操作，并具有更好的地方还可以加快速度...