C++中STL(标准模板库)的使用

周定良

/*
c++标准算法库(STL)
    用于执行基本的算法，比如：for_each(遍历容器)、random_shuffle(随机打乱容器)
    主要实验包含在<algorithm>中，少量封装在<numeric>中，它是STL的三大核心组件之一
    其他两个是container(容器  常用数据结构)和iterator (迭代器  数据结构访问适配器)
    设计思想:算法函数通过迭代器作用在容器上，最大程度的复用。比如for_each()函数
    可以通过迭代器作用在set/map/list/vector/deque等容器上
    所有的算法都会接受容器的迭代器作为参数，而不是容器本身，这样算法可以作用于全部或者部分容器中的元素，
    十分灵活。如果算法（比如std::transform）需要访问两个容器，一般传入第一个容器的第一个元素，第一个
    容器的最后一个元素和第二个容器的第一元素。不需要传入第二个容器的最后一个元素，因为可以通过第一个
    容器的两个迭代器计算出来。除非此算法允许作用在两个不一样长度的容器上，比如search函数。

    为了使容器算法函数具有更高的灵活性，一般算法函数会接受一个函数或则函数对象（类似javascript的回调
    函数），这个函数在算法执行过程中内部使用，执行特殊的业务逻辑。算法函数还有一个规律是具有两种后缀，
    后缀_if 此后缀的函数一般有一个没有后缀的版本与之对应。如find和find_if，前者接受一个值，根据该值
    寻找容器中对应的元素，后者接受一个函数或函数对象（operator()必须返回bool，标识是否匹配）。
    后缀_copy 此后缀用于将算法修改后的元素拷贝到一个新的容器中，原始容器不被修改，所以此算法需要更
    多的内存。


迭代器范围（Range）

STL的迭代器尊首一个原则：前闭后开，[first, last)。容器begin函数返回的迭代器表示容器中的第一个元素，
而end函数返回的迭代器最后一个元素后面的位置（the one after the last element），也就是说*(end)没有意义，
*(end-1)表示最后一个元素。这样有几个好处：1)统一标识容器结尾；2)计算迭代器距离时，不用额外加1。     

*/

/*
ios::sync_with_stdio(false);

这个函数是一个“是否兼容stdio”的开关，C++为了兼容C，保证程序在使用了std::printf和
std::cout的时候不发生混乱，将输出流绑到了一起。

cin，cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低，
而这段语句可以来打消iostream的输入 输出缓存，可以节省许多时间，使效率与scanf与printf相差无几，

*/

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
/*   
一、各种STL的定义和操作
vector 内部数据结构：数组
    随机访问每个元素，所需要的时间为常量
    在末尾增加或删除元素所需时间与元素数目无关，在中间或开头增加或删除元素所需时间随元素数目呈线性变化
    可动态增加或减少元素，内存管理自动完成，但程序员可以使用reserve()成员函数来管理内存
    vector的迭代器在内存重新分配时将失效（它所指向的元素在该操作的前后不再相同）
    当把超过capacity()-size()个元素
        插入vector中时，内存会重新分配，所有的迭代器都将失效；否则，指向当前元素以后的任何元素的迭代器都
        将失效。
        当删除元素时，指向被删除元素以后的任何元素的迭代器都将失效
        
deque 内部数据结构：数组
    随机访问每个元素，所需要的时间为常量。
    在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除元素所需时间随元素数目呈线性变化
        可动态增加或减少元素，内存管理自动完成，不提供用于内存管理的成员函数
    增加任何元素都将使deque的迭代器失效。在deque的中间删除元素将使迭代器失效。在deque的头或尾删除元素时，
        只有指向该元素的迭代器失效
        
list 内部数据结构：双向环状链表
    不能随机访问一个元素
    可双向遍历
    在开头、末尾和中间任何地方增加或删除元素所需时间都为常量
    可动态增加或减少元素，内存管理自动完成
    增加任何元素都不会使迭代器失效。删除元素时，除了指向当前被删除元素的迭代器外，其它迭代器都不会失效
   
slist 内部数据结构：单向链表
    不可双向遍历，只能从前到后地遍历
    其它的特性同list相似
   
stack
    适配器，它可以将任意类型的序列容器转换为一个堆栈，一般使用deque作为支持的序列容器
    元素只能先进后出（FILO）（后进先出[LIFO]）
    不能遍历整个stack
   
queue
    适配器，它可以将任意类型的序列容器转换为一个队列，一般使用deque作为支持的序列容器
    元素只能先进先出（FIFO）
    不能遍历整个queue
   
priority_queue
    适配器，它可以将任意类型的序列容器转换为一个优先级队列，一般使用vector作为底层存储方式
    只能访问第一个元素，不能遍历整个priority_queue
    第一个元素始终是优先级最高的一个元素。
   
set  5
    键和值相等
    键唯一
    元素默认按升序排列
    如果迭代器所指向的元素被删除，则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效
     
multiset 5 5
    键可以不唯一
    其它特点与set相同
     
hash_set
    与set相比较，它里面的元素不一定是经过排序的，而是按照所用的hash函数分派的，
        它能提供更快的搜索速度（当然跟hash函数有关）
    其它特点与set相同
   
hash_multiset
    键可以不唯一
    其它特点与hash_set相同
     
map
    键唯一
    元素默认按键的升序排列
    如果迭代器所指向的元素被删除，则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效
     
multimap
    键可以不唯一
    其它特点与map相同
     
hash_map
    与map相比较，它里面的元素不一定是按键值排序的，而是按照所用的hash函数分派的，它能提供更快的搜索速度
    （当然也跟hash函数有关）
    其它特点与map相同
   
hash_multimap     
    键可以不唯一
    其它特点与hash_map相同
   
   
二、容器模板的使用

    大致有下面6个步骤：

        1.添加相应的头文件(如 #include <list> )( 注意，没有 .h )

        2.添加std命名空间(用 using namespace std; )

        3.赋予模板具体的使用类型(如 typedef list<string> LISTSTR; )

        4.实例化模板(如 LISTSTR test; )

        5.实例化游标(如 LISTSTR::iterator i; )

        6.通过迭代器对象访问模板对象，例如

            // 逐个输出链表test中的元素
            for ( i =  test.begin(); i != test.end(); ++i )
                cout << *i << " ";
               


三、容器模板中的常用函数

   assign()           赋值

   empty()            容器为空则返回非0值

   erase()            删除指定位置或指定范围内的元素

   push_front()       从容器头部插入元素  

   push_back()        从容器尾部插入元素

   pop_front()        删除第一个元素

   pop_back()         删除最后一个元素

   back()              返回最后一个元素的引用

   front()              返回第一个元素的引用

   begin()             返回指向第一个元素的游标 (与迭代器配合使用)

   end()                返回指向最后一个元素的后一个位置的游标 (最后1个元素再加1) (与迭代器配合使用)   
   
*/


//map定义和初始化操作
    map<int,string>  map1;    //创建一个空map
   
   
    //常用操作方法
    map1[3] = "Saniya";        //添加一个元素
    map1.insert(map<int,string>::value_type(2,"Diyabi"));//插入元素
    map1.insert(pair<int,string>(90,"pifdisoayh"));//插入元素
    map1.insert(make_pair(1,"abcdsf"));
    string key = map1[4];        //根据key取得value，key不能修改
    cout << key << endl;
     
    map<int,string>::iterator iter_map = map1.begin();     //取得迭代器的首地址
   
    int key1 = iter_map->first;    //取得key
    string value = iter_map->second;    //取得value
    map1.erase(3);
   
    //遍历
    for(map<int,string>::iterator iter = map1.begin();iter != map1.end(); iter++)
    {
        int keyk = iter->first;
        string valuev = iter->second;
        cout << keyk << " " << valuev <<endl;
    }
    return 0;
     
    cout<<map1.size()<<endl;    //计算map中的元素个数
     
    //输出测试
    cout<<key<<'\n';
   
    cout<<map1[1]<<endl;
    cout<<map1[2]<<endl;
    cout<<map1[3]<<endl;
    cout<<map1[90]<<endl;
    cout<<endl<<endl;
    cout<<key1<<endl;
    cout<<value<<endl;
    return 0;
   
   
    vector<int> v2(4,9);
    for(int i = 0; i < v2.size(); i++)
    {
        cout << v2 << endl;
    }
    return 0;
    vector<string> v1;
    string b = "abcdefghij";
    v1.push_back(b);
    v1.push_back("ijhlgk");
    cout<<v1[0]<<endl;
    v1.pop_back();
    cout<<v1.size()<<endl;
    return 0;

}