C++STL

ryluo 2020-06-19 12:35:49

C++刷题STL常用数据结构

  1. 顺序容器
    • vector, list, deque
  2. 关联容器
    • map, set, multimap, multiset
  3. 容器适配器
    • stack, queue, priority_queue

vector

#include <iostream>
#include <vector>

using namespace std;

void printVec(vector<int>& vec)
{
    for (int i = 0; i < vec.size(); i++) cout << vec[i] << " ";
    cout << endl;
}

int main()
{
    vector<int> vec;
    // 判断vector是否为空
    cout << "判断vector是否为空" << endl;
    cout << vec.empty() << endl;

    // 不断地往vector最后一个位置写入元素
    cout << "不断地往vector最后一个位置写入元素" << endl;
    for (int i = 0; i < 10; i++)
    {
        vec.push_back(i);
    }

    // 利用vector地大小遍历vector
    cout << "遍历vector" << endl;
    for (int i = 0; i < vec.size(); i++) cout << vec[i] << " ";
    cout << endl;

    // 使用insert在vector的末尾插入5个3
    // vec.insert(0, 5, 0); // 插入的位置参数应该是一个迭代器,直接使用一个位置会报错
    // 可以通过一个vec的首地址的迭代器加上一个整数偏移得到指定的位置
    // 当然也可所以使用末尾的迭代器减去一个数到达指定的位置
    cout << "从vector的末尾插入5个7元素" << endl;
    vec.insert(vec.end(), 5, 7);    //
    printVec(vec);

    // 在vector的3号(也就是vec中的第四个位置)位置插入1个100
    cout << "在vector的3号(也就是vec中的第四个位置)位置插入1个100" << endl;
    auto it = vec.begin(); // 使用auto进行类型推理
    vec.insert(it + 3, 1, 100);
    printVec(vec);

    // 删除最后一个元素 pop_back
    cout << "删除最后一个元素" << endl;
    vec.pop_back();
    printVec(vec);

    // 删除编号为5-7中的值
    // 注意这里的区间是左闭右开的
    cout << "删除编号为5-7中的值" << endl;
    vec.erase(vec.begin()+ 5, vec.begin() + 8); 
    printVec(vec);

    system("pause");
    return 0;
}

输出结果:

判断vector是否为空
1
不断地往vector最后一个位置写入元素
遍历vector
0 1 2 3 4 5 6 7 8 9
从vector的末尾插入5个7元素
0 1 2 3 4 5 6 7 8 9 7 7 7 7 7
在vector的3号(也就是vec中的第四个位置)位置插入1个100
0 1 2 100 3 4 5 6 7 8 9 7 7 7 7 7
删除最后一个元素
0 1 2 100 3 4 5 6 7 8 9 7 7 7 7
删除编号为5-7中的值
0 1 2 100 3 7 8 9 7 7 7 7
请按任意键继续. . .

vector二维数组:

#include <iostream>
#include <vector>

using namespace std;


int main()
{
    vector<vector<int>> array(3);

    int a = 0;
    for (int i = 0; i < array.size(); i++) {
        array[i].resize(5);
    }

    for (int i = 0; i < array.size(); i++) {
        for (int j = 0; j < array[0].size(); j++)
            array[i][j] = a++;
    }

    cout << "矩阵的行数为:" << array.size() << endl;
    cout << "矩阵的列数为:" << array[0].size() << endl;

    cout << "矩阵的第一行数据为:" << endl;
    for (int i = 0; i < array[0].size(); i++) cout << array[0][i] << " ";

    system("pause");
    return 0;
}

输出:

矩阵的行数为:3
矩阵的列数为:5
矩阵的第一行数据为:
0 1 2 3 4 请按任意键继续. . .

map

map的底层原理是通过红黑树来实现的,也就是说map内部的所有数据都是有序的(通过Key进行了排序),map的查询、插入删除操作都是O(logn)的。

#include <iostream>
#include <map>

using namespace std;

int main()
{
    // 定义一个map类型,相当于一个字典
    map<string, int> dict;

    dict.insert(pair<string, int>("apple", 2));
    dict.insert(map<string, int>::value_type("origin", 3));
    dict["banana"] = 6; // 这种方法使用起来比较简单

    // 判断是否有元素
    if (dict.empty())
        cout << "该字典没有元素" << endl;
    else
        cout << "该字典有" << dict.size() << "个元素" << endl;

    // 遍历字典
    map<string, int>::iterator iter;  // 定义一个迭代器
    for (iter = dict.begin(); iter != dict.end(); iter++)
        cout << iter->first << ends << iter->second << endl;

    // 查找
    if ((iter = dict.find("banana")) != dict.end())
        cout << "找到banana其值为:" << iter->second << endl;
    else
        cout << "未找到banana" << endl;

    // 查找
    if ((iter = dict.find("watermelon")) != dict.end())
        cout << "找到watermelon其值为:" << iter->second << endl;
    else
        cout << "未找到watermelon" << endl;

    system("pause");
    return 0;
}

unordered map

unordered map的底层是一个防冗余的hash表(开链法,避免地址冲突),但是unordered map中的key不会按照大小进行排序。把数据的存储和查询复杂度降到O(1)。

需要注意的是虽然hash表的查询复杂度是O(1),并不是说unordered map查询时间一定比map短,还需要考虑数据量的大小。

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<string, int> dict;

    dict.insert(pair<string, int>("apple", 1));
    dict.insert(unordered_map<string, int>::value_type("banana", 2));
    dict["origin"] = 3; // 这种方式比较方便

    // 判断是否为空
    if (dict.empty())
        cout << "字典为空" << endl;
    else
        cout << "字典中元素个数为:" << dict.size() <<endl;

    // 遍历
    unordered_map<string, int>::iterator iter;
    for (iter = dict.begin(); iter != dict.end(); iter++)
        cout << iter->first << iter->second << endl;

    // 查找
    if ((iter = dict.find("apple")) != dict.end())
        cout << "找到了apple其值为:" << iter->second << endl;
    else
        cout << "未找到apple" << endl;

    if ((iter = dict.find("water")) != dict.end())
        cout << "找到了water其值为" << iter->second << endl;
    else
        cout << "未找到water" << endl;

    // 使用count进行查找,这个只能判断里面是否有,但是不能得到对应的值
    if (dict.count("app") == 0)
        cout << "未找到app" << endl;
    else
        cout << "找到了app" << endl;

    system("pause");
    return 0;
}

stack

先进后出

img

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main()
{
    stack<int> my_stack;

    // 入栈
    my_stack.push(1);
    my_stack.push(2);
    my_stack.push(3);
    my_stack.push(4);

    // 出栈
    cout << "删除栈顶元素" << endl;
    my_stack.pop();

    // 访问栈顶元素
    cout << "此时的栈顶元素为:" << my_stack.top() << endl;

    // 判断栈为空
    if (my_stack.empty())
        cout << "此时栈为空" << endl;
    else
        cout << "栈不为空,元素的数量为:" << my_stack.size() << endl;  // 栈中元素个数

    system("pause");
    return 0;
}

queue

先进先出

img

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main()
{
    queue<int> my_queue;

    // 入栈
    my_queue.push(1);
    my_queue.push(2);
    my_queue.push(3);
    my_queue.push(4);

    // 出栈
    cout << "弹出队列的第一个元素" << endl;
    my_queue.pop();

    // 访问队首元素
    cout << "访问队首元素:" << my_queue.front() << endl;

    // 访问队尾元素
    cout << "访问队尾元素" << my_queue.back() << endl;

    // 判断队列是否为空
    if (my_queue.empty())
        cout << "此时队列为空" << endl;
    else
        cout << "队列不为空,元素的数量为:" << my_queue.size() << endl;  // 队列元素个数

    system("pause");
    return 0;
}

注意点:队列既可以访问首元素front()也可以访问队尾元素back()