Containers

array

头文件：#include <>

bitset

头文件：#include <bitset>

  • 构造

    1
2
3

    std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));

  • 访问bitset

    • operator[] ：返回pos的位（bool）[不执行边界检查]
    • count
      • 1的个数 .count()
      • 0的个数 .size()-.count()
    • size : 个数
    • test : 1返回true，0返回false [有边界检查out_of_range]
    • any : 至少有一位是1的时候返回true
    • none ： 全是0返回true
    • all

  • 位操作 (return type: bitset& value is *this)

    ​ 无参数– all bits, 有pos参数 – single bits

    • set
    • reset
    • flip

  • to操作

    • to_string operator<<
    • to_ulong Return unsigned long
    • to_ullong Return unsigned long long

  • 运算符

    • ^= 、 &=、 |= (XOR AND OR assign)
    • «=2 、 »=1 (SHL SHR assign)
    • ~ 、«1、 »1 (NOT SHL SHR)
    • == 、!= 、 & 、 | 、 ^

deque

头文件：#include <>

forward_list

头文件：#include <>

list

头文件：#include <>

map

头文件：#include <>

map是红黑树，带排序

queue

头文件：#include <queue>

FIFO（先进先出队列）

Priority（优先队列）

1
2
3
4
5
6

priority_queue< type, container, function >
//大顶堆
priority_queue<int> big_heap;
priority_queue<int,vector<int>,less<int> > big_heap2; 
//小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;

  • type 数据类型

  • container 底层容器 例如vector（默认） deque

  • 默认大堆，每次输出最大元素 （less<int> greater<int>需要头文件#include <functional>）

  • 成员函数

    • bool empty() 空返回true
    • int size() 返回元素数量
    • int top() 返回顶部元素（不删除）
    • void push(int arg) 插入队列
    • emplace(C++11) 原地构造一个元素 插入队列
    • void pop() 删除队列顶部元素
    • swap (C++11)

set

头文件：#include <>

stack

头文件：#include <>

unordered_map

头文件：#include <unordered_map>

unordered_map是Hash表，查找时间复杂度O(1)，元素是无序的

  • 构造

    1
2
3
4
5

    std::unordered_map<std::string,std::string> empty;
std::unordered_map<std::string,std::string> init_list({{"apple","red"},{"lemon","yellow"}});
std::unordered_map<std::string,std::string> copy_list(init_list);
std::unordered_map<std::string,std::string> move_list(merge(init_list,copy_list));
std::unordered_map<std::string,std::string> range_list(move_list.begin(),move_list.end());

  • 容量数量

    • empty / size / max_size

  • 迭代器

    • begin / end / cbegin / cend

  • 元素访问

    • operator[]

    • at 会抛出异常

      1
2
3
4
5
6
7
8

        std::unordered_map<std::string,int> mymap = {
                { "Mars", 3000},
                { "Saturn", 60000},
                { "Jupiter", 70000 } };

  mymap.at("Mars") = 3396;
  mymap.at("Saturn") += 272;
  mymap.at("Jupiter") = mymap.at("Saturn") + 9638;

  • 元素查找

    • find

      1
2
3
4
5

      auto got = map.find(key);
if (got == map.end())
	//没找到
else
    //找到

    • count

    • equal_range

  • 修改

    • emplace
    • emplace_hint
    • insert
    • erase
    • clear
    • swap

  • 桶

    • bucket_count
    • max_bucket_count
    • bucket_size
    • bucket

  • Hash策略

    • load_factor
    • max_load_factor
    • rehash
    • reserve

  • 观察者

    • hash_function
    • key_eq
    • get_allocator

  • 运算符

unordered_set

头文件：#include <>

vector

头文件：#include <vector>