迭代排序列表並計數不同的數字

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>擺在首位。具有隨機訪問迭代器簡化了操作，並具有更好的地方還可以加快速度...