string类

string类有几个查找方法：

size_type find(const string& str, size_type pos = 0) const;
size_type find(const char* s, size_type pos = 0) const;
size_type find(const char* s, size_type pos = 0, size_type n) const;
size_type find(char ch, size_type pos = 0) const;

上述几个方法基本就是从第二个参数的位置开始查找第一个参数的字符串或字符，并返回首次出现的位置，第三个方法还制定了查找字符的长度。同时如果查找失败的话，就会返回string::npos。

string还提供了类似的rfind()、find_first_of()、find_last_of()、find_first_not_of()和find_last_not_of()等方法，它们的重载特征标都与find()相同，功能可以通过函数名得知。

智能指针模板类

C++提供了几种智能指针来自动管理动态内存，C++11提供了shader_ptr和unique_ptr。它们定义了类似指针的对象，可以将new获得的地址赋给这种对象，它的析构函数可以自动使用delete释放内存。

智能指针可以这么定义：

unique_ptr<type> putr(new type);
shared_ptr<type> pstr(new type);

所有智能指针类都有一个explicit构造函数，该构造函数将指针作为参数，因此不要直接用等号来为智能指针赋值：

shared_ptr<double> pd;
double* p_reg = new double;
pd = p_reg;  // 不允许
pd = shared_ptr<double>(p_reg);  //允许
shared_ptr<double> pshared = p_reg;  //不允许
shared_ptr<double> pshared(p_reg);  //允许

unique_ptr的策略是，对于特定的对象，只能有一个智能指针可拥有它，这样只有拥有对象的智能指针的构造函数会删除该对象，然后，让赋值操作转让所有权。比如：

unique_ptr<string> p3(new string("auto"));
unique_ptr<string> p4;
p4 = p3;  //不允许

p4试图接管string对象的所有权，p3的所有权会被剥夺，不过如果后续程序试图再次使用p3的话，会因为p3不再指向任何数据而出现问题，因此编译器会禁止这种语法，避免了p3不再指向有效数据的问题，unique_ptr比较安全。

不过对于函数返回值可以这么赋值：

unique_ptr<string> demo(const char* s)
{
    unique_ptr<string> temp(new string(s));
    return temp;
}

unique_ptr<string> ps;
ps = demo("Uniquely special");  //允许

编译器允许这么做，是因为函数返回的unique_ptr是个暂时的指针，马上会销毁，ps也拥有了字符串对象的所有权。总之，如果要赋值的unique_ptr是个临时右值的话，编译器就允许直接进行赋值，如果会存在一定时间，就不允许。

但我们可以使用move()函数来打破限制，不过要对弃用指针重新赋值才能重新使用它:

unique_ptr<string> ps1, ps2;
ps1 = demo("Unique Special");
ps2 = move(ps1);
ps1 = demo(" and more");

unique_ptr还可以使用new[]和delete[]：

unique_str<double[]>pda(new double(5));

shared_ptr的策略是跟踪引用特定对象的智能指针数。赋值时，计数加1，指针过期时，计数将减一，仅当最后一个指针过期时，才调用delete。如果程序要使用多个指向同一对象的指针的话，最好使用shared_ptr，反之推荐使用unique_ptr。

标准模板库

vector模板类提供下面的一些基本方法:

• size()，返回容器中元素数目
• swap()，交换两个容器的内容
• begin()，返回一个指向容器中第一个元素的迭代器
• end()，返回一个表示超过容器尾的迭代器

所谓迭代器，将其看作为一个指针就可以。迭代器的类型为一个typedef的iterator，作用域为整个类：

vector<double>::iterator pd;

可以使用迭代器来遍历容器内容：

for(pd = scores.begin(); pd != scores.end(); pd++)
    cout << *pd << endl;

所有容器都包含上述的方法。

vector有一个自己的方法push_back()，可以将元素添加到同期末尾。erase()方法可以容器中给定区间的元素，接受两个迭代器参数，如:

scores.erase(scores.begin(), scores.begin() + 2);

区间为[)类型。

insert()方法可以插入元素，接受三个迭代器参数。第一个参数指定新元素的插入位置，第二个和第三个参数定义了被插入区间，通常时另一个容器对象的一部分，比如下面的代码将new_v中除第一个元素外的所有元素插入到old_v的第一个元素前：

vector<int> old_v;
vector<int> new_v;
...
old.v,insert(old_v.begin(), new_v.begin() + 1, new_v.end());

容器还有这么几个非成员函数:for_each()、random_shuffle()、sort()。

for_each()接受三个参数，前两个定义容器中区间的迭代器，最后一个参数是一个函数对象，可以用来代替for循环:

for_each(books.begin(), books.end(), ShowReview);

random_shuffle()接受两个指定区间的迭代器参数，并随机排列该区间的元素:

random_shuffle(books.begin(), books.end());

sort()也可以乱序排序，有两个版本：

可以重写<运算符，然后使用sort()。

还可以和for_each()类似，只不过第三个参数为自定义比较函数的指针:

bool WorseThan(const Review& r1, const Review& r2);
sort(books.begin(), books.end(), WorseThan);

基于范围的for循环：

for(auto x: books)
    do something

这个和for_each()功能一致。

泛型编程

举个例子，比如在double数组中搜索特定值的函数:

double* find_ar(double* ar, int n, const double& val)
{
    for(int i = 0; i < n; i++)
        if(ar[i] == val)
            return &ar[i];
    return nullptr;
}

对于该函数，可以使用模板来与==运算符对应，但还是只适合数组。

再举一个例子，链表:

struct Node
{
    double item;
    Node* p_next;
};

可以这么编写寻找链表某个元素的函数：

Node* find_ll(Node* head, const double& val)
{
    Node* start;
    for(start = head; start != 0; start = start->p_next)
        if(start->item == val)
            return start;
    return nullptr;
}

同样也可以使用模板，但也只限于链表这一数据结构。

不过上面两个函数有共同指出，同时将值依次与容器中的值进行比较，直到匹配未知。据此，泛型编程提出了迭代器的概念，迭代器的能力如下：

• 迭代器类似于一个指针，可以使用解除引用来访问它引用的值
• 迭代器可以赋给另一个迭代器，即p=q成立。
• 迭代器之间可以进行比较，即要定义p==q和p!=q操作。
• 迭代器要能遍历容器中的元素，即要定义++p和p++操作等。

对于find()函数，上面的原则就够了。

将find_ar()改为迭代器版本：

typedef double* iterator;
iterator find_ar(iterator begin, iterator end, const double& val)
{
    iterator ar;
    for(ar = begin; ar != end; ar++)
        if(*ar == val)
            return ar;
    return end;
}

而对于find_ll()，可以定义一个迭代器类，定义了运算符*和++:

class iterator
{
public:
    iterator()
        :pt(nullptr) {}
    iterator(Node* pn)
        :pt(pn){}
    double operator*(){return pt->item;}
    iterator& operator++()  // ++it
    {
        pt = pt->p_next;
        return *this;
    }
    iterator& operator++(int)  //it++
    {
        iterator tmp = *this;
        pt = pt->p_next;
        return tmp;
    }
    //...operator==(),operator!=()等等
private:
    Node* pt;
}

然后使用迭代器类定义find_ll()：

iterator find_ll iterator head, const double& val)
{
     iterator start;
    for(start = head; start != nullptr; ++start)
        if(*start == val)
            return start;
    return nullptr;
}

可以看到该方法和find_ar()很相似。

对于STL的容器类，我们不需要知道迭代类是如何实现的，只需要知道迭代器很好使就行了，有begin()和end()。

可以将指针用作迭代器，比如一个数组，将其作为参数传入sort()函数：

const int SIZE = 100;
double Receipts[SIZE];

sort(Receipts, Receipts + SIZE);

Receipts为数组首地址，Receipts + SIZE为数组最后一个元素后一个元素的地址。

STL提供了一些预定义迭代器。有一种算法copy()可以将数据从一个容器复制到另一个容器中，它是通过迭代器方式实现的，所以可以在容器间使用，也可以在数组间使用，因为可以将指向数组的指针用作迭代器。如：

int casts[10] = {6,7,2,9,4,11,8,7,10,5};
vector<int> dice[10];
copy(casts, casts + 10, dice.begin());

前两个迭代器表示要复制的范围，最后一个迭代器参数表示要将第一个元素复制到什么位置。前两个参数必须是输入迭代器，最后一个参数必须是输出迭代器。

假设要将信息复制到显示器上，则需要使用输出流的迭代器。STL提供了ostream_iterator模板，可以这么生成迭代器：

ostream_iterator<int, char> out_iter(cout, " ");

迭代器模板的第一个参数是被发送给输出流的数据类型，第二个模板参数是输出流使用的字符类型。而构造函数的第一个参数是要使用的输出流，第二个是发送给输出流的每个数据项显示后的分隔符。

上面的迭代器可以这么输出：

*out_iter++ = 15;  //等价于cout << 15 << " ";

然后将dice的内容复制到输出流可以这么写：

copy(dice.begin(), dice.end(), out_iter);

与ostream_iterator对应的，还有istream_iterator，不过是输入流。

除此之外，还有reverse_iterator，back_insert_iterator，front_insert_iterator和insert_iterator。

对reverse_iterator执行递增操作将导致它被递减，back_insert_iterator将元素插入到容器尾部，front_insert_iterator将元素插入到容器的前端，insert_iterator将元素插入到insert_iterator构造函数的参数指定的位置前面。

内置容器

C++提供以下的容器：deque、list、queue、priority_queue、stack、vector、map、multimap、set、multiset、forward_list、unordered_map、unordered_multimap、unordered_set和unordered_multiset。

其中deque、forward_list、list、queue、priority_queue、stack、vector都是序列容器，可以在前后端添加元素，它们的迭代器至少是正向迭代器，元素按特定顺序排列，不会在两次迭代间发生变化。

vector是数组的类表示，提供了自动内存管理功能，可以动态地改变vector对象的长度。

deque是双端队列，顾名思义，两端执行操作，和vector的区别在于在两端执行插入操作和删除操作的时间固定，与之对应的vector是线性时间复杂度。

list是双向链表，其在任意位置进行插入和删除操作的时间都是固定的。

forward_list是单链表，只需要正向迭代器，不可反转容器。

queue是一个适配器类，是个典型的队列，相对于deque，它不可以随机访问元素，也不能遍历。

priority_queue是另一个适配器类，支持操作和queue相同，区别在于其最大元素被移到队首。

stack是典型的栈接口，实现一些栈模型的操作。

array并非容器，其长度固定，不过定义了一些好用的方法，如operator[]和at()，可以把它看成一个智能的固定长度数组。它可以使用一些STL算法，如copy()和for_each()。

STL提供的4中关联容器是set、multiset、map和multimap。他们使用树结构实现，并且使用键值对存储。

set是一个最简单的关联容器，其值类型与键相同，键是唯一的，所以set中没有重复元素。

multiset类似于set，只是可能有多个值的键相同。

map中，值和键的类型不同，键是唯一的，每个键只对应一个值。

multimap和map类似，只是一个键可以与多个值相关联。

然后剩余的unordered_map、unordered_multimap、unordered_set和unordered_multiset是上面4种关联容器的无序版本，内部实现为哈希表。

函数对象

很多STL算法使用函数对象——也叫函数符，函数符可以以函数方式与()结合使用任何对象。这包括函数名、指向函数的指针和重载了()运算符的类对象，如：

class Linear
{
public:
    Linear(double sl_ = 1, double y_ = 0):slope(sl_), y0(y){}
    double operator()(double x){return y0+slope*x;}
private:
    double slope;
    double y0;
};

然后就可以用()来像函数那样使用Linear对象：

Linear f1(2.5, 10.0);
double y1 = f1(12.5);

对于for_each这个函数，它的第三个参数可以是常规函数，也可以是函数符。不过这带来一个问题，如何声明第3个参数？不能将其声明为函数指针，因为会包含类型，但容器可以包含任何类型。STL使用模板来完成声明：

template<typename InputIterator, typename Function>
Function for_each(InputIterator first, InputIterator last, Function f);

这样Function这个模板参数可以接受函数指针，也可以表示具有重载的()运算符的类类型。

其它库

C++提供三个数组模板：vector、valarray、array。其中valarray是面向数值计算的，不是STL的一部分，array是为了替代内置数组而设计的。

C++11添加了initializer_list模板，即列表初始化。所有initializer_list的所有元素类型必须相同。