C/C++ | 每日一练 (4)

news/2025/2/26 5:25:32

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

文章目录

  • C/C++ | 每日一练 (4)
    • 题目
    • 参考答案
      • 基础容器
        • 序列容器
          • `std::array`
          • `std::vector`
          • `std::deque`
          • `std::list`
          • `std::forward_list`
        • 关联容器
          • 有序关联容器
            • `std::set`
            • `std::map`
            • `std::multiset`
            • `std::multimap`
          • 无序关联容器
            • `std::unordered_set`
            • `std::unordered_map`
            • `std::unordered_multiset`
            • `std::unordered_multimap`
      • 容器适配器
        • `std::stack`
        • `std::queue`
        • `std::priority_queue`

C/C++ | 每日一练 (4)

题目

c++ 中 STL 常见容器有哪些？简述一下底层实现的原理。

参考答案

在 c++ 中根据容器的特点和结构分为如下两大类：

  • 基础容器
  • 容器适配器

下面基于以上列举的两大类型进行一一总结。

基础容器

在 c++ 标准库中，基础容器是构建其他容器（如容器适配器）的底层实现，它们提供了丰富的数据存储和管理功能。

基础容器主要分为两大类：序列容器和关联容器。

序列容器

序列容器用于存储线性排列的元素，支持随机访问或顺序访问。它们的特点是元素的顺序由插入顺序决定。

c++ 标准库中提供的序列容器有：std::array、std::vector、std::deque、std::list、std::forward_list。

std::array

c++11 引入的固定大小的序列容器，底层是静态数组。它的大小在编译时确定，因此不支持动态大小。

例如：

#include <iostream>
#include <array>

int main()
{
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 访问元素
    std::cout << arr[2] << std::endl; // 3

    // 修改元素
    arr[2] = 10;
    std::cout << arr[2] << std::endl; // 10

    // 因为 array 是固定大小的容器，不能动态增加、删除元素

    // 遍历
    for (int i : arr)
    {
        std::cout << i << " "; // 1 2 10 4 5
    }
    std::cout << std::endl;

    return 0;
}
std::vector

底层是基于动态数组实现，支持随机访问。它在内存中分配一块连续的空间来存储元素，当容器中的元素数量超过当前分配的空间时，会触发扩容机制，扩容因子根据不同的标准库实现有不同的大小，目前是存在1.5倍和2倍的大小。

例如：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 访问元素
    std::cout << vec[2] << std::endl; // 3

    // 修改元素
    vec[2] = 10;
    std::cout << vec[2] << std::endl; // 10

    // 在末尾添加元素
    vec.push_back(6);
    std::cout << vec.back() << std::endl; // 6

    // 删除最后一个元素
    vec.pop_back();
    std::cout << vec.size() << std::endl; // 5

    // 遍历
    for (int i : vec)
    {
        std::cout << i << " "; // 1 2 10 4 5
    }
    std::cout << std::endl;

    return 0;
}
std::deque

std::deque的底层结构可以看作是一个指针数组，其中每个指针指向一个固定大小的缓冲区（称为块）。这些块组成了整个 std::deque的数据存储。通过这种结构，std::deque可以在头尾进行高效的插入和删除操作，同时也能提供快速的随机访问。

  • 指针数组：std::deque 使用一个数组来存储指向各个数据块（缓冲区）的指针。这个指针数组是连续的，即指针存储在一个连续的数组中。
  • 数据块（缓冲区）：每个指针指向一个固定大小的缓冲区，这些缓冲区用于实际存储数据。缓冲区中的数据是连续存储的，但是缓冲区之间在内存中可能不是连续的。其中每个数据块大小是 4096 / sizeof(T)(其中 T是存储的类型)

例如：

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> dq = {1, 2, 3, 4, 5};

    // 访问元素
    std::cout << dq[2] << std::endl; // 3

    // 修改元素
    dq[2] = 10;
    std::cout << dq[2] << std::endl; // 10

    // 在头部和尾部添加元素
    dq.push_front(0);
    dq.push_back(6);
    std::cout << dq.front() << " and " << dq.back() << std::endl; // 0 and 6

    // 删除头部和尾部元素
    dq.pop_front();
    dq.pop_back();
    std::cout << dq.size() << std::endl; // 5

    // 遍历
    for (int i : dq)
    {
        std::cout << i << " "; // 1 2 10 4 5
    }
    std::cout << std::endl;

    return 0;
}
std::list

双向链表，每个元素包含一个数据域和两个指针（分别指向前后元素）。它不依赖连续的内存空间。std::list 的大小可以动态增加或减少，允许在常数时间内插入或删除元素（只需调整指针）。另外 std::list 不支持随机访问，访问元素时需要从链表头或尾开始遍历。

例如：

#include <iostream>
#include <list>

int main()
{
    std::list<int> lst = {1, 2, 3, 4, 5};

    // 访问第一个元素
    std::cout << lst.front() << std::endl; // 1

    // 修改第一个元素
    lst.front() = 10;
    std::cout << lst.front() << std::endl; // 10

    // 在头部和尾部添加元素
    lst.push_front(0);
    lst.push_back(6);
    std::cout << lst.front() << " and " << lst.back() << std::endl; // 0 and 6

    // 删除第一个和最后一个元素
    lst.pop_front();
    lst.pop_back();
    std::cout << lst.size() << std::endl; // 5

    // 遍历
    for (int i : lst)
    {
        std::cout << i << " "; // 10 2 3 4 5
    }
    std::cout << std::endl;

    return 0;
}
std::forward_list

单向链表，每个元素只包含一个数据域和一个指针（指向后元素），只能单向遍历。与 std::list 一样不依赖于连续的内存空间，可以在常数时间内操作元素（调整指针），也同样不支持随机访问，访问元素时需要从链表头或尾开始遍历。

例如：

#include <iostream>
#include <forward_list>

int main()
{
    std::forward_list<int> flst = {1, 2, 3, 4, 5};

    // 访问第一个元素
    std::cout << flst.front() << std::endl; // 1

    // 修改第一个元素
    flst.front() = 10;
    std::cout << flst.front() << std::endl; // 10

    // 在头部添加元素
    flst.push_front(0);
    std::cout << flst.front() << std::endl; // 0

    // 删除第一个元素
    flst.pop_front();
    std::cout << flst.front() << std::endl; // 10

    // 遍历
    for (int i : flst)
    {
        std::cout << i << " "; // 10 2 3 4 5
    }
    std::cout << std::endl;

    return 0;
}
关联容器

在 c++ 标准库中，关联容器是一类特殊的容器，用于存储键值对，并根据键的值自动组织数据。

c++ 标准库提供了两种主要的关联容器类型，如下所示：

  • 有序关联容器：std::set、std::map、std::multiset、std::multimap。
  • 无序关联容器：std::unordered_set、std::unordered_map、std::unordered_multiset、std::unordered_multimap。
有序关联容器
std::set

存储唯一的键，所有元素按照键的顺序自动排序。std::set 底层使用红黑树实现，因此具有高效的插入、删除和查找操作。

例如：

#include <iostream>
#include <set>

int main()
{
    std::set<int> mySet;

    // 增：插入元素
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);
    mySet.insert(20); // 重复元素不会插入

    // 查找元素
    auto it = mySet.find(20);
    if (it != mySet.end())
    {
        std::cout << *it << std::endl; // 20
    }
    else
    {
        std::cout << "Not found!" << std::endl;
    }

    // set 的键值不可直接修改，需要删除后重新插入
    mySet.erase(it);  // 删除元素
    mySet.insert(25); // 插入新值

    // 删除元素
    mySet.erase(30);

    // 遍历
    for (const auto &value : mySet)
    {
        std::cout << value << " "; // 10 25
    }
    std::cout << std::endl;

    return 0;
}
std::map

以键值对的形式存储数据，键唯一，并且所有元素都按键的顺序自动排序。std::map 底层使用红黑树实现，因此具有高效的插入、删除和查找操作。

例如：

#include <iostream>
#include <map>

int main()
{
    std::map<int, std::string> myMap;

    // 插入键值对
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    // 通过键访问值
    std::cout << myMap[2] << std::endl; // two

    // 修改键对应的值
    myMap[2] = "TWO";
    std::cout << myMap[2] << std::endl; // TWO

    // 删除键值对
    myMap.erase(3);

    // 遍历

    // 1: one
    // 2: TWO
    
    // for (const auto &[key, value] : myMap)
    // {
    //     std::cout << key << ": " << value << std::endl;
    // }

    for (const auto &it : myMap)
    {
        std::cout << it.first << ": " << it.second << std::endl;
    }

    return 0;
}
std::multiset

用于存储多个键，允许重复元素，并且所有元素按照键的顺序自动排序。std::multiset 使用红黑树实现，因此具有高效的插入、删除和查找操作。

例如：

#include <iostream>
#include <set>

int main()
{
    std::multiset<int> myMultiSet;

    // 插入元素
    myMultiSet.insert(10);
    myMultiSet.insert(20);
    myMultiSet.insert(20);
    myMultiSet.insert(30);

    // 查找元素
    auto it = myMultiSet.find(20);
    if (it != myMultiSet.end())
    {
        std::cout << *it << std::endl; // 20
    }
    else
    {
        std::cout << "Not found!" << std::endl;
    }

    // multiset 的键值不可直接修改，需要删除后重新插入
    myMultiSet.erase(it);  // 删除一个元素
    myMultiSet.insert(25); // 插入新值

    // 删除所有值为20的元素
    myMultiSet.erase(20);

    // 遍历
    for (const auto &value : myMultiSet)
    {
        std::cout << value << " "; // 10 25 30
    }
    std::cout << std::endl;

    return 0;
}
std::multimap

以键值对的形式存储数据，允许重复元素，并且所有元素都按键的顺序自动排序。std::multimap 底层使用红黑树实现，因此具有高效的插入、删除和查找操作。

例如：

#include <iostream>
#include <map>

int main()
{
    std::multimap<int, std::string> myMultiMap;

    // 插入键值对
    myMultiMap.insert({1, "one"});
    myMultiMap.insert({2, "two"});
    myMultiMap.insert({2, "TWO"});
    myMultiMap.insert({3, "three"});

    // 查找键对应的值（可能有多个）
    auto range = myMultiMap.equal_range(2);
    for (auto it = range.first; it != range.second; ++it)
    {
        // two
        // TWO
        std::cout << it->second << std::endl;
    }

    // 修改某个键值对的值
    auto it = myMultiMap.find(2);
    if (it != myMultiMap.end())
    {
        it->second = "TWO MODIFIED";
    }

    // 删除某个键值对
    myMultiMap.erase(it);

    // 遍历
    // 1: one
    // 2: TWO
    // 3: three
    
    // for (const auto &[key, value] : myMultiMap)
    // {
    //     std::cout << key << ": " << value << std::endl;
    // }

    for (const auto &it : myMultiMap)
    {
        std::cout << it.first << ": " << it.second << std::endl;
    }

    return 0;
}
无序关联容器
std::unordered_set

用于存储唯一的键，所有元素不按特定顺序排序。std::unordered_set 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。

例如：

#include <iostream>
#include <unordered_set>

int main()
{
    std::unordered_set<int> us;

    // 插入元素
    us.insert(1);
    us.insert(2);
    us.insert(3);

    // 查找元素
    auto it = us.find(2);
    if (it != us.end())
    {
        std::cout << *it << std::endl; // 2
    }
    else
    {
        std::cout << "Not found!" << std::endl;
    }

    // unordered_set 不支持直接修改键，只能删除后重新插入
    us.erase(it);
    us.insert(25);

    // 删除
    us.erase(1);

    // 遍历
    for (const auto &elem : us)
    {
        std::cout << elem << " "; // 25 3
    }
    std::cout << std::endl;

    return 0;
}
std::unordered_map

以键值对的形式存储数据，键唯一，并且所有元素都不按特定顺序排序。std::unordered_map 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。

例如：

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

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

    // 插入键值对
    um[1] = "one";
    um[2] = "two";
    um[3] = "three";

    // 通过键访问值
    std::cout << um[2] << std::endl; // two

    // 修改键对应的值
    um[2] = "TWO";
    std::cout << um[2] << std::endl; // TWO

    // 删除键值对
    um.erase(3);

    // 遍历
    for (const auto &pair : um)
    {
        // 2: TWO
        // 1: one
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}
std::unordered_multiset

用于存储键，允许相同的元素出现多次，所有元素不按特定顺序排序。std::unordered_multiset 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。

例如：

#include <iostream>
#include <unordered_set>

int main()
{
    std::unordered_multiset<int> ums;

    // 插入元素
    ums.insert(1);
    ums.insert(2);
    ums.insert(2);
    ums.insert(3);

    // 查找元素
    auto range = ums.equal_range(2);
    std::cout << std::distance(range.first, range.second) << std::endl; // 2

    // unordered_multiset 不支持直接修改键，只能删除后重新插入
    ums.erase(1);
    ums.insert(10);

    // 删除所有值为2的元素
    ums.erase(2);

    // 遍历
    for (const auto &elem : ums)
    {
        std::cout << elem << " "; // 10 3
    }
    std::cout << std::endl;

    return 0;
}
std::unordered_multimap

以键值对的形式存储数据，允许相同的键值出现多次，每个键可以对应多个值（键值对），并且所有元素都不按特定顺序排序。std::unordered_multimap 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。

例如：

#include <iostream>
#include <unordered_map>

int main()
{
    std::unordered_multimap<int, std::string> umm;

    // 插入键值对
    umm.insert({1, "one"});
    umm.insert({2, "two"});
    umm.insert({2, "TWO"});
    umm.insert({3, "three"});

    // 查找键对应的值（可能有多个）
    auto range = umm.equal_range(2);
    std::cout << distance(range.first, range.second) << std::endl; // 2
    for (auto it = range.first; it != range.second; ++it)
    {
        std::cout << it->second << " "; // TWO two
    }
    std::cout << std::endl;

    // 修改某个键值对的值
    auto it = umm.find(2);
    if (it != umm.end())
    {
        it->second = "TWO_UPDATED";
    }

    // 删除某个键值对
    umm.erase(3);

    // 遍历
    for (const auto &pair : umm)
    {
        // 2: TWO_UPDATED
        // 2: two
        // 1: one
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

容器适配器

容器适配器是一种特殊的容器，它们基于标准容器（如std::vector、std::deque、std::list等），通过封装和限制其接口来提供特定的抽象数据类型。容器适配器并不直接存储数据，而是通过底层容器来数据存储，并且只暴露部分功能，以满足特定的使用场景。

c++ 标准库中提供了三个容器适配器：std::stack、std::queue、std::priority_queue。

std::stack

后进先出（LIFO）的数据结构，支持在栈顶插入和删除元素。默认基于 std::deque 实现，可以使用 std::vector 或 std::list 作为底层容器。

template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack { 
	//...
}

例如：

#include <iostream>
#include <stack>
#include <vector>
#include <list>

int main()
{
    std::stack<int> s;

    // 使用 std::vector
    // std::stack<int, std::vector<int>> s1;
    
    // 使用 std::list
    // std::stack<int, std::list<int>> s2;

    // 插入元素
    s.push(1);
    s.push(2);
    s.push(3);

    // 查询栈顶元素
    std::cout << s.top() << std::endl; // 3

    // 弹出栈顶元素
    s.pop();
    std::cout << s.top() << std::endl; // 输出新栈顶元素的值    2

    // 判断栈是否为空
    if (!s.empty())
    {
        std::cout << "stack is not empty" << std::endl; // stack is not empty
    }

    // 获取栈的大小
    std::cout << s.size() << std::endl; // 2

    return 0;
}
std::queue

先进先出（FIFO）的数据结构，支持在队尾插入元素，在队头删除元素。默认基于 std::deque 实现，可以使用 std::list 作为底层容器。

template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue
{
    // ...
}

需要注意的是：std::vector 是一个动态数组，支持快速的尾部插入和删除操作（push_back 和 pop_back），但不支持高效的头部删除操作（pop_front）。因此， std::vector 无法作为 std::queue 的底层容器。

例如：

#include <iostream>
#include <queue>
#include <list>

int main()
{
    std::queue<int> q;

    // 使用 std::list
    // std::queue<int, std::list<int>> q1;

    // 元素入队
    q.push(1);
    q.push(2);
    q.push(3);

    // 输出队头元素
    std::cout << q.front() << std::endl; // 1

    // 输出队尾元素
    std::cout << q.back() << std::endl; // 3

    // 元素出队
    q.pop();
    std::cout << q.front() << std::endl; // 2

    // 判断队列是否为空
    if (!q.empty())
    {
        std::cout << "queue is not empty" << std::endl; // queue is not empty
    }

    // 获取队列的大小
    std::cout << "queue size: " << q.size() << std::endl; // queue size: 2

    return 0;
}
std::priority_queue

优先队列，元素会按照优先级顺序排（默认是大顶堆，如果需要小顶堆，则需要自定义比较器）。默认基于 std::vector 作为底层容器，可以使用 std::deque 作为底层容器。

template<typename _Tp, typename _Sequence = vector<_Tp>,
   typename _Compare  = less<typename _Sequence::value_type> >
class priority_queue
{
    // ...
}

需要注意的是：std::list 只支持双向迭代器，不支持随机访问。而优先队列需要上浮和下沉操作（需要随机访问的支持），所以 std::list 无法作为 std::priority_queue 的底层容器。

例如：

#include <iostream>
#include <queue>
#include <deque>

int main()
{
    std::priority_queue<int> pq;
    // std::priority_queue<int, std::deque<int>> pq;

    // 堆中插入元素
    pq.push(1);
    pq.push(3);
    pq.push(2);

    // 查询堆顶元素
    std::cout << pq.top() << std::endl; // 3

    // 删除堆顶元素
    pq.pop();
    std::cout << pq.top() << std::endl; // 2

    // 判断堆是否为空
    if (!pq.empty())
    {
        // priority queue is not empty
        std::cout << "priority queue is not empty" << std::endl; 
    }

    // 获取优先队列的大小
    // priority queue size: 2
    std::cout << "priority queue size: " << pq.size() << std::endl; 

    return 0;
}

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。

在这里插入图片描述


http://www.niftyadmin.cn/n/5868038.html

相关文章

Linux中常见命令使用

Linux中常见命令使用

Linux命令&#xff0c;本质是一个二进制可执行程序&#xff0c;与Windows系统中的.exe文件是一个意思 ls -l -l看到的信息&#xff0c;开始是d&#xff0c;说明是文件夹&#xff0c;开始是-&#xff0c;则是文件w -h让文件大小更人性化的显示 文件操作命令 touch 创建文件…
阅读更多...
将DeepSeek接入vscode的N种方法

将DeepSeek接入vscode的N种方法

接入deepseek方法一：cline 步骤1：安装 Visual Studio Code 后，左侧导航栏上点击扩展。 步骤2：搜索 cline，找到插件后点击安装。 步骤3：在大模型下拉菜单中找到deep seek，然后下面的输入框输入你在deepseek申请的api key，就可以用了 让deepseek给我写了一首关于天气的…
阅读更多...
音乐游戏Drummania(GITADORA)模拟器

音乐游戏Drummania(GITADORA)模拟器

文章目录 &#xff08;一&#xff09;Drummania和GITADORA&#xff08;1.1&#xff09;基本情况&#xff08;1.2&#xff09;机体 &#xff08;二&#xff09;模拟器&#xff08;2.1&#xff09;主程序&#xff08;2.2&#xff09;模拟器主题 &#xff08;三&#xff09;曲谱文…
阅读更多...
AIoT是什么？关键技术及应用

AIoT是什么？关键技术及应用

一.AIoT定义 AIoT 概念是在 2017 年正式向公开市场提出的。2017 年 11 月 28 日&#xff0c;在由光际资本、36 氪、特斯联联合主办的 “万物智能.新纪元 AIoT 未来峰会” 上&#xff0c;与会专家及行业嘉宾首次正式向公开市场提出 AIoT 概念。AIoT 即人工智能物联网&#xff0c…
阅读更多...
网页五子棋——项目部署

网页五子棋——项目部署

目录 安装 openjdk 安装 MySQL 创建数据库和数据表 修改 WebSocket 建立连接的 url 上传项目 在项目实现完成后&#xff0c;我们就可以将项目部署到云服务器上&#xff08;在这里使用的是 Ubuntu&#xff09; 我们先在服务器上安装 jdk、mysql 等 更新软件包&#xff…
阅读更多...
Go小技巧易错点100例（二十三）

Go小技巧易错点100例（二十三）

本期分享&#xff1a; 1.Go Module控制Go版本 2.int转string注意事项 3.Go项目查看mod依赖关系 Go Module控制Go版本 当我们开发Go项目涉及到两台及以上的机器&#xff0c;而且它们又刚好是不同操作系统的时候&#xff0c;可能就要把代码挪到另一台机器上重新编译&#xff…
阅读更多...
六十天前端强化训练之第二天CSS选择器与盒模型深度解析

六十天前端强化训练之第二天CSS选择器与盒模型深度解析

欢迎来到编程星辰海的博客讲解 目录 一、CSS 核心概念 1. 三种引入方式 2. CSS 注释 3. 常见单位系统 二、CSS选择器核心知识 1. 基础选择器类型 2. 组合选择器 3. 伪类选择器&#xff08;部分示例&#xff09; 4. 优先级计算规则 三、盒模型深度解析 1. 标准盒模型图…
阅读更多...
JavaWeb-GenericServlet源码分析(适配器/模板方法)

JavaWeb-GenericServlet源码分析(适配器/模板方法)

文章目录 类直接实现Servlet接口的弊端Servlet接口的方法适配器设计模式 适配器对象的改造关于init方法的ServletConfig对象来源使用模板方法设计模式改造init方法 GenericServlet内置抽象类ServletConfig接口ServletConfig接口简介测试再谈GenericServlet抽象类 类直接实现Ser…
阅读更多...
最新文章

Copyright @ 2022~2023