STL学习总结

Posted on Edited on In Views:

常用容器

string容器

基本概念

  • string是C++风格的字符串，本质上是一个类。其内部封装了char*。

  • 成员函数主要有find，copy，delete，replace，insert

构造函数

  • string();//生成空string

  • string(const char* s);//以字符串s初始化

  • string(const string& str);//以string对象初始化另一个string对象

  • string(int n, char c);//以n个字符c初始化

赋值操作

  • string& operator=(const char* s);

  • string& operator=(const string &s);

  • string& operator=(char c);

  • string& assign(const char *s)

  • string& assign(const char *s, int n)

  • string& assign(const string &s)

  • string& assign(int n, char c);

字符串拼接

  • string& operator+=(const char* str);

  • string& operator+=(const char c);

  • string& operator+=(const string& str);

  • string& append(const char* s)

  • string& append(const char* s,int n);

  • string& append(const string& str);

  • string& append(const string &s,int pos,int n);//字符串s中从pos开始的n个字符连接到字符串结尾

查找和替换

  • int find(const string& str, int pos = 0) const;//从pos开始查找str出现的第一次位置

  • int find(const char* s,int pos = 0) const//从pos开始查找s出现的第一次位置

  • int fing(const char* s, int pos, int n) const;//从pos开始查找s的前n个字符出现的第一次位置

  • int find(const char c,int pos = 0) const//从pos开始查找c出现的第一次位置

  • int rfind(const string& str, int pos = npos) const;//从pos开始查找str出现的最后一次位置

  • int rfind(const char* s,int pos = npos) const//从pos开始查找s出现的最后一次位置

  • int rfind(const char* s, int pos, int n) const;//从pos开始查找s的前n个字符出现的最后一次位置

  • int find(const char c,int pos = 0) const//从pos开始查找c出现的最后一次位置

  • sting& replace(int pos, int n, const string& str)//替换从pos开始n个字符为字符串str

  • sting& replace(int pos, int n, const char* s)//替换从pos开始n个字符为字符串s

  • find是从左往右，rfind是从右往左，二者都是寻找第一次找到的字符或字符串，故从结果上来看find的结果是从左到右第一次出现的位置，rfind的结果是从左到右最后一次出现的位置。

  • find和rfind找不到字符时返回-1。

  • replace在替换时要指定替换的开始位置、字符数量和字符内容。

字符串比较

  • 比较方式：按ASCII码进行比较。
    = 返回 0
    > 返回 1
    < 返回 -1

  • int compare(const string& s) const;

  • int compare(const char* s) const;

字符串存取

  • char& operator[](int n);//通过[]取字符

  • char& at(int n);//通过at取字符

插入和删除

  • string& insert(int pos, const char* s);

  • string& insert(int pos, const string& str);

  • string& insert(int pos, int n, char c);//在pos位置插入n个字符c

  • string& erase(int pos, int n = npos);//删除从pos开始的n个字符

  • string& erase(pos);//删除pos处的一个字符

  • erase(first,last);//删除从first到last之间的字符

  • 插入和删除的下标都是从0开始。

子串

  • string substr(int pos = 0, int n = npos) const;//返回从pos开始的n个字符组成的字符串

vector容器

基本概念

  • vector数据结构和数组十分相似，也称为单端数组。

  • 数组是静态空间，而vector可以动态扩展。
    动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

  • vector的迭代器是支持随机访问的迭代器

构造函数

  • vector<T> v;//采用模板实现类实现，默认构造函数

  • vector<T> v(num)//创建容量为num的vector，默认值为0

  • vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身

  • vector(n, elem);//将n个elem拷贝给本身

  • vector(const vector& vec);//拷贝构造

赋值操作

  • vector& operator=(const vector& vec);

  • assign(beg, end);//将[beg, end)区间中的元素拷贝给本身

  • assign(n, elem);//将n个elem拷贝给本身

容量和大小

  • empty();//判断容器是否为空

  • capacity();//容器的容量

  • size();//容器的元素的个数

  • resize(int num);//重新指定容器的长度为num。若容器变长，则以默认值填充新位置；若容器变短，则多出的元素将被删除。

  • resize(int num, elem);//重新指定容器的长度为num。若容器变长，则以elem填充新位置；若容器变短，则多出的元素将被删除。

插入和删除

  • push_back(elem);//尾插元素elem

  • pop_back();//删除最后一个元素

  • insert(const_iterator pos, elem);//迭代器指向位置pos插入元素elem

  • insert(const_iterator pos, int count, elem);//迭代器指向位置pos插入count个元素elem

  • erase(const_iterator pos);//删除迭代器指向的元素

  • erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素

  • clear();//删除容器中所有元素

数据存取

  • at(int idx);//返回索引idx所指的数据

  • operator[];

  • front();//返回容器中的第一个元素

  • back();//返回容器中的最后一个元素

互换容器

  • swap(vec);//将vec与本身的元素互换

  • swap可以使两个容器互换，可以达到收缩内存效果。

预留空间

  • reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问

  • 预留空间可以减少vector在动态扩展容量时的扩展次数。如果数据量较大，可以一开始利用reserve预留空间。

deque容器

基本概念

  • vector对于头部的插入效率低，数据量越大，效率越低。deque相对而言对头部的插入速度更快。但是vector访问元素的速度更快。这与两者内部的实现有关。

  • 内部工作原理：deque内部有个中控器，维护每段缓冲区的内容，缓冲区中存放真实数据。中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间。

  • deque容器的迭代器也是支持随机访问的。

构造函数

  • deque<T>depT;

  • deque(beg,end);//将[beg, end)区间中的元素拷贝给本身

  • deque(n,elem);//将n个elem拷贝给本身

  • deque(const deque& dep);//拷贝构造函数

赋值操作

  • deque& operator=(const deque& dep);

  • assign(beg, end);//将[beg, end)区间中的元素拷贝给本身

  • assign(n, elem);//拷贝构造函数

大小操作

  • deque.empty();//判断容器是否为空

  • deque.size();//返回容器中元素的个数

  • deuqe.resize(int num);//重新指定容器的长度为num。若容器变长，则以默认值填充新位置；若容器变短，则多出的元素将被删除。

  • dque.resize(int num, elem);//重新指定容器的长度为num。若容器变长，则以elem填充新位置；若容器变短，则多出的元素将被删除。

  • deque容器没有容量的概念。

插入和删除

  • push_back(elem);//在容器尾部添加一个数据

  • push_front(elem);//在容器头部添加一个数据

  • pop_back;//删除容器的最后一个数据

  • pop_front;//删除容器的第一个数据

  • insert(pos, elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置

  • insert(pos, n, elem);//在pos位置插入n个elem数据，无返回值

  • insert(pos, beg, end);//在pos位置插入[beg,end)区间的数据，无返回值。

  • clear();//清除所有数据

  • erase(beg, end);//删除[beg, end)区间的数据u，返回下一个数据的位置

  • erase(pos);//删除pos位置的数据，返回下一个数据的位置

  • 插入和删除提供的位置是迭代器

数据存取

  • at(int, idx);//返回索引idx所指的数据

  • operator[];

  • front();//返回第一个元素

  • end();//返回最后一个元素

排序

  • sort(iterator beg, iterator end);//对beg和end之间的元素进行排序

  • sort算法使用时应包含头文件 algorithm。

stack容器

基本概念

stack是一种先进后出的数据结构，它只有一个出口。栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为。栈中进出数据称为入栈，栈中弹出数据称为出栈。

常用接口

构造函数

  • stack<T> stk;

  • stack(const stack& stk);//拷贝构造

赋值操作

  • stack& operator=(const stack& stk);

数据存取

  • push(elem);//向栈顶添加数据

  • pop();//从栈顶移除一个数据

  • top();//返回栈顶元素

大小操作

  • empty();//判断堆栈是否为空

  • size();//返回栈的大小

queue容器

基本概念

queue是一种先进先出的数据结构，它有两个出口。队列容器允许从一端新增元素，从另一端移除元素。队列中只允许队头和队尾才可以被外界使用，因此队列不允许有遍历行为。队列中进数据称为入队(push)，出数据称为出队(pop)。

构造函数

  • queue<T> que;

  • queue(const queue& que);//拷贝构造

赋值操作

  • queue& operator=(const queue& que);

数据存取

  • push(elem);//往队尾添加元素

  • pop();//删除队头第一个元素

  • back();//返回最后一个元素

  • front();//返回第一个元素

大小操作

  • empty();//判断堆栈是否为空

  • size();//返回栈的大小

list容器

基本概念

  • 链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针连接实现的。链表由一系列结点组成。结点有数据域和下一个结点地点的指针域组成。STL的链表是一个双向循环链表。由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。

  • list的优点是采用动态存储分配，不会造成内存浪费和溢出；链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。

  • list的缺点是链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大。

  • list有一个重要的性质，插入和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

构造函数

  • list<T> lst;

  • list(beg, end);//将[beg, end)区间中的元素拷贝给本身

  • list(n, elem);//将n个elem拷贝给本身

  • list(const list& lst);//拷贝构造函数

赋值与交换

  • assign(beg, end);//将[beg, end)区间中的元素拷贝给本身

  • asign(n, elem);//将n个elem拷贝给本身

  • list& operator = (const list& lst);

  • swap(lst);//将lst于本身的元素互换

大小操作

  • size();//返回容器中元素的个数

  • empty();//判断容器是否为空

  • resize();//重新指定容器的长度为num。若容器变长，则以默认值填充新位置；若容器变短，则多出的元素将被删除。

  • resize(int num, elem);//重新指定容器的长度为num。若容器变长，则以elem填充新位置；若容器变短，则多出的元素将被删除。

插入和删除

  • push_back(elem);//尾插一个元素

  • pop_back();//删除最后一个元素

  • push_front(elem);//在容器开头插入一个元素

  • pop_front();//删除第一个元素

  • insert(pos, elem);//在pos位置插elem元素的拷贝

  • insert(pos, n, elem);//在pos位置插入n个elem

  • insert(pos, beg, end);//在pos位置插入[beg, end)区间的数据，无返回值

  • clear();//删除容器所有元素

  • erase(beg, end);//删除[beg, end)区间的数据，返回下一个元素的位置

  • erase(pos);//删除pos位置的数据，返回下一个数据的位置

  • remove(elem);//删除容器中所有与elem值匹配的元素

数据存取

  • front();//返回第一个元素

  • back();//返回最后一个元素

  • list容器中不可以通过[]或者at方式访问数据。

反转和排序

  • reverse();//反转链表

  • sort();//链表排序

set/ multiset容器

基本概念

  • 所有元素都会在插入时自动排序。

  • set/ multiset属于关联式容器，底层结构由二叉树实现。

  • 区别：set不允许容器中有重复的元素；multiset允许容器中有重复元素。

构造和赋值

  • set<T> st;

  • set(const set& st);//拷贝构造函数

  • set& operator=(const set& st);

大小和交换

  • size();//返回容器中元素的个数

  • empty();//判断容器是否为空

  • swap();//交换两个容器

插入和删除

  • insert(elem);//插入元素elem

  • clear();//清空容器

  • erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器

  • erase(beg, end);//删除区间[beg, end)的所有元素，返回下一个元素的迭代器

  • erase(elem);//删除容器中所有与elem值匹配的元素

查找和统计

  • find(key);//查找key是否存在，若存在返回该元素的迭代器；若不存在返回set.end()

  • count(key);//统计key的元素个数（对于set，结果为0或1）

set和multiset的区别

  • set不可以插入重复数据，而multiset可以。

  • set插入数据的同时会返回插入结果，表示插入是否成功。返回的内容为对组，first为迭代器，second为bool。

  • multiset不会检测数据，因此可以插入重复数据。

pair对组创建

  • pair<type, type> p ( value1, value2 );

  • pair<type, type> p = make_pair( value, value2 );

容器排序

set/ multiset容器容器默认排序规则为从小到大，可利用仿函数改变排序规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <set>
#include <string>
class Person {
    public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    string m_Name;
    int m_Age;
};
//仿函数
class comparePerson {
    public:
    bool operator()(const Person& p1, const Person &p2) {
        //按照年龄进行排序  降序
        return p1.m_Age > p2.m_Age;
    }
};

void test01()
{
    set<Person, comparePerson> s;

    Person p1("刘备", 23);
    Person p2("关羽", 27);
    Person p3("张飞", 25);
    Person p4("赵云", 21);

    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    s.insert(p4);

    for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;
    }
}
int main() {

    test01();

    system("pause");

    return 0;
}

map/ multimap容器

基本概念

  • map/ multimap容器中所有容器都是pair。

  • pair中第一个元素为key，起到索引作用，第二个元素为value。

  • 所有元素都会根据元素的key自动排序。

  • map/ multimap容器数据关联式容器，底层结构由二叉树实现。

  • 可以根据key值快速找到value值。

  • 区别：map不允许容器中有重复key值元素；multimap允许容器中有重复key值元素。

构造和赋值

  • map<T1, T2> mp;

  • map(const map& mp);//拷贝构造函数

  • map& operator=(const map& mp);

大小和交换

  • size();//返回容器中元素的数目

  • empty();//判断容器是否为空

  • swap(st);//交换两个容器

插入和删除

  • map中所有元素都是成对出现，插入数据时候要使用对组

  • insert(elem);//插入元素elem

  • clear();//清除所有元素

  • erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器

  • erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器

  • erakey(key);//删除容器中值为key的元素

查找和统计

  • find(key);//查找key是否存在，若存在返回该元素的迭代器；若不存在返回map.end()

  • count(key);//统计key的元素个数（对于map，结果为0或1）

容器排序

map/ multimap容器容器默认排序规则为从小到大，可利用仿函数改变排序规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <map>

class MyCompare {
    public:
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};

void test01() {
    //默认从小到大排序
    //利用仿函数实现从大到小排序
    map<int, int, MyCompare> m;

    m.insert(make_pair(1, 10));
    m.insert(make_pair(2, 20));
    m.insert(make_pair(3, 30));
    m.insert(make_pair(4, 40));
    m.insert(make_pair(5, 50));

    for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
        cout << "key:" << it->first << " value:" << it->second << endl;
    }
}
int main() {

    test01();

    system("pause");

    return 0;
}

常用算法

  • 算法主要是由头文件<algorithm> <functional> <numeric> 组成。

  • 是所有STL头文件中最大的一个，范围涉及到比较、 交换、查找、遍历操作、复制、修改等等

  • 体积很小，只包括几个在序列上面进行简单数学运算的模板函数

  • 定义了一些模板类,用以声明函数对象。

常用遍历算法

for_each

  • for_each(iterator beg, iterator end, _func);// beg 开始迭代器; end 结束迭代器; _func 函数或者函数对象

  • 实现容器的遍历

transform

  • transform(iterator beg1, iterator end1, iterator beg2, _func);//beg1 源容器开始迭代器; end1 源容器结束迭代器; beg2 目标容器开始迭代器; _func 函数或者函数对象

  • 搬运容器到另一个容器中

  • 搬运的目标容器必须要提前开辟空间，否则无法正常搬运

常用查找算法

find

  • find(iterator beg, iterator end, value);//beg 开始迭代器; end 结束迭代器; value 查找的元素

  • 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

find_if

  • find_if(iterator beg, iterator end, _Pred);// beg 开始迭代器; end 结束迭代器; _Pred 函数或者谓词（返回bool类型的仿函数）

  • 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

adjacent_find

  • adjacent_find(iterator beg, iterator end);//beg 开始迭代器; end 结束迭代器

  • 查找相邻重复元素,返回相邻元素的第一个位置的迭代器

  • bool binary_search(iterator beg, iterator end, value);// beg 开始迭代器;end 结束迭代器;value 查找的元素

  • 查找指定的元素，查到 返回true 否则false

  • 在无序序列中不可用

count

  • count(iterator beg, iterator end, value);// beg 开始迭代器; end 结束迭代器; value 统计的元素

  • 统计元素出现次数

  • 统计自定义数据类型时，需要配合重载 operator==

count_if

  • count_if(iterator beg, iterator end, _Pred);// beg 开始迭代器; end 结束迭代器; _Pred 谓词

  • 按条件统计元素出现次数

常用排序算法

sort

  • sort(iterator beg, iterator end, _Pred);//beg 开始迭代器; end 结束迭代器; _Pred 谓词

  • 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

random_shuffle

  • random_shuffle(iterator beg, iterator end);//beg 开始迭代器; end 结束迭代器

  • 指定范围内的元素随机调整次序

  • 使用时需要添加随机数种子

merge

  • merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

  • 容器元素合并，并存储到另一容器中

  • 两个容器必须是有序的

reverse

  • reverse(iterator beg, iterator end);//beg 开始迭代器; end 结束迭代器

  • 反转指定范围的元素

常用拷贝和替换算法

copy

  • copy(iterator beg, iterator end, iterator dest); //beg 开始迭代器; end 结束迭代器; dest 目标起始迭代器

  • 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

replace

  • replace(iterator beg, iterator end, oldvalue, newvalue);//beg 开始迭代器; end 结束迭代器; oldvalue 旧元素; newvalue 新元素

  • 将区间内旧元素 替换成 新元素

replace_if

  • replace_if(iterator beg, iterator end, _Pred, newvalue);//beg 开始迭代器; end 结束迭代器; _pred 谓词; newvalue 替换的新元素

  • 按条件替换元素，满足条件的替换成指定元素

swap

  • swap(container c1, container c2);//c1容器1; c2容器2

  • 互换两个容器的元素，两个容器要同种类型

常用算术生成算法

  • 算术生成算法属于小型算法，使用时包含的头文件为#include

accumulate

  • accumulate(iterator beg, iterator end, value);//beg 开始迭代器； end 结束迭代器； value 起始值

  • 计算容器元素累计总和

fill

  • fill(iterator beg, iterator end, value); //beg 开始迭代器; end 结束迭代器; value 填充的值

  • 向容器中填充指定元素

常用集合算法

set_intersection

  • set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);// beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

  • 求两个集合的交集

  • 两个集合必须是有序序列

  • 目标容器开辟空间需要从两个容器中取小值

  • set_intersection返回值既是交集中最后一个元素的位置

set_union

  • set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

  • 求两个集合的并集

  • 两个集合必须是有序序列

  • 目标容器开辟空间需要两个容器相加

  • set_union返回值既是并集中最后一个元素的位置

set_difference

  • set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

  • 求两个集合的差集

  • 两个集合必须是有序序列

  • 目标容器开辟空间需要从两个容器取较大值

  • set_difference返回值是差集中最后一个元素的位置