List容器

双向链表#include < list >

• 在任何位置插入和删除都是常数时间
• 不支持根据下标随机存取元素
• 具有所有顺序容器都有的成员函数

List容器还支持的8个成员函数：

1. Push_front() :在链表最前面插入
2. Pop_front():删除链表最前面的元素
3. Sort()：排序（list不支持STL算法sort,因为不支持随机访问迭代器）
4. Remove()：删除和指定值相等的所有元素
5. Unique()：删除所有和前一个元素相同的元素
6. Merge()：合并两个链表，并清空被合并的链表
7. Reverse()：颠倒链表，逆序
8. Splice()：在指定位置前面插入另一链表中的一个或多个元素，并在另一链表中删除被插入的元素

List容器的sort函数

• List容器的迭代器不支持完全随机访问,不能用标准库中的sort函数对它进行排序,List自己的sort成员函数:

List classname
Classname.sort(compare); //compare函数可以自己定义
Classname.sort(); //无参数版本，按照 0)
    {
        typename list::const_iterator it;
        //" typename "是一个C++程序设计语言中的关键字。 当用于泛型编程时是另一术语" class "的同义词。
        //这个关键字用于指出模板声明（或定义）中的非独立名称（dependent names）是类型名，而非变量名。
        for( it = lst.begin(); it != lst.end(); it++)
        {

• 可变长的动态数组
• 必须包含头文件 #include < vector >
• 所有STL算法 都能对vector操作

支持随机访问迭代器

* 根据下标随机访问某个元素时间为常数
* 在尾部添加速度很快
* 在中间插入慢

vector的成员函数

• 构造函数初始化

• 其他常用函数

#include 
#include 
#include 
using namespace std;

int main()
{
    int a[5] = {1, 2, 3, 4, 5};
    vector v(5);//每个初始化为0

iterator与const_iterator及const iterator区别

1. iterator,const_iterator作用：遍历容器内的元素，并访问这些元素的值。iterator可以改元素值,但const_iterator不可改。跟C的指针有点像
   (容器均可以++iter,而vector还可以iter-n, iter+n,n为一整型,iter1-iter2:结果是difference_type类型，表两元素的距离.)
2. const_iterator 对象可以用于const vector 或非 const vector,它自身的值可以改(可以指向其他元素),但不能改写其指向的元素值.
3. const iterator与const_iterator是不一样的：声明一个 const iterator时，必须初始化它。一旦被初始化后，就不能改变它的值,它一旦被初始化后,只能用它来
   改它指的元素,不能使它指向其他元素。(因此const iterator几乎没什么用途)

• STL算法就是一个个函数模板, 大多数在 中定义
• 算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个
  局部区间进行操作，因此需要两个参数，一个是起始元素的迭代器，

一个是终止元素的后面一个元素的迭代器。比如，排序和查找

• 有的算法返回一个迭代器。比如 find() 算法，在容器中查找一个元
  素，并返回一个指向该元素的迭代器
• 算法可以处理容器，也可以处理普通数组

vector的迭代器是随机迭代器，遍历 vector 可以有以下几种做法(deque亦然)：

vector v(100);
int i;
for(i = 0;i < v.size() ; i ++)

标准模板库STL 概述

简单地说就是使用模板的程序设计法。

将一些常用的数据结构（比如链表，数组，二叉树和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。

容器概述

可以用于存放各种类型的数据（基本类型的变量，
对象等）的数据结构，都是类模版,分为三种：

1. 顺序容器
   vector, deque,list
2. 关联容器
   set, multiset, map, multimap
3. 容器适配器
   stack, queue, priority_queue

对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载 == 和 < 运算符。

顺序容器简介

容器并非排序的，元素的插入位置同元素的值无关。

• vector 头文件 < vector >

  • 动态数组。
  • 元素在内存连续存放。
  • 随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间）。

• deque 头文件 < deque >

  • 双向队列。
  • 元素在内存连续存放。
  • 随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间）。

• list 头文件 < list >

  • 双向链表。
  • 元素在内存不连续存放。
  • 在任何位置增删元素都能在常数时间完成。不支持随机存取。

关联容器简介

• 元素是排序的
• 插入任何元素，都按相应的排序规则来确定其位置
• 在查找时具有非常好的性能
• 通常以平衡二叉树方式实现，插入和检索的时间都是 O(log(N))

• set/multiset 头文件 < set >

  • set 即集合。set中不允许相同元素，multiset中允许存在相同的元素。

• map/multimap 头文件 < map >

  • map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名
    为first,另一个名为second, map根据first值对元素进行从小到大排序，并可快速地根据first来检索元素。map同multimap的不同在于是否允许相同first值的元素

• stack :头文件 < stack >

  • 栈。是项的有限序列，并满足序列中被
    删除、检索和修改的项只能是最近插入

序列的项（栈顶的项）。后进先出。

• queue 头文件 < queue >

  • 队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。

• priority_queue 头文件 < queue >

  • 优先级队列。最高优先级元素总是第一个出列

顺序容器和关联容器中都有的成员函数

• begin 返回指向容器中第一个元素的迭代器
• end 返回指向容器中最后一个元素后面的位置的迭代器
• rbegin 返回指向容器中最后一个元素的迭代器
• rend 返回指向容器中第一个元素前面的位置的迭代器
• erase 从容器中删除一个或几个元素
• clear 从容器中删除所有元素

顺序容器的常用成员函数

• front :返回容器中第一个元素的引用
• back : 返回容器中最后一个元素的引用
• push_back : 在容器末尾增加新元素
• pop_back : 删除容器末尾的元素
• erase :删除迭代器指向的元素(可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器

迭代器

• 用于指向顺序容器和关联容器中的元素
• 迭代器用法和指针类似
• 有const 和非 const两种
• 通过迭代器可以读取它指向的元素
• 通过非const迭代器还能修改其指向的元素
  定义一个容器类的迭代器的方法可以是：

容器类名::iterator 变量名;

或：

容器类名::const_iterator 变量名;

访问一个迭代器指向的元素：

*迭代器变量名

• vector 和deque提供的是RandomAccessIterator，
• list提供的是BidirectionalIterator，
• set和map提供的 iterators是 ForwardIterator

迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素。
如果迭代器到达了容器中的最后一个元素的后面，此时再使用
它，就会出错，类似于使用NULL或未初始化的指针一样。

双向迭代器

若p和p1都是双向迭代器，则可对p、p1可进行以下操作：

• ++p, p++ 使p指向容器中下一个元素
• –p, p– 使p指向容器中上一个元素
• *p 取p指向的元素
• p = p1 赋值
• p == p1 , p!= p1 判断是否相等、不等

随机访问迭代器

若p和p1都是随机访问迭代器，则可对p、p1可进行以下操作：

• 双向迭代器的所有操作
• p += i 将p向后移动i个元素
• p -= i 将p向向前移动i个元素
• p + i 值为: 指向 p 后面的第i个元素的迭代器
• p – i 值为: 指向 p 前面的第i个元素的迭代器
• p[i] 值为: p后面的第i个元素的引用
• p < p1, p p1, p>= p1

#include 
#include 
using namespace std;

int main()
{
    string s1("hello"), s2("hello"), s3("hell");
    int f1 = s1.compare(s2);
    int f2 = s1.compare(s3);
    int f3 = s3.compare(s1);
    int f4 = s1.compare(1, 2, s3, 0, 3); //s1 1-2; s3 0-3
    int f5 = s1.compare(0, s1.size(), s3); //s1 0-end

//string类
// string 类 是一个模板类, 它的定义如下:
// typedef basic_string string;
#include 
#include 
using namespace std;
int main()
{
    string s1("hello");//一个参数的构造函数
    string s2(8, '6');//两个参数的构造函数 int char？
    string month = "May";//赋值操作符初始化 
    //不提供以字符和整数为参数的构造函数
//错误的初始化方法：
/*    string error1 = 'c';
    string error2('c');
    string error3 = 1;
    string error(1);*/
    //char可以赋值给string对象 
    string s3;
    s3 = 'c';
    //构造的string太长而无法表达 ? 会抛出length_error异常

    //string 对象的长度用成员函数 length()读取；
    string s4("hhhhhh");
    cout  s5;
    //string 支持getline函数
    string s6;
    getline(cin, s6);
    //string的赋值和连接
    string s7("12345"), s8;
    s8 = s7;//用 ‘=’ 赋值
    s8.assign(s7);
    s8.assign(s7, 1, 3);//从s7中下标为1开始复制3个字符给s8