标签： C++容器

C++:单词计数

问题

单词计数程序,有序和无序版本.

C++.
image-2147

有序源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*************************************************************************
    > File Name: test.11.39.cpp
    > Author: puruidong
    > Mail: 1@w1520.com
    > Created Time: 2014年07月15日
 ************************************************************************/

#include<iostream>
#include<map>
using namespace std;

/*********************************
 

    单词计数程序,字典序.


 *****************************************/

 int main()
 {
     cout << "单词计数程序,字典序:" << endl;
     map<string,int> map;
     string pa;
     while(cin >> pa)
     {
         ++map[pa];
     }
     cout << "输出计算结果:" << endl;
     for(const auto &s : map)
     {
        cout << s.first << " ------ "  << s.second << endl;
     }
     return 0;
 }

无序源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*************************************************************************
    > File Name: test.11.38.cpp
    > Author: puruidong
    > Mail: 1@w1520.com
    > Created Time: 2014年07月15日
 ************************************************************************/

#include<iostream>
#include<unordered_map>
#include<iterator>
using namespace std;


/*****************************************
 

    用unordered_map重写单词计数程序


 **************************************************/


 int main()
 {
     unordered_map<string,int> map;
     string pa;
     while(cin >> pa)
     {
         ++map[pa];//自增.
     }
    cout << "***********************\n统计结果:\n******************************" << endl;
     for(const auto &s : map)
     {
         cout << s.first << "\t************************\t" << s.second << endl;
     }
     cout << "输出桶的数目:" << map.bucket_count() << endl;
     cout << "最大能容纳的最多的桶的数量:" << map.max_bucket_count() << endl;
     cout << "第1个桶中有多少个元素:" << map.bucket_size(1) << endl;
     cout << "关键字a在哪个桶中:" << map.bucket("a") << endl;
     cout << "每个桶的平均元素数量:" << map.load_factor() << endl;
     cout << "容器试图维护的平均桶大小:" << map.max_load_factor() << endl;
     
     return 0;
 }

C++:查找并删除重复元素

问题

查找容器中的重复元素，并删除它们.

C++.
image-2094

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*************************************************************************
    > File Name: test.10.9.cpp
    > Author: puruidong
    > Mail: 1@w1520.com
    > Created Time: 2014年06月09日
 ************************************************************************/

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
/***********************
 
    查找并删除vector中的重复元素

 ***********************************/

void outv(vector<string> ves)
{
    for(vector<string>::const_iterator it=ves.begin();it!=ves.end();++it)
    {
        cout << "\t"  << *it << endl;
    }
    cout << "****************************" << endl;
}


void elimdups(vector<string> &ts)
{
    cout << "**********************\n未排序前的vector:" << endl;
    outv(ts);
    sort(ts.begin(),ts.end());
    cout << "排序后:" << endl;
    outv(ts);
    auto un_begin =  unique(ts.begin(),ts.end());
    cout << "unique后:" << endl;
    outv(ts);
    ts.erase(un_begin,ts.end());
    cout << "erase删除后:" << endl;
    outv(ts);
}


int main()
{
    string v;
    vector<string> vec;
    cout << "输入多个相同元素:" << endl;
    while(cin >> v)
    {
        vec.push_back(v);
    }
    elimdups(vec);
    return 0;
}

问题2

你认为算法不改变容器大小的原因是什么？

解答

以下回答来自网络:

没有问题啊，Lippman前面自己不已经给出这个问题的答案了吗？

Key Concept: Algorithms Never Execute Container Operations
The generic algorithms do not themselves execute container operations. They operate solely in terms of iterators and iterator operations. The fact that the algorithms operate in terms of iterators and not container operations has a perhaps surprising but essential implication: When used on “ordinary” iterators, algorithms never change the size of the underlying container. As we’ll see, algorithms may change the values of the elements stored in the container, and they may move elements around within the container. They do not, however, ever add or remove elements directly.

As we’ll see in Section 11.3.1 (p. 406), there is a special class of iterator, the inserters, that do more than traverse the sequence to which they are bound. When we assign to these iterators, they execute insert operations on the underlying container. When an algorithm operates on one of these iterators, the iterator may have the effect of adding elements to the container. The algorithm itself, however, never does so.

在
fill_n(back_inserter(vec),10,0);
中，问题在于，fill_n算法从来都不会改变容器的size，改变容器size的是back_inserter，back_inserter并不是一种“算法”，它可以看成是种“迭代适配器”。
于是，上面这条语句中的fill_n是一直是在“被back_inserter修改着的”容器中插入无素，它本身从来不曾修改vec容器的大小，而且也不知道容器是否被谁改过。
换句话说，它只会低着头不断往里插，却不曾知道back_inserter一直在背地里协助它，并为之承担了“修改容器大小”的骂名，呵呵。
[原文]