vector的实现原理

vector的实现原理

std::vector 是C++标准库中的一个动态数组实现，它的实现原理基于数组数据结构。实现通常包含一个指向数组起始位置的指针、数组的大小和容量等信息。

在尾部进行插入和删除操作时，只需调整尾部指针，不需要移动整个数据块。

当元素数量达到当前内存块的容量时，std::vector 会申请一个更大的内存块，将元素从旧的内存块复制到新的内存块，并释放旧的内存块。

由于数组的连续内存结构，通过索引进行访问时可以通过指针运算实现常数时间复杂度的随机访问。

template <class T, class Allocator = std::allocator<T>> class vector {

private:

T* elements;// 指向数组起始位置的指针 size_t size;// 当前元素数量

size_t capacity;// 当前分配的内存块容量 };

list的实现原理

std::list 是C++标准库中的一个双向链表实现，它的实现原理基于链表数据结构。每个节点包含两个指针，分别指向前一个节点和后一个节点, 以及存储实际数据的部分。

template <class T> struct Node {

T data;

Node* prev;

Node* next;

};

std::list 维护一个头指针和一个尾指针，它们分别指向链表的第一个和最后一个节点。

在插入和删除操作时，只需调整相邻节点的指针，不需要移动整个数据块。

vector和list的区别

1. 实现上

vector使用动态数组实现。连续的内存块，支持随机访问。在尾部进行插入/删除操作较快，但在中间或头部进行插入/删除可能会涉及大量元素的移动。

list使用双向链表实现。不连续的内存块，不支持随机访问。在任意位置进行插入/删除操作都是常数时间复杂度。

1. 访问上

vector支持通过索引进行快速随机访问。使用迭代器进行访问时，效率较高。