字符串

    string s = "Hello World";

    // Element access
    s[0];
    s.front();
    s.back();

    // Iterators
    s.begin();
    s.end();

    // Capacity
    s.empty();
    s.size();

    // Operations
    s.clear();
    s.insert(s.begin(), '1');
    s.insert(s.end(), '2');
    s.erase(s.begin());
    s += '3';
    s.compare("Hello World");
    s.substr(4, 5);

    // Search
    s.find("zhang");// string::nops

    to_string(INT_MAX);
    to_string(INT_MIN);
    stoi(max);
    stoi(min);

    isspace('a');
    isalpha('a');
    isupper('A');
    islower('a');
    isdigit('1');

Containers Library

容器	底层数据结构	时间复杂度	有无序	可不可重复
array	数组	随机读改 O(1)	无序	可重复	支持快速随机访问
vector	数组	随机读改、尾部插入、尾部删除 O(1),头部插入、头部删除 O(n)	无序	可重复
list	双向链表	插入、删除 O(1),随机读改 O(n)	无序	可重复
set	红黑树	插入、删除、查找 O(log2n)	有序	不可重复
multiset	红黑树	插入、删除、查找 O(log2n)	有序	可重复
map	红黑树	插入、删除、查找 O(log2n)	有序	不可重复
multimap	红黑树	插入、删除、查找 O(log2n)	有序	可重复
hash_set	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	不可重复
hash_multiset	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	可重复
hash_map	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	不可重复
hash_multimap	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	可重复
stack	list	顶部插入、顶部删除 O(1)	无序	可重复
queue	list	尾部插入、头部删除 O(1)	无序	可重复
priority_queue	vector+max-heap	插入、删除 O(log2n)	有序	可重复

序列容器(Sequence Containers)

array(数组)

static contiguous array

    array<int,4> a = {7,5,16,8};

    // Element access
    a[0];
    a.front();
    a.back();

    // Iterators
    a.begin();
    a.end();

    // Capacity
    a.empty();
    a.size();

vector(数组)

dynamic contiguous array

    vector<int> v = {7,5,16,8};
    vector<int> v1(2,0);
    vector<int> v2(v.begin(),v.end());

    // Element access
    v[0];
    v.front();
    v.back();

    // Iterators
    v.begin();
    v.end();

    // Capacity
    v.empty();
    v.size();
    v.max_size();
    v.reserve();
    v.capacity();
    v.shrink_to_fit();
    // vector是按照容器现在容量的一倍进行增长.vector容器分配的是一块连续的内存空间,每次容器的增长,并不是在原有连续的内存空间后再进行简单的叠加,而是重新申请一块更大的新内存,并把现有容器中的元素逐个复制过去,同时销毁旧的内存.这时原有指向旧内存空间的迭代器已经失效,所以当操作容器时,迭代器要及时更新

    // Modifiers
    v.clear();
    v.insert(v.begin(),1);
    v.insert(v.end(),2);
    // Iterator pointing to the inserted value
    v.erase(v.begin());
    // Iterator following the last removed element. If the iterator pos refers to the last element, the end() iterator is returned
    v.push_back(3);
    v.pop_back();

list(链表)

doubly-linked list

    list<int> l = {7,5,16,8};

    // Element access
    l.front();
    l.back();

    // Iterators
    l.begin();
    l.end();

    // Capacity
    l.empty();
    l.size();

    // Modifiers
    l.clear();
    l.insert(l.begin(),1);
    l.insert(l.end(),2);
    l.erase(l.begin());
    l.push_back(3);
    l.pop_back();
    l.push_front(4);
    l.pop_front();

关联容器(Associative Containers)

set

collection of unique keys,sorted by keys

    set<int> treeset;

    // Iterators
    treeset.begin();
    treeset.end();

    // Capacity
    treeset.empty();
    treeset.size();

    // Modifiers
    treeset.clear();
    treeset.insert(1);
    treeset.erase(2);

    // Lookup
    treeset.count(1);
    treeset.find(1);// treemap.end()

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

map

collection of key-value pairs,sorted by keys,keys are unique

    map<int, int> treemap;

    // Iterators
    treemap.begin();
    treemap.end();

    // Capacity
    treemap.empty();
    treemap.size();

    // Modifiers
    treemap.clear();
    treemap.insert(make_pair(1, 1));
    treemap[2] = 2;
    treemap.erase(1);

    // Element access
    treemap[2] = 2;

    // Lookup
    treemap.count(1);
    treemap.find(1);

    for (auto it = treemap.begin(); it != treemap.end(); it++) {
        cout << it->first << ' ' << it->second << endl;
    }

无序关联容器(Unordered Associative Containers)

unordered_set

collection of unique keys,hashed by keys

    unordered_set<int> hashset;

    // Iterators
    hashset.begin();
    hashset.end();

    // Capacity
    hashset.empty();
    hashset.size();

    // Modifiers
    hashset.clear();
    hashset.insert(1);
    hashset.erase(1);

    // Lookup
    hashset.count(1);
    hashset.find(1);

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

unordered_map

collection of key-value pairs,hashed by keys,keys are unique

    unordered_map<int, int> hashmap;

    // Iterators
    hashmap.begin();
    hashmap.end();

    // Capacity
    hashmap.empty();
    hashmap.size();

    // Modifiers
    hashmap.clear();
    hashmap.insert(make_pair(1, 1));
    hashmap[2] = 2;
    hashmap.erase(1);

    // Element access
    hashmap[2] = 2;

    // Lookup
    hashmap.count(1);
    hashmap.find(1);

    for (auto it = hashmap.begin(); it != hashmap.end(); it++) {
        cout << it->first << ' ' << it->second << endl;
    }

容器适配器(Container Adaptors)

stack(栈)

adapts a container to provide stack(LIFO data structure)

    stack<int> s;

    // Element access
    s.top();

    // Capacity
    s.empty();
    s.size();

    // Modifiers
    s.push(1);
    s.pop();

queue(队列)

adapts a container to provide queue(FIFO data structure)

    queue<int> q;

    // Element access
    q.front();
    q.back();

    // Capacity
    q.empty();
    q.size();

    // Modifiers
    q.push(1);
    q.pop();

priority_queue(优先队列)

adapts a container to provide priority queue

    priority_queue<int> pq; // 大根堆
    priority_queue<int,vector<int>,greater<>> pq2;// 小根堆

    // Element access
    pq.top();

    // Capacity
    pq.empty();
    pq.size();

    // Modifiers
    pq.push(1);
    pq.pop();