C++ STL容器

一、序列式容器

容器的通用查询方法

InputIterator find (InputIterator first, InputIterator last, const T& val);

其中,first 和 last 为输入迭代器,[first, last) 用于指定该函数的查找范围;val 为要查找的目标元素。

该函数会返回一个输入迭代器,当 find() 函数查找成功时,其指向的是在 [first, last) 区域内查找到的第一个目标元素;如果查找失败,则该迭代器的指向和 last 相同。

count(first,last,value);

其中first是容器的首迭代器,last是容器的末迭代器,value是询问的元素。函数返回和value相同的元素个数;
count可以用于关联容器的查询:

map<Key_Type, ValType> mymap;
if(map.count(value1) == 0){/*.没有元素.*/}

1. vector

特点:从尾部快速插入和删除,可直接访问任意元素。
实现:动态数组。malloc、rela
常用方法:

  1. 头文件: #include <vector>

  2. 创建和初始化

    vector<Type> arr;
    vector<Type> arr(n [, val]); //创建长度为n,[初始值为val]的数组
    vector<vector<Type>> arr(n, vector<Type>(m, val)); //n*m的二维数组,初值为val
  3. 尾部插入和删除

    arr.push_back(elem); //尾部插入
    arr.pop_back(); //尾部删除
  4. 查询

    arr[i]; //下标访问
    arr.front();    //返回头部元素
    arr.back();     //返回尾部元素
  5. 容器大小

    arr.size(); //返回元素个数
    arr.capacity(); //容器容量
  6. 任意位置插入

    arr.insert(pos, elem); //pos位置插入elem
    arr.insert(pos, n, elem); //pos位置插入n个elem
  7. 任意位置删除

    arr.erase(pos); //删除pos位置元素,返回下一个元素位置
    arr.erase(begin, end); //删除[begin, end)元素,返回下一个的位置
  8. 逆序存储

    arr.reverse(pos1, pos2); //pos1到pos2的元素逆序存储
  9. 迭代器

    arr.begin();
    arr.end();
    for(auto i = arr.begin(); i != arr.end(); i++){
       cout<<*i<<endl;
    }

2. deque (Double-Ended Queue)

特点:从前面或后面快速的插入与删除,直接访问任何元素。
实现:双端队列。中控器(map,索引数组)+缓冲区(分段数组,实际存储体),像二维数组。
常用方法:

  1. 头文件: #include <deque>

  2. 创建和初始化(同vector)

    deque<Type> deq;
  1. 头部/尾部插入和删除

    deq.push_front(elem);    //头部插入
    deq.pop_front();         //头部删除
    deq.push_back(elem);
    dqe.pop_back();
  2. 查询

    dqe[i];
    dqe.front();    //返回头部元素
    dqe.back();
  3. 任意位置插入/删除(同vector)

  4. 迭代器(同vector)

3. list

特点:从任何地方快速插入与删除
实现:双向链表
常用方法:

  1. 头文件 #include <list>

  2. 创建和初始化(同vector)

    list<Type> li;
  3. 插入和删除

    li.push_front(elem);
    li.pop_front();
    li.push_back(elem);
    li.pop_back();
  4. 查询:使用迭代器

    //遍历访问
    for(auto i = li.begin(); i != li.end(); i++){
        cout<<*i<<endl;
    }
    //搜索
    list<int>::iterator int_itor=find(li.begin(),li.end(),3);
    cout <<*int_itor << endl;
  5. 容器大小

  6. 任意位置插入(同vector)

    代码块
  7. 任意位置删除(同vector)

  8. 迭代器(同vector)

    li.begin();
    li.end();

二、关联容器

特点:都是有序的,升序排列

1. set

特点:快速查找,不允许重复值。存储的是一组无重复的元素。如果要修改某一个元素值,必须先删除原有的元素,再插入新的元素。
实现:红黑树
常用方法:

  1. 头文件 #include <set>

  2. 创建和初始化

    set<Type> myset;
    set<Type, op> myset; //op为仿函数,排序规则,默认是 升序less<T>,降序为greater<T>
    //仿函数
    struct cmp{
       bool operator()(T &a, T &b){
           return a < b;   //降序
       }
    }
  3. 插入和删除

    myset.empty();    //判断是否为空
    myset.insert(elem);    //插入elem
    myset.insert(pos, elem);    //pos位置插入elem
    myset.erase(elem);    //删除elem
    myset.erase(pos);     //删除pos位置元素
    myset.clear();    //清空集合
  4. 查询

    myset.find(elem); //返回迭代器,=myset.end()时则找不到元素
    myset.count(elem);    //返回elem元素的数目
  5. 容器大小

    myset.size();
    myset.max_size();    //可容纳最大元素数量
  6. 迭代器

    //顺序遍历
    myset.begin(); 
    myset.end();
    //逆序遍历
    myset.rbegin();
    myset.rend();

2. multiset

特点:快速查找,允许重复值
实现:红黑树
常用方法:

  1. 头文件 #include <set>

3. map

特点:单重映射,基于关键字快速查找,不允许重复值
实现:红黑树,按Key排序
常用方法:

  1. 头文件 #include <map>
  1. 创建和初始化
    map<KeyType, ValType> m;
    map<KetType, ValType, op> m; //op为排序规则,仿函数,默认是less<T>,升序
  1. 插入和删除
  • 直接插入(修改式)

    m[key] = vlaue;    //不适用于multimap
  • 用pair<>构造键值对,然后插入

    m.insert(pair<KeyType, ValType>(key, value));
  • 使用make_pair()函数构建键值对,然后插入

    m.insert(make_pair(key, value));
  • 使用value_type标志

    m.insert(map<KeyType, ValType>::value_type(key, value));
  1. 查询
m[key];    //使用前需要保证key在m中,否则会自动插入key的值
m.find(key);    //返回迭代器,找不到时返回m.end()
m.count(key);   //返回数量,找不到时返回值为0

使用m.begin()和m.end()迭代器遍历

for(auto i = m.begin(); i != m.end(); i++){
      cout<<i->first<<" "<<i->second<<endl;
}
  1. 容器大小

    m.size();
    m.max_size();
  2. 迭代器

    m.begin();
    m.end();

4. multimap

特点:一对多映射,基于关键字快速查找,允许重复值
实现:红黑树
常用方法:

5. C++11新特性

用hash实现map、multimap、set、multiset

  1. unordered_map
  2. unordered_multimap
  3. unordered_set
  4. unordered_multimset

三、容器适配器

1. stack栈

特点:先进后出
实现:deque
常用方法:

  1. 头文件 #include <stack>
  1. 创建

    stack<Type> st;
  2. 插入和删除

    st.push(elem);    //elem插入到栈顶
    st.pop();         //删除栈顶元素
  3. 查询

    st.top();    //返回栈顶元素
  4. 容器大小

    st.size();
  5. 判断是否为空

    st.empty();

2. queue

特点:先进先出,只能在尾部插入,只能在头部弹出
实现:deque
常用方法:

  1. 头文件 #inclue <queue>
  1. 创建和初始化

    queue<Type> que;
  2. 插入和删除

    que.push(elem);    //队列尾部插入元素
    que.pop();         //弹出队列头部元素
  3. 查询

    que.front();    //返回队列头的元素引用
    que.back();     //返回队列尾的元素引用
  4. 容器大小

    que.size();
  5. 判断是否为空

    que.empty();

3. priority_queue

特点:优先级最大的先出
实现:vector,堆排序,大顶堆/小顶堆
常用方法:

  1. 头文件 #include <queue>
  1. 创建和初始化

    priority_queue<int> pq;
    priority_queue<Type, container<Type>, op> pq;
    //container可以是C++中任意一种容器。op为排序规则,是仿函数。对基本类型,默认less<T>是大顶堆,也可以选greater<T>
    //仿函数
    struct cmp{
       bool operator() (Type &a, Type &b){
             return a > b; //小顶堆
       }
    }
  2. 插入和删除

    pq.push(elem);    //插入元素elem,并调整堆
    pq.pop();         //弹出堆顶(优先级最大)元素
  3. 查询

    pq.top();    //返回堆顶元素索引
  4. 容器大小

    pq.size();
  5. 判断优先队列是否为空

    pq.empty();
全部评论

相关推荐

牛客251490824号:你这不去保研找鸡毛工作
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务