vector push_back涉及的数据结构知识点和算法
时间: 2023-09-29 15:09:32 浏览: 81
学数据结构涉及的算法
vector push_back 涉及的数据结构知识点是动态数组,算法是动态内存分配。
vector 是一个动态数组,可以在运行时自动扩展大小,push_back 函数将元素插入 vector 容器的尾部。当 vector 的容量不足时,push_back 函数会触发重新分配内存空间并将原有元素复制到新的内存空间中,再将新的元素插入到新的内存空间中。因此,push_back 操作的时间复杂度是 O(1) 均摊时间复杂度,但是在重新分配内存空间时,时间复杂度会变为 O(n)。
动态内存分配算法是指程序在运行时根据需要动态地申请和释放内存空间。在实现 vector 的 push_back 操作中,需要使用动态内存分配算法来动态地分配内存空间。常见的动态内存分配算法有分配器、伙伴算法、堆算法等。C++ STL 中的 vector 类使用的是堆算法,即使用 new 和 delete 进行内存分配和释放。
阅读全文