C++ STL 容器使用

 

1：关联容器和顺序容器

c++中有两种类型的容器：顺序容器和关联容器

顺序容器主要有：vector、list、deque等。

vector表示一段连续的内存地址，基于数组的实现

list表示非连续的内存，基于链表实现

deque与vector类似，但是对于首元素提供删除和插入的双向支持

关联容器主要有：map和set。

map是key-value形式的，set是单值。map和set只能存放唯一的key值

multimap和multiset可以存放多个相同的key值。

容器类自动申请和释放内存，我们无需new和delete操作。

2：顺序容器的介绍

vector

需要包含头文件#include<vector>

主要的操作有

     vector<int> vec1;    //默认初始化，vec1为空
     vector<int> vec2(vec1);  //使用vec1初始化vec2
	 vec1.push_back(100);            //尾部添加元素
     int size = vec1.size();         //元素个数
     bool isEmpty = vec1.empty();    //判断是否为空
    int out = vec1.front();       //取不删除
     vec1.pop_back();              //删除末尾元素
     vector<int>::iterator iter = vec1.begin();
     for(;iter != vec1.end();iter++)
     {
        cout<<*iter;
     }

List

需要添加头文件#include<list>

list是stl实现的双向链表，与向量vector想比，它允许快速的插入和删除，但是随机访问却是比较慢，主要的操作

    list<int> lst1;          //创建空list
    list<int> lst2(3);       //创建含有三个元素的list
    list<int> lst3(3,2); //创建含有三个元素为2的list
    lst1.push_back(10);                    //末尾添加值
    lst1.pop_back();                   //删除末尾值
    lst1.clear();                      //清空值
    bool isEmpty1 = lst1.empty();          //判断为空
    lst1.erase(lst1.begin(),lst1.end());                        //删除元素
    lst1.front();                      //返回第一个元素的引用
    lst1.back();                       //返回最后一个元素的引用
    lst1.reverse();                        //反转
    lst1.size();                       //含有元素个数
    lst1.sort();                       //排序
    lst1.unique();                         //删除相邻重复元素
    for(list<int>::const_iterator iter = lst1.begin();iter != lst1.end();iter++)
    {
       cout<<*iter;
    }

Stack

使用该容器时需要包含#include<stack>头文件；

1.入栈：如s.push(x);

2.出栈:如 s.pop().注意：出栈操作只是删除栈顶的元素，并不返回该元素。

3.访问栈顶：如s.top();

4.判断栈空：如s.empty().当栈空时返回true。

5.访问栈中的元素个数，如s.size（）;

 

 

Deque

    需要包括头文件<deque>;

    定义：

         deque<数据类型> 变量名;

    Eg:

        deque<int> que;//定义了一个整型的双端队列;

   基本操作（红色标识为常用操作）：

     　　que.assign(beg,end) 将[beg; end)区间中的数据赋值给que。

     　　que.assign(n,elem) 将n个elem的拷贝赋值给que。

     　　que. at(idx) 传回索引idx所指的数据，如果idx越界，抛出out_of_range。

     　　que.back() 返回容器que的最后一个元素的引用。如果que为空，则该操作未定义。

     　　que.begin() 传回迭代器中的第一个数据地址。

     　　que.clear() 移除容器中所有数据。

　　     que.empty() 判断容器是否为空。

　　     que.end() 返回一个迭代器，它指向容器que的最后一个元素的下一位置。

              que.front() 返回容器que的第一个元素的引用。如果que为空，则该操作为空。

            que.pop_back() 删除最后一个数据。

　　     que.pop_front() 删除头部数据。

     　　que.push_back(elem) 在尾部加入一个数据。

     　　que.push_front(elem) 在头部插入一个数据。

 

3:关联容器的介绍

map

//1.定义和初始化

    map<int,string> map1;                  //空map

    //2.常用操作方法

//1.定义和初始化
    map<int,string> map1;                  //空map
    //2.常用操作方法
    map1[3] = "Saniya";                    //添加元素
    map1.insert(map<int,string>::value_type(2,"Diyabi"));//插入元素
    //map1.insert(pair<int,string>(1,"Siqinsini"));
    map1.insert(make_pair<int,string>(4,"V5"));
    string str = map1[3];                  //根据key取得value，key不能修改
    map<int,string>::iterator iter_map = map1.begin();//取得迭代器首地址
    int key = iter_map->first;             //取得key
    string value = iter_map->second;       //取得value
    map1.erase(iter_map);                  //删除迭代器数据
    map1.erase(3);                         //根据key删除value
    map1.size();                       //元素个数
    map1.empty();                       //判断空
    map1.clear();                      //清空所有元素
    //3.遍历
    for(map<int,string>::iterator iter = map1.begin();iter!=map1.end();iter++)
    {
       int keyk = iter->first;
       string valuev = iter->second;
}

 

 

set集合

set的含义是集合，它是一个有序的容器，里面的元素都是排序好的支持插入、删除、查找等操作，就像一个集合一样，所有的操作都是严格在logn时间内完成，效率非常高。

set和multiset的区别是：

set插入的元素不能相同，但是multiset可以相同，set默认是自动排序的，使用方法类似list。

4：几种容器的比较

1)vector

内部数据结构：数组。

在末尾增加或者删除元素所需时间与元素数目无关，在中间或者开头增加或者删除元素所需时间是随元素数目呈线性变化。

2):deque

内部数据结构是：数组

随机访问每个元素，所需要的时间为常量。在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除所需时间随元素数目呈线性变化。

3)list

内部数据结构：双向环状链表

不能随机访问一个元素，可双向遍历，在开头，末尾和中间的任何地方增加或者删除元素所需时间都是常量。

4)set

键和值相等。

键唯一

元素默认按升序排列、

5)map

键唯一，

元素默认按键的升序排列