c++如何打印每个整数在STL列表中出现的次数

Question

using namespace std;

int main()
{
    list<int> numbers; list<int> numb;

    for (int i = 0; i<10; i++)
        numbers.push_back(rand() % 20);

    list<int>::iterator it;

    for (it = numbers.begin(); it != numbers.end(); ++it)
    {
        cout << *it << " ";
    }

    return 0;
}

我想使用 std::count()，但我无法正确使用。我尝试执行以下操作：

using namespace std;

int main()
{
    list<int> numbers; list<int> numb;

    for (int i = 0; i<10; i++)
        numbers.push_back(rand() % 20);

    list<int>::iterator it;

    for (it = numbers.begin(); it != numbers.end(); ++it)
    {
        cout << *it << " ";

        while (it != numbers.begin() && it != numbers.end())
        {
            ++it;
            *it = count(it, numbers.begin(), numbers.end());
            cout << " " << *it;
        }

        cout << endl;
    }

    return 0;
}

但是它给我一个错误：

binary == no operator found which takes a left hand operator type 'int' (or there is not acceptable conversion).

我知道我做错了什么。

我也尝试了一些东西，比如int numb = std::count(numbers.begin()), numbers.end(), *it)，但也没有用。所以，我想知道是否有一个特殊的运算符来计算列表中的值。

Answer 1

我建议你使用地图：

map<int, int> counts;
for(int val : Numbers)
  ++counts[val];

Answer 2

您需要再次查看 std::count 的签名。它需要三个参数 std::count(InputIterator first, InputIterator last, const T& val); 和 returns 数据集中 val 的出现次数。所以像这样的东西应该适合你，其中 theNumber 是你正在计算的数字。

#include <algorithm>

int occurrences = std::count(numbers.begin(), numbers.end(), theNumber);

Answer 3

您没有正确使用迭代器（您正在修改 it，同时您仍在使用它迭代列表），并且您没有正确调用 std::count()。

代码应该更像这样：

#include <iostream>
#include <list>
#include <algorithm>
#include <cstdlib>

int main()
{
    std::list<int> numbers;
    int numb;

    for (int i = 0; i < 10; i++)
        numbers.push_back(std::rand() % 20);

    std::list<int>::iterator it;    

    for (it = numbers.begin(); it != numbers.end(); ++it)
    {
        numb = std::count(numbers.begin(), numbers.end(), *it);
        std::cout << *it << " " << numb << std::endl;
    }

    /* or:
    for (int value : numbers)
    {
        numb = std::count(numbers.begin(), numbers.end(), value);
        std::cout << value << " " << numb << std::endl;
    }
    */

    return 0;
}

但是，正如其他人所说，您应该使用 std::map 来跟踪计数，这样您就可以计算重复项，例如：

#include <iostream>
#include <list>
#include <map>
#include <cstdlib>

int main()
{
    std::list<int> numbers;
    std::map<int, int> numb;

    for (int i = 0; i < 10; i++)
        numbers.push_back(rand() % 20);

    for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it)
        numb[*it]++;

    /* or:
    for (int value : numbers)
        numb[value]++;
    */

    for (std::map<int, int>::iterator it = numb.begin(); it != numb.end(); ++it)
        std::cout << it->first << " " << it->second << std::endl;

    /* or:
    for (auto &item : numb)
        std::cout << item.first << " " << item.second << std::endl;
    */

    return 0;
}

可以简化为：

#include <iostream>
#include <map>
#include <cstdlib>

int main()
{
    std::map<int, int> numb;

    for (int i = 0; i < 10; i++)
        numb[rand() % 20]++;

    for (std::map<int, int>::iterator it = numb.begin(); it != numb.end(); ++it)
        std::cout << it->first << " " << it->second << std::endl;

    /* or:
    for (auto &item : numb)
        std::cout << item.first << " " << item.second << std::endl;
    */

    return 0;
}

Answer 4

一般来说，使用地图是解决问题的更好方法，但如果您必须使用列表来解决问题，这里有一个可能的解决方案：

#include <iostream>
#include <algorithm>
#include <list>

int main()
{
    std::list<int> numbers, unique_num, numb;
    int num;

    // Create both the original list and a list that
    // will be left with only unique numbers
    for (int i = 0; i<10; i++){
        num = rand() % 20;
        numbers.push_back(num);
        unique_num.push_back(num);
    }

    // Sort and select the unique numbers
    unique_num.sort();
    unique_num.unique();

    // Count unique numbers and store the count in numb
    std::list<int>::iterator iter = unique_num.begin();
    while (iter != unique_num.end())
        numb.push_back(count(numbers.begin(), numbers.end(), *iter++));

    // Print the results
    for(std::list<int>::iterator iter1 = unique_num.begin(), iter2 = numb.begin();
            iter2 != numb.end(); iter1++, iter2++)
        std::cout<< "Number " << *iter1 << " appears " <<
          *iter2 << ( *iter2 > 1 ? " times " : " time" ) << std::endl;

    return 0;
}

该程序使用另一个列表 unique_num 来保存出现在 numbers 中的唯一数字。该列表最初创建时与 numbers 相同，然后进行排序并删除重复项。

程序然后遍历该唯一列表中的数字，并使用计数来获取每个数字在原始 numbers 列表中出现的次数。然后将出现的次数存储在新列表 numb 中。

打印时，程序使用三元运算符检查是否应打印 "time" 或 "times"，具体取决于结果是否暗示出现一次或多次。

注意 - 如果您每次运行您的程序都需要不同的列表值，您需要使用 srand 更改随机种子。在您的程序中包含 header #include <time.h> 并在您的 main.c 文件开头包含 srand(time(NULL)); 行。

Answer 5

有额外的内存：

您可以使用桶来获得复杂度 O(N + MAX_NUM)。所以当 MAX_NUM <= N 我们有 O(N):

#include <iostream>
#include <list>
#include <algorithm>
#include <ctime>

const int MAX_NUM = 20;
const int N = 10;

int main() {
    std::list<int> numbers;
    int buckets[MAX_NUM];

    std::fill(buckets, buckets + MAX_NUM, 0);

    srand(time(NULL));

    for (int i = 0; i < N; i++) numbers.push_back(rand() % MAX_NUM);

    // computing
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        buckets[*it]++;
    }

    //printing answers
    for (int i = 0; i < MAX_NUM; i++) {
        if (buckets[i]) std::cout << "value " << i << " appears in the list " << buckets[i] << " times." <<std::endl;
    }

    return 0;
}

对于大数据，我建议对桶使用 std::unordered_map，然后获得复杂度 O(N)（由于散列）：

#include <iostream>
#include <list>
#include <algorithm>
#include <ctime>
#include <unordered_map>

const int N = 10;
const int MAX_NUM = 20;
int main() {
    std::list<int> numbers;
    std::unordered_map<int, int> buckets;

    srand(time(NULL));

    for (int i = 0; i < N; i++) numbers.push_back(rand() % MAX_NUM);

    // computing
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        buckets[*it]++;
    }

    //printing answers
    for (auto & k_v : buckets) {
        std::cout << "value " << k_v.first << " appears in the list " << k_v.second << " times." <<std::endl;
    }
    return 0;
}

没有额外的内存：

更通用的方式，你可以用std::vector代替std::list和std::sort就可以了，然后用一个简单的for来统计值的变化。复杂度为 O(N log N)：

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

const int N = 10;
const int MAX_NUM = 20;

int main() {
    std::vector<int> numbers;

    srand(time(NULL));

    for (int i = 0; i < N; i++) numbers.push_back(rand() % MAX_NUM);

    // sorting
    std::sort(numbers.begin(), numbers.end());

    //printing answers for sorted vector
    if (numbers.size() > 0) {
        int act_count = 1;
        for (int i = 1; i < numbers.size(); i++) {
            if (numbers[i] != numbers[i -1]) {
                std::cout << "value " << numbers[i-1] << " appears in the list " << act_count << " times." <<std::endl;
                act_count = 1;
            } else {
                act_count++;
            }
        }
        std::cout << "value " << numbers[numbers.size() - 1] << " appears in the list " << act_count << " times." <<std::endl;
    }
    return 0;
}

您也可以在 std::list 上执行上述操作，也得到 O(nlogn)，但不能使用 std::sort：

#include <iostream>
#include <list>
#include <ctime>

const int N = 10;
const int MAX_NUM = 20;

int main() {
    std::list<int> numbers;

    srand(time(NULL));

    for (int i = 0; i < N; i++) numbers.push_back(rand() % MAX_NUM);

    // sorting
    numbers.sort();

    //printing answers for sorted list
    if (!numbers.empty()) {
        int act_count = 0;
        auto prev = numbers.begin();
        for (auto it = numbers.begin(); it != numbers.end(); it++) {
            if (*it != *prev) {
                std::cout << "value " << *it << " appears in the list " << act_count << " times." <<std::endl;
                act_count = 1;
            } else {
                act_count++;
            }
            prev = it;
        }
        std::cout << "value " << *prev << " appears in the list " << act_count << " times." <<std::endl;
    }

    return 0;
}

c++如何打印每个整数在STL列表中出现的次数

c++ how to print how many times each integer appears in the STL list

c++

stl

list

count

operators