C++中如何在vector中插入有序元素
发布时间: 2024-05-02 16:08:01 阅读量: 9 订阅数: 19
![C++中如何在vector中插入有序元素](https://img-blog.csdnimg.cn/1729e077cf74470f9c12f90fe7b52b21.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU4NTE5OQ==,size_16,color_FFFFFF,t_70)
# 2.1 vector的底层实现原理
vector是一种动态数组,底层使用连续的内存空间存储元素。它内部维护了一个指针数组,指向实际存储元素的内存块。当需要插入或删除元素时,vector会动态调整内存块的大小。
vector的底层实现使用了一种称为"连续内存分配器"的机制。该机制将内存分配为大块,称为"块"。每个块包含一定数量的元素,通常为32或64个。当vector需要更多空间时,它会从分配器中请求一个新的块,并将元素从旧块移动到新块。
# 2. vector中插入元素的理论基础
### 2.1 vector的底层实现原理
vector是一种动态数组,底层使用连续的内存空间存储元素。当需要插入元素时,vector会动态地调整其容量,以容纳新的元素。
vector的底层实现使用了一个数组指针和一个容量值。数组指针指向存储元素的内存地址,容量值表示数组可以容纳的元素数量。当插入一个元素时,如果当前容量不足,vector会分配一个更大的数组,并将原有元素复制到新数组中。
### 2.2 插入操作的时间复杂度分析
vector中插入元素的时间复杂度取决于插入位置和当前容量。
**插入到末尾**
当插入元素到vector末尾时,时间复杂度为O(1)。这是因为不需要移动任何现有元素,只需要将新元素添加到数组的末尾即可。
**插入到中间**
当插入元素到vector中间时,时间复杂度为O(n),其中n是vector的当前大小。这是因为需要将插入点之后的元素向后移动,以腾出空间给新元素。
**插入到开头**
当插入元素到vector开头时,时间复杂度也为O(n)。这是因为需要将所有元素向后移动,以腾出空间给新元素。
**代码块:**
```cpp
#include <vector>
int main() {
std::vector<int> v;
// 插入到末尾
v.push_back(1); // 时间复杂度:O(1)
// 插入到中间
v.insert(v.begin() + 2, 2); // 时间复杂度:O(n)
// 插入到开头
v.insert(v.begin(), 0); // 时间复杂度:O(n)
return 0;
}
```
**代码逻辑分析:**
* `push_back()`函数将元素插入到vector末尾。
* `insert()`函数将元素插入到指定位置。
* `begin()`函数返回指向vector第一个元素的迭代器。
# 3.1 二分查找法
#### 3.1.1 二分查找算法的原理和步骤
二分查找算法是一种高效的搜索算法,适用于有序数组。其基本原理是将数组划分为两部分,不断缩小搜索范围,直到找到目标元素或确定其不存在。
二分查找算法的步骤如下:
1. 初始化两个指针,`left` 和 `right`,分别指向数组的第一个元素和最后一个元素。
2. 计算数组的中间索引 `mid`。
3. 比较目标元素与 `arr[mid]`:
- 如果相等,则返回 `mid`。
- 如果目标元素小于 `arr[mid]`,则将 `right` 更新为 `mid - 1`。
- 如果目标元素大于 `arr[mid]`,则将 `left` 更新为 `mid + 1`。
4. 重复步骤 2 和 3,直到 `left` 大于或等于 `right`。
5. 如果 `left`
0
0