vector

std::vector 是 STL 提供的内存连续的可变长度的数组(亦称列表)数据结构。能够提供线性复杂度的插入和删除,以及常数复杂度的随机访问。

C++中所有容器提供的都是值(value)语意,而非引用(reference)语意。容器执行插入元素的操作时,内部实施拷贝动作。所以STL容器内存储的

元素必须能够被拷贝(含有指针成员的类必须提供拷贝构造函数)。

 

1. 为什么要使用 vector

   vector 由于其对内存的动态处理,时间效率在部分情况下低于静态数组,并且在编译器不一定开全优化的情况下更加糟糕。所以在正常存储数据的时候,

   通常不选择 vector 。下面给出几个 vector 优秀的特性,在需要用到这些特性的情况下,vector 能给我们带来很大的帮助。

   1)vector 可以动态分配内存,还支持动态扩容。

   2)vector 重写了比较运算符及赋值运算符,这使得我们可以方便的判断两个容器是否相等。例如可以利用 vector<char> 实现字符串比较。

      另外 vector 也重载了赋值运算符,使得数组拷贝更加方便。

   3)vector 便利的初始化,由于 vector 重载了 = 运算符,所以我们可以方便的初始化。此外从 C++11 起 vector 还支持列表初始化,

      例如 vector<int> data {1, 2, 3};

 

2. vector 的实现细节

   vector 的底层其实仍然是定长数组,它能够实现动态扩容的原因是增加了避免数量溢出的操作。

   首先需要指明的是 vector 中元素的数量(长度)n与它已分配内存最多能包含元素的数量(容量)N是不一致的, vector 会分开存储这两个量。

   当向 vector 中添加元素时,如发现n > N,那么容器会分配一个尺寸为 2N 的数组,然后将旧数据从原本的位置拷贝到新的数组中,再将原来的内存释放。

   尽管这个操作的渐进复杂度是O(n),但是可以证明其均摊复杂度为O(1)。而在末尾删除元素和访问元素则都仍然是O(1)的开销。 因此,只要对 vector 的尺

   寸估计得当并善用 resize()reserve() ,就能使得 vector 的效率与定长数组不会有太大差距。

   另外vector的访问效率也是比数组要低的,因为virtual等的修饰,访问元素比想象中的要复杂。

 

3. vector 的构造函数

vector<int> v0;                              // 创建空vector
v0.reserve(3);                               // 预分配三个元素的空间
vector<int> v1(3);                           // 创建一个初始空间为3的vector,其元素的默认值是0
vector<int> v2(3, 2);                        // 创建一个初始空间为3的vector,其元素的默认值是2
vector<int> v4(v2);                          // 创建一个v2的拷贝vector v4, 其内容元素和v2一样
vector<int> v5(v4.begin()+1, v4.begin()+3);  // 创建一个v4的拷贝vector v5,其内容是v4[1]~v4[3]
vector<int> v6(std::move(v2));               // 移动v2到新创建的vector v6,只发生浅拷贝,可能提高效率。(C++11)

 

4. vector 的元素访问

v.at(pos);   // 返回容器中下标为 pos 的引用。如果数组越界抛出 std::out_of_range 类型的异常。
v[pos];      // 返回容器中下标为 pos 的引用。不执行越界检查。
v.front();   // 返回首元素的引用。
v.back();    // 返回末尾元素的引用。
v.data();    // 返回指向数组第一个元素的指针。

 

5. vector 的迭代器

begin()/cbegin();    // 返回指向首元素的迭代器,其中 *begin = front 。
end()/cend();        // 返回指向数组尾端占位符的迭代器,注意是没有元素的。
rbegin()/rcbegin();  // 返回指向逆向数组的首元素的逆向迭代器,可以理解为正向容器的末元素。
rend()/rcend();      // 返回指向逆向数组末元素后一位置的迭代器,对应容器首的前一个位置,没有元素。

  

6. vector 的长度和容量

   size指容器当前拥有的元素个数;而capacity则指容器在必须分配新存储空间之前可以存储的元素总数。

   resize既分配了空间,也创建了对象,可以通过下标访问。当resize的大小小于capacity,便会修改容量。

   reserve只修改capacity大小,不修改size大小,也不创建对象。

empty();           // 返回一个 bool 值,即 v.begin() == v.end() , true 为空, false 为非空。
size();            // 返回容器长度(元素数量),即 std::distance(v.begin(), v.end()) 。
resize(size);      // 改变 vector 的长度并且会创建对象,多退少补。补充元素可以由参数指定。
max_size();        // 返回容器的最大可能长度。
reserve(size);     // 使得 vector 预留一定的内存空间,避免不必要的内存拷贝。
capacity();        // 返回容器的容量,即不发生拷贝的情况下容器的长度上限。
shrink_to_fit();   // 使得 vector 的容量与长度一致,多退但不会少。

 

7. vector 元素增删及修改

iterator insert(iterator loc, const TYPE &val);                       // 在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器
void insert(iterator loc, size_type num, const TYPE &val);            // 在指定位置loc前插入num个值为val的元素
void insert(iterator loc, input_iterator start, input_iterator end);  // 在指定位置loc前插入区间[start, end)的所有元素

iterator erase(iterator position);              // 删除某个迭代器的元素,返回指向下一个元素的迭代器
iterator erase(iterator first, iterator last);  // 删除某个区间的元素,返回指向下一个元素的迭代器

clear();      // 清除所有元素
push_back();  // 在末尾插入一个元素
pop_back();   // 删除末尾元素

  

 

原文链接: https://www.cnblogs.com/yanghh/p/13024906.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    vector

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/352317

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月2日 上午7:27
下一篇 2023年3月2日 上午7:28

相关推荐