第10章泛型算法（Generic Algorithms）

时间：2019-11-25 17:00:02 阅读：95 评论：0 收藏：0 [点我收藏+]

10.1 Overview

1、defined in the #include <algorithm>

2、Operated by travesing a range of elements bounded by two iterators

Exercise Section 10.1

10.1\10.2

//p10_1.cpp 
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <string>

using namespace std;

int main()
{
    vector<int> ivec{1, 2, 3, 4, 5, 1, 2, 1, 1, 3, 2, 2, 1, 1};
    list<string> str_list{"good","bad", "hello", "good", "nice", "fine", "just", "good"};
    cout << "count 1: " <<count(ivec.begin(), ivec.end(), 1)<< endl;
    cout << "count good: " << count(str_list.begin(), str_list.end(), "good")<< endl;


    return 0;
}

10.2 A First Look at the Algorithms

The most basic way to understand the algorithms is to know wheather they read elements, write elements, or rearrange the order of the elements.

accumulate in #include <numeric>

Exercises Section 10.2.1

10.3、

//p10_3.cpp
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main()
{
    vector<int> ivec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    int sum = accumulate(ivec.begin(), ivec.end(), 0);

    cout << "sum of ivec = " << sum << endl;
    
}

10.4、

会损失精度？

10.5、

比较的是指针

使用泛型算法一定要保证不会超范围的解引用

Exercises Section 10.2.2

10.6、

//p10_6.cpp 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> ivec(10, 1);
    for(auto ix : ivec)
        cout << ix << ‘ ‘ ;
    cout << endl;

    fill_n(ivec.begin(), ivec.size(), 0);
    for(auto ix : ivec)
        cout << ix << ‘ ‘ ;
    cout << endl;

    return 0;
}

10.7、

(a)

(a)
vector<int> vec; list<int> lst; int i;
while(cin >> i)
    lst.push_back(i);
copy(lst.cbegin(), lst.cend(); vec.begin());//错误
//correct:
copy(lst.cbegin(), lst.cend(); back_insert(vec));
(b)
vector<Int> vec;
vec.reserve(10);//不改变容器大小，容器仍为空
fill_n(vec.begin(), 10, 0);////correct:
fill_n(back_insert(vec), 10, 0);

10.8、

？？我理解为这并不是算法本身改变了容器大小，而是插入迭代器改变了容器大小

Exercises Section 10.2.3

10.9、

调用unique以后，后面的重复的单词不打印出来，后来查看了容器的size发现使用unique后的size不变。

//p10_9.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    vector<string> str_vec;
    string str_temp;
    while(cin >> str_temp)
        str_vec.push_back(str_temp);
    for(auto ix : str_vec)
        cout << ix << ‘ ‘ ;
    cout << endl;
    sort(str_vec.begin(), str_vec.end());
    for(auto ix : str_vec)
        cout << ix << ‘ ‘ ;
    cout << endl;
    auto end_unique = unique(str_vec.begin(), str_vec.end());
    for(auto ix : str_vec)
        cout << ix << ‘ ‘ ;
    cout << endl;
    cout << str_vec.size() << endl;
    
    str_vec.erase(end_unique,str_vec.end());
    for(auto ix : str_vec)
        cout << ix << ‘ ‘ ;
    cout << endl;
    cout << str_vec.size();


    return 0;   
}

10.10、

算法不直接作用于容器，只是通过迭代器方位容器中的元素。

10.3 Customizing Operations

10.3.1 Passing a Function to an Algorithm

Exercises Section 10.3.1

10.11、

//p10_11.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void elimDumps(vector<string> &words);
bool isShorter(const string &s1, const string &s2);

int main()
{
    vector<string> str_vec;
    string str_temp;
    while(cin>>str_temp)
        str_vec.push_back(str_temp);
    elimDumps(str_vec);
    for(auto &ix : str_vec)
    {
         cout << ix << ‘ ‘ ;
    }   
    cout << endl;
    stable_sort(str_vec.begin(), str_vec.end(), isShorter);


    for(auto &ix : str_vec)
    {
         cout << ix << ‘ ‘ ;
    }   
    cout << endl;

    return 0;
}


void elimDumps(vector<string> &words)
{
    sort(words.begin(), words.end());
    auto end_unique = unique(words.begin(), words.end());
    words.erase(end_unique, words.end());
}

bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}

10.13、

//p10_13.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

inline bool more_than_five(string &str)
{
    return str.size() >= 5;
}

int main()
{
    vector<string> str_vec;
    string str_temp;
    while(cin >> str_temp)
        str_vec.push_back(str_temp);
    vector<string> str_partion(str_vec.size());
    auto end_more_than_five = partition(str_vec.begin(),str_vec.end(), more_than_five);
    str_vec.erase(end_more_than_five, str_vec.end());

    for(auto &ix : str_vec)
        cout << ix << ‘ ‘ ;
    cout << endl;

    return 0;
}

10.3.2 Lambda Expressions

[capture list] (parameter list) -> return type{function body}

capture list （捕获列表）只能用于局部非静态变量，lambdas可以直接使用局部静态变量和定义在函数外部的变量

Exercises Section 10.3.2

10.14、

#include <iostream>

using namespace std;

auto f = [](int x, int y) {return x+y;};

int main()
{
    cout << f(1,2) << endl;
}

10.15、

//p10_15.cpp
#include <iostream>
using namespace std;

int func(int x,int y)
{   
    return [x](int z){return x + z;}(y);
}

int main()
{
    cout << func(2,3);

    return 0;
}

10.16、

书上的：

void biggies(vector<string> &words, vector<string>::size_type sz)
{
    elimDups(words);
    satble_sort(words.begin(), words.end(), [](const string &a, const string &b)
                                            {return a.size(), >= b.size();}
    );
    auto wc = find_if(words.begin(), words.end(), [sz](const string &a)
                                                    {return a.size() >= sz;}
    );
    auto count = words.end() - wc;

    cout << cout <<" " << make_plural(count, "word", "s") 
         << " of length " << sz << " or longer" << endl;

    for_each(wc, words.end(), [](const string &s)
                                {cout << s << " ";}
    );
    cout << endl;
}

10.17、

//p10_17.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

class Sales_data{
    public:
        Sales_data(){}
        Sales_data(string s):_Isbn(s){}
        string Isbn(){return _Isbn;}
    private:
        string _Isbn;
};

int main()
{
    Sales_data a("978-7-121-15535-2"); //初始化对象
    Sales_data b("978-7-121-20038-0");
    Sales_data c("978-7-121-20934-5");
    Sales_data d("978-7-115-47258-8");
    Sales_data e("978-7-121-34180-9");
    Sales_data f("978-7-121-32905-0");

    vector<Sales_data> vec1{a,b,c,d,e,f};

    stable_sort(vec1.begin(), vec1.end(),[](Sales_data s1, Sales_data s2){return s1.Isbn() < s2.Isbn();});
    for(auto ix : vec1)
    {
        cout << ix.Isbn() << endl;
    }

    return 0;

}

10.18、

//p10_18.cpp

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

void elimDups(vector<string> &words)

{

sort(words.begin(), words.end());

auto end_unique = unique(words.begin(), words.end());

words.erase(end_unique, words.end());

}

void biggies(vector<string> &words, vector<string>::size_type sz)

{

elimDups(words);

auto wc = partition(words.begin(), words.end(), [sz](const string &a)

{return a.size() >= sz;}

);

words.erase(wc,words.end());

for_each(words.begin(), words.end(), [](const string &s)

{cout << s << " ";}

);

cout << endl;

}

int main()

{

string temp;

vector<string> words;

while(cin >> temp)

words.push_back(temp);

biggies(words, 5);

return 0;

}

10.19、

把18题的partition 换成stable_partition

10.3.3 Lambda capture and return

函数返回的lambda 不能捕捉引用，必须保证lambda在执行的时候捕获的引用依然存在

尽量不要使用捕捉引用或指针

Exercises Section 10.3.3

10.20、

//p10_20.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string str_temp;
    vector<string> str_vec;
    while(cin >> str_temp)
        str_vec.push_back(str_temp);
    cout << "There are " << count_if(str_vec.begin(), str_vec.end(),[](string &s){return s.size() >= 6;})
         << " words have more than 6 characters" << endl;

    return 0;
}

10.21、

//p10_21.cpp
#include <iostream>

using namespace std;

int main()
{
    bool not_zero = false;
    for(int i = 7; !not_zero; --i)
    {
        auto f = [i]()->bool {if(i == 0)
            return  true;
            else 
            return false;};
        not_zero = f();
        
    }

    return 0;
    
}

10.3.4 Binding Arguments

参数绑定：用于泛型算法需要的谓词的参数个数和所需的调用的函数参数不一致的情况

bind: #include <functional>　　用法： auto newCallable = bind(callable, arg_list);

_n：palceholder　　　　using namespace std::placeholders

eg:

auto g = bind(f, a, b, _2, c, _1);

g(_1, _2) ;

f(a, b, _2, c, _1)

bind可用于改变参数的顺序

默认参数绑定的非占位参数是同过拷贝绑定到可调用对象的，对于需要通过引用的参数或者不可拷贝的参数要使用ref

ref cref

Exercises Section 10.3.4

10.22、

//p10_22.cpp
#include <iostream>
#include <functional>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
using namespace std::placeholders;



bool func(const string &s, string::size_type sz)
{
    return s.size() <= sz;
}

int main()
{
    vector<string> str_vec;
    string str_temp;
    while(cin >> str_temp)
        str_vec.push_back(str_temp);
    auto number = count_if(str_vec.cbegin(), str_vec.cend(), bind(func,_1, 6));
    cout << "there are " << number << " words" << endl;

    return 0 ;
}

10.23、

如果进行绑定的函数有n个参数，那么bind 获取n+1 个参数，额外的第一个参数是绑定的函数本身

10.24、

这里有C++ Primer 5的所有代码和答案：https://github.com/Mooophy/Cpp-Primer

后面就不贴代码了

10.4. Revisiting Iterators

Insert iterators　　stream iterator 　　reverse iterators　　move iterators

10.26、

front_inserter: 从最前面插入元素使用push_front

back_inserter:从最后面插入元素使用push_back

inserter : 从指定位置插入　　使用insert

10.27、

//p10_27.cpp
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
//#include <functional>


using std::string;
using std::vector;
using std::cout;
using std::cin;
using std::endl;
//using std::unique_copy;

int main()
{
    vector<string> str_vec{"good", "good", "study", "day", "day", "up","and", "sport", "healther"};
    vector<string> str_vec_targ;
    unique_copy(str_vec.begin(),str_vec.end(), back_inserter(str_vec_targ));

    cout << "str_vec: " << endl;
    for_each(str_vec.cbegin(), str_vec.cend(), [](const string &s){cout << s << " ";});
    cout << "str_vec_targ: " << endl;
    for_each(str_vec_targ.cbegin(), str_vec_targ.cend(), [](const string &s){cout << s << " ";});

    return 0;
}

10.28、

//p10.28.cpp
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>

using std::vector;
using std::list;
using std::cout;
using std::endl;


int main()
{
    vector<int> ivec {1, 2, 3, 4, 5, 6, 7, 8, 9};
    list<int> lis1, lis2, lis3;
    //vector没有push_front
    //vector<int> lis1, lis2, lis3;
    //copy(ivec.cbegin(), ivec.cend(), inserter(lis1,lis1.begin()));
    //copy(ivec.cbegin(), ivec.cend(), front_inserter(lis2));//这一句会报错
    //copy(ivec.cbegin(), ivec.cend(), back_inserter(lis3));
    copy(ivec.cbegin(), ivec.cend(),inserter(lis1,lis1.begin()));
    copy(ivec.cbegin(), ivec.cend(),front_inserter(lis2));
    copy(ivec.cbegin(), ivec.cend(),back_inserter(lis3));
    cout << "inserter : " << endl;
    for_each(lis1.cbegin(), lis1.cend(), [](const int &i){cout << i << " " ;});
    cout <<‘\n‘;
    cout << "front_inserter : " << endl;
    for_each(lis2.cbegin(), lis2.cend(), [](const int &i){cout << i << " " ;});
    cout <<‘\n‘;
    cout << "inserter : " << endl;
    for_each(lis3.cbegin(), lis3.cend(), [](const int &i){cout << i << " " ;});

}

10.29、

//p10_29.cpp 
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iterator>

using std::vector;
using std::string;
using std::ifstream;
using std::cout;
using std::endl;
using std::istream_iterator;
using std::ostream_iterator;

int main(int argc , char * argv[])
{
    if(argc != 2)
    {
        cout << "erro: Usage : " << argv[0] << " filename" <<endl;
        exit(EXIT_FAILURE);
    }
    //vector<string> str_vec;
    ifstream in(argv[1]);
    istream_iterator<string> istr_iter(in), eof;
    vector<string> str_vec(istr_iter,eof);
    //copy(istr_iter, eof,back_inserter(str_vec));
    ostream_iterator<string> ostr_iter(cout, " ");
    copy(str_vec.cbegin(),str_vec.cend(), ostr_iter);

    return 0;
}

10.30、10.31

//p10_30.cpp
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::istream_iterator;
using std::ostream_iterator;
//using std::unique_copy;

int main()
{
    istream_iterator<int> i_iter(cin), eof;
    ostream_iterator<int> o_iter(cout, " ");
    vector<int> vec(i_iter, eof);
    //sort(i_iter,eof);不能对输入直接使用sort
    sort(vec.begin(), vec.end());
    copy(vec.begin(), vec.end(), o_iter);
    //10.31
    cout << endl;
    unique_copy(vec.begin(), vec.end(), o_iter);//英文第五版书中unqiue_copy有误

    
    return 0;
}

10.33、

//p10_33.cpp
#include <iostream>
#include <fstream>
#include <iterator>
#include <string>

using std::ifstream;
using std::ofstream;
using std::istream_iterator;
using std::ostream_iterator;
using std::cin;
using std::cout;
using std::endl;
using std::string;

int main()
{
    cout << "Enter an file name: " ;
    string filename;
    cin >> filename;
    ifstream ifn(filename);
    ofstream oofn(filename+"_odd"),eofn(filename+"_even");
    istream_iterator<int> integer_input(ifn), input_eof;
    ostream_iterator<int> odd_output(oofn," ");
    ostream_iterator<int> even_output(eofn, "\n");
    while(integer_input != input_eof)
    {
        if((*integer_input)%2)
            *odd_output++ = *integer_input++;
        else
        {
            *even_output++ = *integer_input++;
        } 
    }
    
    return 0;
}

10.4.3 Reverse Iterators

forward_list 和 stream iterators 没有reverse iterator

Exercises Section 10.4.3

10.34\35\36\37

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

using std::vector;
using std::list;
using std::cout;
using std::endl;

int main()
{
    vector<int> ivec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};//10.34 10.35
    list<int> lis{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5};//10.36
    list<int> lis1;         //10.37

    for_each(ivec.cbegin(), ivec.cend(), [](const int &i){cout << i << " ";});
    cout << ‘\n‘;

    //10.34:
    for_each(ivec.crbegin(), ivec.crend(), [](const int &i){cout << i << " ";});
    cout << ‘\n‘;

    //10.35:
    for(auto iter = --ivec.cend(); iter != --ivec.cbegin(); --iter)
        cout << *iter << " ";
    cout << ‘\n‘;
    
    //10.36:
    auto last_zero = find(lis.crbegin(), lis.crend(), 0);
    for_each(last_zero.base(),lis.cend(), [](const int &i){cout << i << " ";});
    cout <<‘\n‘;

    //10.37:
    copy(ivec.cbegin()+3, ivec.cbegin()+7,front_inserter(lis1));
    for_each(lis1.cbegin(), lis1.cend(), [](const int &i){cout << i <<" ";});
    cout << endl;

    return 0;
}

Exercises Section 10.5.1

10.38、

Input Iterator : ==　　!=　　++ 　　‘=‘右侧的 * 　　->　　(*it).member

Output Iterator: ++ 　　*只出现在左侧

Forward Iterator：read,write,支持多次访问不支持--

Bidirectional Iterator: 支持--

Random-access Iterators：relational operators(<，<=, >, and >=)

10.39、

list: bidirectional iterator

vector: random-access iterator

10.40、

first two :input　　dest:output

reverse: bidirectional iterator

unique: forward iterator

10.41、

10.42、

//p10_42.cpp
//
//Exercise 10.42
//Reimplement the program that eliminated duplicate words that we wrote in 
//10.2.3(p.383) to  use a list instead of a vector.
//

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

using std::string; 
using std::list;

void elimDups(list<string> &words)
{
    words.sort();
    words.unique();
}

int main()
{
    list<string> lis{"aa", "aa", "aa", "aa", "aasss", "aa"};
    elimDups(lis);
    for_each(lis.cbegin(), lis.cend(), [](const string &s){std::cout << s << " ";});
    std::cout << std::endl;
}

第10章泛型算法（Generic Algorithms）

原文：https://www.cnblogs.com/xiaogaogao/p/11904440.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

第10章 泛型算法（Generic Algorithms）

10.1 Overview

10.2 A First Look at the Algorithms

10.3 Customizing Operations

10.3.1 Passing a Function to an Algorithm

10.3.2 Lambda Expressions

10.3.3 Lambda capture and return

10.3.4 Binding Arguments

10.4. Revisiting Iterators

10.4.3 Reverse Iterators

第10章泛型算法（Generic Algorithms）