C++笔记-算法(STL)

2017-04-21

　　算法的一些通用特征:

　　STL文档使用模板参数名称来表示参数模型的概念.比如下面的copy()原型:

1 2	template<class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, OutputIterator last, OutputIterator result);

所以标识符InputIterator和OutputIterator都是模板参数,看名字一眼就能看出来区间参数必须是输入迭代器或更高级的,而只是结果存储的迭代器必须是输出迭代器或更高级的.
　　STL的有些算法有两个版本: 就地算法(in-place algorithm)和复制算法(copying algorithm),顾名思义,sort()就是就地算法的例子:函数完成时,结果被存放在原始数据的位置上; 而copy()函数将结果发送到另一个位置,所以他是复制算法;STL对此的约定是,复制版本的名称将以_copy结尾.
　　比如replace()函数,他将所有的old_value替换为new_value,则它的复制版本为:

1
2
3

template<class InputIterator,class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first,Inputiterator last, OutputIterator result,
                            const T& old_value, const T& old_value);

对于复制算法的约定是: 返回一个迭代器,指向复制的超尾(最后一个值后面)的位置
　　另一个常见变体是: 有些函数是根据函数应用于容器元素得到的结果来执行操作的.他们通常以_if结尾,比如replace_if:

template < class ForwardIterator, class UnaryPredicate, class T >
  void replace_if (ForwardIterator first, ForwardIterator last,
                   UnaryPredicate pred, const T& new_value)
{
  while (first!=last) { 
    if (pred(*first)) *first=new_value; //pred()是个一元谓词,根据其真假来决定是否将new_value赋给first
    ++first;
  }
}

一个使用STL的例子:

假设编写一个程序,让用户输入单次,希望最后得到一个按照输入顺序排列的单次列表,一个按照字母排序的列表(忽略大小写),并记录每个单次被输入的次数(不考虑标点,数字,符号):
输入和保存我们可以用vector<>:

vector<string> word;
string input;
while(cin >> input && input != "quit")
    word.push_back(input);

然后我们可以创建一个set对象,然后将vector中的单词复制(使用插入迭代器)到集合中.集合自动对其排序,无需使用sort(); 且集合只允许一个键出现一次因此也无需调用unique().至于忽略大小写…可以使用transfor,将vector中的数据复制到集合中.使用一个转换函数将函数转成小写;

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <algorithm>
#include <cctype>
using namespace std;
void display(const string & a)
{
    cout << a << " ";
}
char toLower(char ch){ return tolower(ch);}
string & ToLower(string & st)
{
    transform(st.begin(),st.end(),st.begin(),toLower);
    return st;
}
int main()
{
    vector<string> words;
    cout << "输入单词(quit退出): " << endl;
    string input;
    while (cin >> input && input != "quit")
        words.push_back(input);
    cout << "原始数据: " << endl;
    for_each(words.begin(),words.end(),display);
    cout << endl;
    set<string> word_s;
    transform(words.begin(),words.end(),
              insert_iterator<set<string>>(word_s,word_s.begin()),ToLower);
    cout << "list: " << endl;
    for_each(word_s.begin(),word_s.end(),display);
    cout << endl;
    map<string,int> wordmap;
    set<string>::iterator si;
    for(si = word_s.begin();si != word_s.end(); si++)
        wordmap[*si] = count(words.begin(),words.end(),*si);
    cout << "新数据: " << endl;
    for_each(word_s.begin(),word_s.end(),display);
    return 0;
}

其他库

　　slice类对象可用作数组索引,他们表示的是不是一个值而是一组值.slice对象被初始化为三个整数值: 起始索引,索引数,跨距.起始索引是第一个被选中的元素的索引,索引数指出要选择多少个元素,跨距表示元素之间的距离.例: slice(1,4,3)创建的对象表示选择四个元素,他们的索引分别是1,4,7,10;从索引开始加上跨距得到下一个元素的索引.
　　把第1,4,7,10元素设为10:

1	varint[slice(1,4,3)] = 10;

一个valarrat和slice混用的例子:

#include <iostream>
#include <valarray>
#include <cstdlib>
using namespace std;
const int SIZE = 12;
void show(const valarray<int>& v, int cols)
{
    int lim = v.size();
    for(int i = 0; i < lim; ++i)
    {
        cout.width(3);
        cout << v[i];
        if(i % cols == cols -1)
            cout<< endl;
        else
            cout << ' ';
    }
    if(lim % cols != 0)
        cout << endl;
}
int main()
{
    valarray<int> vint(SIZE);
    int i = 0;
    for(; i < SIZE; ++i)
        vint[i] = rand() % 10;
    cout << "原始数据: " << endl;
    show(vint,3);
    valarray<int> vcol(vint[slice(1,4,3)]);
    cout << "第二列: " << endl;
    show(vcol,1);
    valarray<int> vrow(vint[slice(3,3,1)]);
    cout << "第二行: " << endl;
    show(vrow,3);
    cout << "将最后一列设为10:" <<endl;
    show(vint,3);
    cout << "将第一列设置为下两个的总和:" << endl;
    vint[slice(0,4,3)] = valarray<int>(vint[slice(1,4,3)])
            + valarray<int>(vint[slice(2,4,3)]);
    show(vint,3);
    return 0;
}

模板initializer_list(C++11)

　　模板initializerlist(在头文件initializer中)是C++11新增的,可以使用初始化列表语法将STL容器初始化为一系列值:

1 2	vector<double> payments(45.99,39.23,19.95,89.01); //创建一个包含四个元素的容器,并用列表中的四个值来初始化这些元素;

这么做可行是因为容器包含了将initializer_list作为参数的构造函数.比如vector就包含了一个将initializer_list作为参数的构造函数,因此上述声明和下面的等同;

1	vector<double> payments( {45.99,39.23,19.95,89.01} );

　　这是C++11新增的通用初始化语法,可以使用{}而不是()来调用构造函数,并且在类有接受initializer_list作为参数的构造函数则将优先使用:

1	shared_ptr<double> pd{new double};

　　所有initializer_list元素的类型都必须相同,但编译器有的时候将尽心必要转换:

1 2	vector<double> payments {45.99, 39.23, 19, 89.0}; //19会转为19.0,但不能进行窄化转换,也就是不能隐式的把上面的double转为int;

　　initializer_list使用例子,另外他还包含成员函数begin() end() size():

#include <iostream>
#include <initializer_list>
using namespace std;
double sum(initializer_list<double> il)
{
    double s = 0;
    for(auto p = il.begin(); p != il.end(); p++)
        s += *p;
    return s;
}
double average(const initializer_list<double> & av)
{
    double s = 0;
    double n = av.size();
    if(n > 0){
    for(auto p = av.begin(); p != av.end(); p++)
        s += *p;
    s = s/n;
    }
    return s;
}
int main()
{
    cout << "List 1: sum = " << sum({2,3,4});
    cout << "ave = " << average({2,3,4}) << endl;
    initializer_list<double> dl = {1.1, 2.2, 3.3, 4.4, 5.5};
    cout << "List 2: sum = " << sum(dl);
    cout << "ave = " << average(dl) << endl;
    dl = {16.0, 25.0, 36.0, 40.0, 64.0};
    cout << "List 3: sum = " << sum(dl);
    cout << "ave = " << average(dl) << endl;
    return 0;
}

　　可以按值传递initializer_list对象,也可以按引用传递;STL是按值传递;