[C++ 面试基础知识总结] 顺序容器

[C++ 面试基础知识总结] 顺序容器

参考书籍：《C++ Primer》

目录

顺序容器与选择

顺序容器类型：
vector 可变大小数组
deque 双端队列
list 双向链表
forward_list 单向链表
array 固定大小数组
string 专门用于保存字符的可变大小数组

选择容器的基本原则：
1.默认情况用vector
2.小元素多，空间额外开销重要的时候避免使用list或forward_list
3.要求随机访问元素时，用vector或deque
4.要求在容器中间插入或删除元素时，用list或forward_list
5.需要在头尾插入或删除元素，但不会在中间进行次操作时，用deque

复合使用：如果一个程序只有在读取输入时才需要在容器中间插入元素，随后需要随机访问元素，则可以在输入阶段使用list，一旦输入完成后，将list中的内容拷贝到一个vector中。

迭代器

迭代器的基本操作可以参考：[C++ 面试基础知识总结]字符串，向量和数组

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。除forward_list以外的顺序容器还支持按逆序寻址元素的迭代器reverse_iterator。采用rbegin和rend操作分别生成指向容器尾元素和收元素之前位置的迭代器。

    list<string> a ;
    auto i1 = a.begin();   //list<string>::iterator
    auto i2 = a.rbegin();  //list<string>::reverse_iterator
    auto i3 = a.cbegin();  //list<string>::const_iterator
    auto i4 = a.crbegin(); //list<string>::const_reverse_iterator
1
2
3
4
5

容器的初始化和赋值

创建一个容器为另一个容器的拷贝时，两个容器的类型和其存放的元素类型都必须匹配。用传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了，容器中的元素类型也可以不同，只要是可以转换的即可。

    list<int> l(10,0);
    //拷贝容器
    list<int> l2(l);
    //采用迭代器拷贝范围
    vector<double> v (l.begin(),l.end());
1
2
3
4
5

array的大小也是类型的一部分，当定义一个array时，除了指定元素类型，还要指定容器大小。

    //正确，保存10个int的数组
    array<int,10> a1;
    //错误，array<int>不是一个容器
    array<int> a2;
1
2
3
4

进行赋值运算时，如果两个容器原来大小不等，则让两个容器的大小都与右边容器的原大小相等。

    list<int> l(10,1);
    list<int> l2(5,-1);
    l = l2;
    //l的大小为5，即l2的大小
    cout << l.size() << endl;
1
2
3
4
5

除array以外的顺序容器都支持assign，assign可以将右边运算对象的元素拷贝到左边运算对象中，也可以指定数目且具有相同给定值的元素替换容器中的原有元素。

    list<string> l;
    vector<const char *> v;
    //将v中的元素替换为该范围内的元素
    v.assign(l.begin,l.end);
    //将v中的元素替换为5个0
    v.assign(5,0);
1
2
3
4
5
6

顺序容器操作

添加元素

using namespace std;
 
struct People{
    People(const string &name, int age): name(name),age(age){}
    string name;
    int age;
};
 
int main(int argc, const char * argv[]) {
    list<People> l;
    vector<People> v;
 
    People p("Summer",26);
 
    l.push_front(p);   //在容器头部添加元素 vector不支持
    v.push_back(p);   //在容器尾部添加元素 forward_list不支持
    v.emplace_back("Summer",26);   //采用构造函数的方法在容器尾部添加元素
    v.insert(v.begin(),p);  //在指定位置（v的首元素）之前插入元素，vector不推荐在除尾部以外的位置插入元素
    v.insert(v.begin(),l.begin(),l.end()); //在指定位置之前（v的首元素）之前插入l的所有元素
    v.insert(v.begin(),v.begin(),v.end());  //错误，迭代器表示拷贝范围，不能指向与目标相同的容器
 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意：使用一个对象来初始化容器或将一个对象插入到容器时，实际上放入容器中的是对象值的一个拷贝，而不是对象本身。容器中的元素与提供值得对象之间没有任何关联！

访问元素

访问容器中的元素的主要方法：解引迭代器，调用front,back函数，使用下标。

    vector<int> v(10,0);
 
    // 以下4种写法都是访问v首元素
    auto p1 = *v.begin();
    auto p2 = v.front();
    auto p3 = v[0];
    auto p4 = v.at(0);
1
2
3
4
5
6
7

注意：如果容器为空，调用front,back函数会发生严重错误。在使用下标时需要保证给定下标在有效范围内，防止发生越界。在容器中访问成员函数返回的都是引用，如果容器是一个const对象，则返回值是const引用。如果容器不是const，则可以用返回值来改变元素的值。

删除元素

    list<int> l(10,0);
    vector<int> v(10,0);
 
    l.pop_front();  // 删除首元素，vector不支持
    v.pop_back();  //删除尾元素，forward_list不支持
    v.erase(v.begin);  // 删除指定位置的元素，返回指向被删元素之后的迭代器
    v.erase(v.begin,v.end); // 删除指定区域内的元素，返回指向最后一个被删元素之后的迭代器，这里等价于v.clear()
    v.clear(); // 删除所有元素
1
2
3
4
5
6
7
8

注意：删除元素的函数都不会检查其参数，所以在删除元素之前，必须保证被删元素确实存在。

改变容器大小

改变容器大小时，如果容器缩小，容器后部的元素会被删除，如果容器增大，会在容器后部添加新元素。

    vector<int> v(10,1);
 
    v.resize(15); //将5个值为0的元素添加到vector末尾
    v.resize(20,-1); //将5个值为-1的元素添加到vector末尾
    v.resize(5); //从vector末尾删除15个元素
1
2
3
4
5

迭代器失效

向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针，引用或迭代器失效。使用失效的指针，引用或迭代器是一种严重错误。当使用迭代器时，最好保证在每次改变容器的操作之后都正确地重新定位迭代器。
注意：end返回的迭代器很容易失效，不要保存end返回的迭代器。

vector对象的增长

int main(int argc, const char * argv[]) {
    vector<int> v(50,1);
 
    v.reserve(60);  //为v分配能容纳60个元素的内存空间
    cout << v.size() << endl;  //v的大小为50
    cout << v.capacity() << endl;  //v的容量为60
 
    v.shrink_to_fit();  //将v的容量减小到与大小相当
    cout << v.size() << endl;  //v的大小为50
    cout << v.capacity() << endl;  //v的容量为50
 
    v.push_back(1);  //新增一个元素，v的容量已满，系统为v重新分配内存空间
    cout << v.size() << endl;  //v的大小为51
    cout << v.capacity() << endl;  //v的容量为100，系统自动为v重新分配的内存空间为原来的2倍
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在有些编程环境下运行最后一条语句，输出的v的容量也有可能是75，即系统自动为v重新分配的内存空间为原来的1.5倍。

string 操作

string除了支持顺序容器的通用操作外，还支持一些其他的操作。

改变string

    string s = "Summer love C++";
    s = s.substr(0,11);  // 从下标为0的位置开始的11个字符，s = "Summer love"
    s = s.append(" Swift"); // 在尾部添加" Swift"，s = "Summer love Swift"
    s = s.replace(12, 5, "Objective-C"); // 将从下标为12位置开始的5个字符替换为"Objective-C"，s = "Summer love Objective-C"
1
2
3
4

注意：substr和replace函数的开始位置不能超出string的长度，操作长度最大值为string长度与开始位置之差。

搜索string

    string s = "Summer love C++";
    auto pos = s.find("love");  //pos为7，查找"love"第一次出现的位置
    pos = s.find_first_of("love");  //pos为4，查找任何"love"中的字符第一次出现的位置
    pos = s.find_first_of("love",6);  //pos为7，从位置6开始查找任何"love"中的字符第一次出现的位置
    pos = s.find_first_not_of("love");  //pos为0，查找任何非"love"中的字符第一次出现的位置
    pos = s.find_last_of("love");  //pos为10，查找任何"love"中的字符最后一次出现的位置
1
2
3
4
5
6

注意：搜索对大小写敏感！

数值转换

    float pi = 3.14;
    string s = to_string(pi); //数值转化为字符串
 
    int i = stoi(s);  //字符串转化整数
    long l = stol(s);  //字符串转化长整数
    unsigned long ul = stoul(s);  //字符串转化无符号长整数
    float f = stof(s);  //字符串转化浮点数
    double d = stod(s)  //字符串转化无符号浮点数
1
2
3
4
5
6
7
8

容器适配器

除了顺序容器外，标准库还定义了3个顺序容器适配器:stack,queue和priority_queue。适配器可以接受一种已有的容器类型，使其行为看起来像一种不同的类型。所有适配器都要求容器具有添加，删除元素和访问尾元素的能力。所以array和forward_list无法用来构造适配器。

栈stack

stack只需要实现添加，删除，访问尾元素操作，所以可以用vector，list，deque来构造，默认情况下stack是基于deque构造的。

    deque<int> d;
    vector<int> v；
 
    stack<int> s1(d); //基于deque构造栈，默认情况
    stack<int,vector<int>> s2(v); //基于vector构造栈，需要在第二个参数传入容器类型
    stack<int> s3;  //不用顺序容器，直接构造栈
1
2
3
4
5
6
7

栈的基本操作

    vector<int> v = {1,2,3,4,5};
    stack<int,vector<int>> s(v); // 用vector构造栈
    s.push(6); // 将一个新元素压入栈顶
    int i = s.top();  //返回栈顶元素 i=6
    s.pop();  //删除栈顶元素（出栈）
    i = s.top();  //返回栈顶元素 i=5
1
2
3
4
5
6

队列queue

queue需要实现添加尾元素，删除首元素，访问首尾元素操作，所以只能用list，deque来构造，默认情况下queue是基于deque构造的。

    deque<int> d;
    list<int> l;
 
    queue<int> q1(d); //基于deque构造队列，默认情况
    queue<int,list<int>> q2(l);  //基于list构造栈，需要在第二个参数传入容器类型
    queue<int> q3; //不用顺序容器，直接构造队列
1
2
3
4
5
6

队列的基本操作

    list<int> l = {1,2,3,4,5};
    queue<int,list<int>> q(l); // 用list构造队列
 
    int front = q.front(); //返回队首元素，front=1
    q.pop();  //删除队首元素（出队）
    front = q.front(); //返回队首元素，front=2
 
    int back = q.back();  //返回队尾元素，front=5
    q.push(6);  //将6添加到队尾（入队）
    back = q.back();  //返回队尾元素，front=6
1
2
3
4
5
6
7
8
9
10

priority_queue与queue的区别在于priority_queue，需要实现的是队尾元素的添加删除和随机访问，所以只能用vector和deque进行构造，默认情况是用vector构造priority_queue。且priority_queue的元素是按优先级排序的（queue是按入队顺序），可用q.top()返回优先级最高的元素。