版本比较

旧版本 13

changes.mady.by.user zhongluqiang

保存于

比较

新版本 14

changes.mady.by.user zhongluqiang

保存于

标识

  • 该行被添加。
  • 该行被删除。
  • 格式已经改变。

STL基本概念

  • 容器：用于存放数据的类模板，比如vector, list, stack, queue等。
  • 迭代器：用于存取容器中存放的元素，可以理解成指针，用于遍历和操作容器。使用迭代器可以实现以相同的风格访问和操作大部分的容器。
  • 算法：用来操作容器中元素的函数模板，比如sort, unique等。

容器

用于存放元素，实例化时指定元素类型。如果存储的是一个对象，那么最好重载==和<运算，因为大部分算法都会用这两个运算符来进行相等判断和排序。

容器分为两大类：

顺序容器：可变长动态数组vector、双端队列deque、双向链表list。顺序容器的元素具有前后关系，可指定位置插入和删除。

关联容器：set、multiset、map、multimap。关联容器的元素是排序过的，不能指向插入位置。插入的元素会自动排序。默认情况下，关联容器中的元素按从小到大排序，使用运算符"<"进行比较。关联容器在查找时有很好的性能。

容器适配器：栈stack、队列queue、优先队列priority_queue。在上两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能。


任何两个容器对象，只要类型相同，就可以用<、<=、>、>=、==、!=进行字典式的比较，它们的运行规则如下：

a == b: a和b中的元素个数相同，且对应元素相等，使用==运算符。

a < b: 类似于单词的字典序比较，使用<运算符。

a != b: 等价于!(a == b)。

a > b: 等价于 b < a。

a <= b：等价于 !(b < a)。

a >= b: 等价于!(a < b)。


所有的容器都有以下两个成员函数：

int size()：返回容器对象中元素的个数。

bool empty()：判断容器对象是否为空。


顺序容器和关联容器还有以下成员函数：

begin(): 返回指向容器第一个元素的迭代器。

end(): 返回指向容器最后一个元素后面的位置的迭代器。

rbegin(): 返回指向容器最后一个元素的反向迭代器。

rend(): 返回指向容器第一个元素前面的位置的迭代器。

erase(): 删除一个或几个元素。

clear(): 删除所有元素。


顺序容器还有以下常用成员函数：

front(): 返回容器中第一个元素的引用。

back(): 返回容器中最后一个元素的引用。

push_back(): 在容器末尾增加新的元素。

pop_back(): 删除容器末尾的元素。

insert(): 插入一个或多个元素。

迭代器

用于访问容器中的元素，有以下四种：

1. 正向迭代器，定义方法如下：

代码块
容器类名::iterator 迭代器名;

2. 常量正向迭代器，定义方法如下：

代码块
容器类名::const_iterator 迭代器名;

3. 反向迭代器，定义方法如下：

代码块
容器类名::reverse_iterator 迭代器名;

4. 常量反向迭代器，定义方法如下：

代码块
容器类名::const_reverse_iterator 迭代器名;

注意，容器适配器stack、queue和priority_queue没有迭代器，它们有自己的方法用于访问元素。

不同的容器的迭代器功能有强弱之分，这决定了容器是否支持某种STL算法，比如，排序算法sort需要通过迭代器支持随机访问功能，如果某种容器不支持随机访问，如list，那就不支持使用sort进行排序。

常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问5种：

正向迭代器：支持++p和p++、*p，两个迭代器可以赋值，可以用==和!=比较；

双向迭代器：支持正向迭代器的全部功能，还支持--p和p--；

随机访问迭代器：在双向迭代器的基础上，支持 p+i、p-i、p+=i、p-=i、p[i]，还支持 <、>、<=、>=比较。

不同容器的迭代器功能：

容器迭代器功能
vector随机访问
deque随机访问
list双向
set/multiset双向
map/multimap双向
stack不支持
queue不支持
priority_queue不支持


迭代器的辅助函数：

advance(p, n): 使迭代器向前或向后移动n个元素。

distance(p, q): 计算两个迭代器之间的距离，即p经过多少次++后和q相等，如果p本身就在q后面，则这个函数会陷入死循环。

iter_swap(p, q): 用于交换两个迭代器q、q指向的值，相当于通过指针交换元素内容。

算法

能在各种容器上通用的函数模板，通过迭代器来操作元素。

大部分算法需要通过迭代器提供一个操作区间，比如begin()~end()。

有的算法返回一个迭代器，比如find算法。

排序、查找等算法需要对元素进行比较，比较判断大小及是否相等。在STL中，比较大小通过"<"运算符来实现，和">"无关。而比较相等时，并不一定是使用"=="运行符，而是要根据情况来确定。如果是在未排序的区间上应用find进行查找，那么使用"=="运算符来判断相等。如果是在已经排序好的区间上进行查找、合并等操作（比如折半查找算法binary_search，关联容器自身的find成员函数)，那么判断x=y的条件是x<y和y<x同时为假。如果一个类将"<"运算符重载为永远返回false，那么对于STL算法来说，这个类的所有对象都是相等的。


vector

可变长数组，支持以下迭代器：

  • begin()/end()
  • rbegin()/rend()
  • cbegin()/cend()
  • crbegin()/crend()


支持以下容量相关的操作：

  • size()
  • empty()
  • resize()
  • reserve()
  • capacity()

注意：size()和resize()是配套的，用于调整数组的实际大小，调小时截断，调大时补零。reserve()和capacity()是配套的，用于调整数组的预分配空间大小，这个大小不影响数组的内容和size()的返回值。如果对性能要求不高，那么完全不需要调用reserve()来预分配空间，而是只使用vector默认的增长策略。


支持以下元素访问操作：

  • 下标操作符[]
  • front()
  • back()

注意front()和back()都是返回引用，也就是可以直接通过这两个函数的返回值来修改元素。


支持以下修改操作：

  • push_back()
  • pop_back()
  • insert()
  • erase()
  • clear()


以下是vector的一些示例操作：

代码块
linenumberstrue
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v1{1, 2, 3, 4, 5};

    cout << "size:" << v1.size() << endl;           // 5
    cout << "capacity:" << v1.capacity() << endl;   // 5

    v1.reserve(15);
    cout << "size:" << v1.size() << endl;           // 5
    cout << "capacity:" << v1.capacity() << endl;   // 15


    v1.resize(10);
    cout << "size:" << v1.size() << endl;           // 10, 后面的5个元素值为全零
    cout << "capacity:" << v1.capacity() << endl;   // 15

    v1.resize(5); // 截断后面5个元素

    // 正向遍历
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 反向遍历，注意it仍为++
    for(auto it = v1.rbegin(); it != v1.rend(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 访问元素
    v1.front();
    v1.front() = 0;
    v1.back();
    v1.back() = 6;

    // 修改元素
    v1.push_back(6);
    v1.pop_back();
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // insert
    v1.insert(v1.begin(), -1);      // 在指定位置之前插入
    v1.insert(v1.end(), 7);
    v1.insert(v1.begin(), 5, -2);   // 批量插入
    {
        vector<int> tmp{8, 9, 10};
        v1.insert(v1.end(), tmp.begin(), tmp.end());  // 在指定位置插入一个区间的值
    }
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // erase
    v1.erase(v1.begin());                   // 删除当前位置的元素
    v1.erase(v1.begin(), v1.begin() + 4);   // 删除一个区间的元素
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    return 0;
}

list

与vector同为顺序容器，但是不支持随机访问，其访问过程只能是从前往后遍历或是从后往前遍历。

支持的迭代器如下：

  • begin()/end()
  • rbegin()/rend()
  • cbegin()/cend()
  • crbegin()/crend()

以上迭代器只支持双向操作，也就是it++和it--，不支持随机访问，比如it+n。

容量相关的操作如下：

  • size()
  • empty()

元素访问：

  • front()
  • back()

修改元素：

  • push_front()
  • pop_front()
  • push_back()
  • pop_back()
  • insert()
  • resize()

上面的resize()和vector的resize()类似，用于重新分配大小，不够补上空的元素，多了截断多余的元素。


示例代码：

代码块
linenumberstrue
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> a{1, 2, 3, 4, 5};

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

    // 前后插入/删除元素
    a.pop_front();
    a.pop_back();
    a.push_front(0);
    a.push_back(6);

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

    // 删除单个元素
    for(auto it = a.begin(); it != a.end(); it++) {
        if(*it == 3) {
            a.erase(it);
            break; // 这里必须break，因为it被删除后已经被回收了，不再指向下一个元素
        }
    }

    // 循环体中删除元素
    auto it = a.begin();
    while(it != a.end()) {
        if(*it == 2) {
            it = a.erase(it); // 返回删除元素的下一个元素
        } else {
            it++;
        }
    }

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

    return 0;
}

queue/deque

queue和deque都是队列，用于先进先出操作，不同的是queue只能在一头插入，在另一头弹出，而deque两头都可以插入和弹出，通过比较它们支持的方法即可分辨出区别：

queue支持的方法：

代码块
push();
pop();
front();
back();
size();
empty();
clear();

deque支持的方法：

代码块
push_front();
push_back();
pop_front();
pop_back();
front();
back();
size();
empty();
clear();

stack

先进后出，支持以下方法：

代码块
push();
pop();
top();
size();
emtpy();

注意stack不支持清空操作！！！如果要清空一个队列，可以将其与一个空的栈进行swap。

set

集合类型，用于去重和排序，默认使用==进行相等判断，使用<进行排序，也就是说如果想实现自定义类型的set操作，则必须要重载该类型的==和<运算符。

set默认按从小到大排序，如果想改成从大到小，则以下是供参考的写法：

代码块
set<int> s1;               // s1按从小到大排序，等效于set<int, less<int>> s1;
set<int, greater<int>> s2; // s2按从大到小排序

auto comp = [](int a, int b) { return a < b; }; // 自定义比较方法
set<int, decltype(comp)> s3(comp);

class Comp {    // 自定义比较方法，仿函数形式
    bool operator()(int a, int b) { return a < b; } 
};
set<int, Comp> s4;


set支持全部的四种类型的迭代器，但是只能进行双向迭代，也就是it++和it--。

容量操作：

  • size()
  • empty()

修改元素：

  • insert()
  • erase()
  • clear()

集合操作：

  • find()
  • count()
  • lower_bound()
  • upper_bound()
  • equal_range()

示例代码：

代码块
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(4);
    s.insert(3);
    s.insert(2);
    s.insert(1);
    
    // 遍历
    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 查找与删除元素
    auto it = s.find(1);
    if(it != s.end()) {
        s.erase(it);
    }
    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // lower_bound，找第一个大于或等于的元素的位置
    auto it1 = s.lower_bound(3);
    cout << "it1:" << *it1 << endl; // 3

    // upper_bound，找第一个大于某个元素的位置
    auto it2 = s.upper_bound(4);
    cout << "it2:" << *it2 << endl; // 5

    // 查找指定元素的范围，由于set是去重的，所以返回的区间长度只能是1或0
    auto p = s.equal_range(4);
    cout << "first:" << *p.first << ", second:" << *p.second << endl;
    cout << "distance:" << distance(p.first, p.second) << endl;

    return 0;
}

unordered_set

无序集合，使用哈希表实现，相比于set，由于是无序的，所以不支持lower_bound/upper_bound操作，也无需在构造时指定比较函数。

unordered_set只支持正向遍历，所以不存在反正迭代器。unordered_set的迭代器只支持++操作。

unordered_set支持的所有方法如下：

迭代器：

  • begin()/end()
  • cbegin()/cend()

容量相关：

  • size()
  • empty()

查找：

  • find()
  • count()

修改：

  • insert()
  • erase()
  • clear()





































目录