2017-10-18 98 views
3

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

请在下面找到我的尝试。列表的大小是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()是不是一种选择。制作一份清单或独特物品的副本太慢,对我来说很有用。

+2

'K +'?你确定吗? – melpomene

+1

'for(const auto num:v)'迭代列表。然后使用'std :: map '作为结果,并在'num'索引处计算'int'。 –

+3

输入列表是否已排序? – melpomene

回答

2

你的代码有以下问题:

  1. 按值传递容器的功能。你应该通过const引用来减少速度和内存丢失。
  2. 您的状况*it == *it+1始终为假(您比较nn+1)。可能你想写*it == *(it+1),但std::listbidirectional 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 +自定义迭代器方法,但它看起来不够优雅。

3

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

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

    return temp.size(); 
} 
+0

@Galik Opps是的,我只是蒙蔽了复制OP的片段。 – P0W

+0

@DanielTrugman肯定感谢 – P0W

+0

@DAle如果你有什么想法,你可以提供一个 – P0W

2

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

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

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

的方法独特的价值观:

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; 
} 
0

您可以使用std::list<int>::unique()让所有不同的元素在vsize()数他们。 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(); 
} 
+2

你应该添加一个注释,输入是需要排序的,而且它不适用于常量列表。 – moooeeeep

+0

@moooeeeep谢谢。我已经在打字了。 –

+1

结果应该是'size_t',而不是'int' –

1

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

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

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>摆在首位。具有随机访问迭代器简化了操作,并具有更好的地方还可以加快速度...