底层
,
Source
Edit
History

常用容器的底层原理

C++

STL（Standard Template Library）中包含多种容器，每种容器都有其特定的底层实现。以下是几种常见的STL容器以及它们的底层实现方式：

  1. 数组容器（array）：

    • 底层实现：std::array 是一个固定大小的数组容器，底层实现使用静态数组来存储元素，因此具有数组的特性，如随机访问和连续存储空间。

  2. 动态数组容器（vector）：

    • 底层实现：std::vector 是一个动态数组容器，底层实现使用动态分配的数组来存储元素。当元素数量超过当前容量时，会重新分配更大的内存空间，并将原有元素拷贝到新的内存空间中。

  3. 链表容器（list）：

    • 底层实现：std::list 是一个双向链表容器，底层实现使用双向链表来存储元素。每个节点包含指向前一个节点和后一个节点的指针。

  4. 双端队列容器（deque）：

    • 底层实现：std::deque 是一个双端队列容器，底层实现通常使用多个固定大小的数组块来存储元素，每个数组块称为一个缓冲区。当需要在两端插入或删除元素时，可以在头部或尾部的缓冲区进行操作。

  5. 栈容器（stack） 和 队列容器（queue）：

    • 底层实现：std::stack 和 std::queue 分别是栈和队列容器的适配器，它们的底层实现通常基于其他容器，如 std::deque 或 std::list。栈通常使用 std::deque 作为底层容器，而队列通常使用 std::deque 或 std::list。

  6. 映射容器（map） 和 集合容器（set）：

    • 底层实现：std::map 和 std::set 是基于红黑树实现的关联容器。红黑树是一种自平衡的二叉搜索树，具有良好的平衡性能，保证了插入、删除和查找操作的时间复杂度都是 O(log n)。

以上是一些常见的STL容器及其底层实现方式的简要介绍。不同的容器在不同的场景下具有不同的性能特点和适用性，应根据实际需求选择合适的容器。

C#

在 C# 中，常用的容器包括数组、列表（List）、字典（Dictionary）、队列（Queue）和栈（Stack）等。这些容器在 .NET Framework 中都有其特定的底层实现方式。以下是其中一些常见容器的底层实现方式：

  1. 数组：

    • 底层实现：数组是 C# 中的基本数据结构，底层实现直接使用内存中的连续存储空间来存储元素。数组的长度在创建时确定，且无法改变。

  2. **列表（List<T>) ** ：

    • 底层实现：列表使用动态数组来存储元素，底层实现使用数组作为存储元素的载体。当列表需要扩展容量时，会重新分配更大的数组，并将原有元素拷贝到新的数组中。

  3. 字典（Dictionary<TKey, TValue>）：

    • 底层实现：字典使用哈希表（hash table）来存储键值对。哈希表是一种基于数组的数据结构，通过哈希函数将键映射到数组的索引位置，并在该位置存储对应的值。哈希表具有良好的查找性能，查找、插入和删除操作的时间复杂度都是 O(1)。

  4. 队列（Queue<T>）：

    • 底层实现：队列通常使用链表来实现，底层实现使用双向链表或循环链表来存储元素。在队列的头部进行出队操作，在队列的尾部进行入队操作。

  5. 栈（Stack<T>）：

    • 底层实现：栈通常使用链表或数组来实现，底层实现使用数组或链表来存储元素。在栈顶进行入栈和出栈操作。

除了以上常见的容器，C# 还提供了其他一些容器和数据结构，如集合（HashSet<T>）、有序集合（SortedSet<T>）、双端队列（Deque<T>）等，它们也有各自特定的底层实现方式。

总的来说，C# 中的容器都是经过优化的数据结构，具有良好的性能和易用性，开发人员可以根据实际需求选择合适的容器来进行数据操作。

vector和list的使用场景

  1. vector：

    • 底层实现：vector 使用动态数组实现，因此在内存中是连续存储的，可以通过索引进行快速访问。

    • 适用场景：

      • 需要快速随机访问元素，时间复杂度为 O(1)。
      • 需要在尾部进行频繁的插入和删除操作，时间复杂度为 O(1)。
      • 需要通过 push_back 在尾部添加元素，并且不需要频繁在中间或头部插入或删除元素。
      • 对内存空间的连续性要求不高。

  2. list：

    • 底层实现：list 使用双向链表实现，每个节点包含指向前一个节点和后一个节点的指针，因此在内存中不是连续存储的。

    • 适用场景：

      • 需要在任意位置进行频繁的插入和删除操作，时间复杂度为 O(1)。
      • 不需要进行频繁的随机访问元素，因为在 list 中进行随机访问的时间复杂度是 O(n)。
      • 需要高效地在中间或头部插入或删除元素。
      • 对内存空间的连续性要求较低，且可以接受额外的指针开销。

stack的适配器是什么，能不能用vector，为什么

在C++中，std::stack 是一个适配器容器，它提供了一种通过特定容器类型（默认是 std::deque）来实现栈（后进先出）数据结构的方式。

适配器容器本质上是一个封装了底层容器的类，它提供了一种特定的接口，使得底层容器的功能能够满足某种特定的数据结构需求。std::stack 就是通过封装底层容器来提供栈的功能，使得用户可以使用类似于栈的操作，如 push()、pop()、top() 等，而无需关心底层容器的具体实现。

std::stack 默认使用 std::deque 作为底层容器，但也可以通过模板参数指定其他容器类型，如 std::vector。但是，并不是所有的容器都适合用作 std::stack 的底层容器。虽然 std::vector 也可以存储元素，并提供栈的基本操作，但并不是最佳选择，原因如下：

  1. 高效的插入和删除操作：std::deque 支持高效的在头部和尾部进行插入和删除操作，时间复杂度为 O(1)，这与栈的操作特性相符。

  2. 不会触发数据移动：由于 std::deque 使用了分段连续存储的数据结构，插入和删除操作不会触发数据的整体移动，而 std::vector 则可能会导致数据的移动，时间复杂度为 O(n)。

相比之下，std::deque 提供了更好的插入和删除操作性能，同时不需要频繁地重新分配内存。因此，通常情况下，建议使用 std::deque 作为 std::stack 的底层容器。