前言:
在编程的浩瀚星空中,数据结构如同指引方向的星辰,它们不仅是构建算法与程序大厦的基石,更是解决复杂问题、优化性能的关键所在。其中,vector作为C++标准模板库(STL)中的一颗璀璨明珠,凭借其灵活、高效的特点,在软件开发中占据了举足轻重的地位。
vector,即向量容器,是一种能够存储任意类型对象的动态数组。它封装了动态数组的所有特性,包括自动的内存管理、灵活的元素访问方式以及高效的随机访问性能,同时还提供了丰富的成员函数来支持元素的插入、删除、遍历等操作。与静态数组相比,vector的最大优势在于其大小可以动态变化,无需程序员手动管理内存,极大地简化了编程复杂度,提高了代码的安全性和可维护性。 本文旨在深入探讨vector的内部机制、使用技巧及最佳实践,帮助读者全面了解并掌握这一强大的数据结构。我们将从vector的基本概念和特性出发,逐步深入到其内存管理策略、迭代器使用、元素操作、性能优化等多个方面。同时,结合实际应用场景,展示vector在解决各种编程问题时的独特魅力和高效性。
无论你是C++编程的初学者,还是希望提升编程技能的老手,本文都将为你提供宝贵的参考和实用的指导。让我们一起踏上这场关于vector的探索之旅,解锁C++编程的新世界,感受数据结构的魅力与力量。
vector
,不分配任何内存。vector
。实现代码:
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例:
void testvector1() {
xny::vector<int> v;
assert(v.size() == 0); // 验证大小
assert(v.capacity() == 0); // 验证容量
assert(v.empty()); // 验证是否为空
cout << "testvector1 passed" << endl;
}
int main()
{
testvector1();
return 0;
}
输出:
testvector1 passed
vector
,并使用默认值填充。实现代码:
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
vector(size_t n, const T& val = T()){ // 缺省参数用T类型的匿名对象
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val; // 填充默认值
}
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例:
void testvector2(){
xny::vector<int> v(4, 1);
assert(v.size() == 4); // 验证大小
assert(v.capacity() == 4); // 验证容量
assert(!v.empty()); // 验证是否为空
for (size_t i = 0; i < 4; ++i) {
assert(v[i] == 1); // 验证默认值
}
cout << "testvector2 passed" << endl;
}
int main()
{
testvector3();
return 0;
}
输出:
testvector2 passed
【思考】:
void testvector3() {
int arr[] = { 1, 2, 3, 4, 5 };
xny::vector<int> v(arr, arr + 5); // 使用迭代器范围初始化构造函数
}
【结果】:
添加代码如下:
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
iterator begin(){ return _start; }
iterator end(){ return _finish; }
vector() {}
vector(size_t n, const T& val = T()){ // 缺省参数用T类型的匿名对象
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val; // 填充默认值
}
}
// 使用迭代器范围初始化的构造函数
template<class InputIterator>
vector(InputIterator first, InputIterator last){
while (first != last) // 迭代器区间左闭右开
{
push_back(*first);
++first;
}
}
void reserve(size_t n){
if (n > capacity()){
size_t sz = size();
T* tmp = new T[n];
if (_start){
for (size_t i = 0; i < sz; i++){
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void push_back(const T& x){
if (_finish == _endofstorage){
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例:
void testvector3() {
int arr[] = { 1, 2, 3, 4, 5 };
xny::vector<int> v1(arr, arr + 5); // 使用迭代器范围构造函数
for (auto e : v1){
cout << e << " ";
}
cout << endl;
string str("hello world");
xny::vector<char> v2(str.begin(), str.end());
for (auto e : v2) {
cout << e << " ";
}
// 这里我们用两种不同类型的迭代器进行测试
}
输出:
【思考】:
error C2100
,看看编译示例:【解释】:
vector(int n, const T& val = T()) {
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val;
}
}
输出:
1 2 3 4 5
h e l l o w o r l d
vector
的拷贝构造函数。vector
是否完全复制原来的内容和容量。实现代码:
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
vector(size_t n, const T& val = T()){
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val;
}
}
vector(const vector<T>& v){
size_t sz = v.size();
_start = new T[capacity()];
for (size_t i = 0; i < sz; i++) {
_start[i] = v._start[i];
}
_finish = _start + sz;
_endofstorage = _start + v.capacity();
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例:
void testvector4() {
xny::vector<int> v1(5, 10);
xny::vector<int> v2(v1);
assert(v2.size() == 5); // 验证大小
assert(v2.capacity() == 5); // 验证容量
for (size_t i = 0; i < 5; ++i) {
assert(v2[i] == 10); // 验证数据拷贝
}
std::cout << "testvector4 passed" << std::endl;
}
int main()
{
testvector4();
return 0;
}
输出:
testvector4 passed
vector
赋值后,是否正确拷贝了内容和容量。实现代码:
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
vector(size_t n, const T& val = T()){
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val;
}
}
// 自定义一个swap函数方便拷贝
void swap(const vector<T> v){
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
// 赋值运算符重载
vector<T>& operator=(const vector<T>& v){
swap(v);
return *this;
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
【说明】:
vector<T>
的值作为参数,创建一个临时对象 v
。调用拷贝构造函数时自动执行拷贝,然后在赋值操作中与现有对象交换内容。传值是安全的,避免了手动内存管理问题。v
离开作用域时自动销毁,保证资源释放。测试样例:
void testvector5() {
xny::vector<int> v1(5, 10);
xny::vector<int> v2 = v1; // 赋值操作
assert(v2.size() == 5); // 验证大小
assert(v2.capacity() == 5); // 验证容量
for (size_t i = 0; i < 5; ++i) {
assert(v2[i] == 10); // 验证数据拷贝
}
std::cout << "testvector5 passed" << std::endl;
}
int main()
{
testvector5();
return 0;
}
输出:
testvector5 passed
实现代码:
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
【注意】
begin
与 end
迭代器【解释】:
begin
函数返回指向 vector
起始位置的迭代器(即指向第一个元素)。end
函数返回指向 vector
末尾的迭代器(即指向最后一个元素的下一个位置)。vector
中的元素。添加代码:
iterator begin(){
return _start;
}
iterator end(){
return _finish;
}
reserve
函数:实现动态扩容reserve
函数,测试在容量不足时是否能正确扩展。添加代码:
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
if (_start) {
for (size_ t i = 0; i < sz; i++) {
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
【注意】:
memcpy(tmp, _start, sizeof(T) * sz);
但是vector是深拷贝,但是vector空间上存的对象是string数组,使用memcpy
导致string对象的浅拷贝
测试用例:
void testvector6() {
xny::vector<int> v(5, 10);
v.reserve(10); // 预留容量
assert(v.capacity() == 10); // 验证容量扩展
for (size_t i = 0; i < 5; ++i) {
assert(v[i] == 10); // 验证数据保持不变
}
std::cout << "testvector6 passed" << std::endl;
}
int main()
{
testvector6();
return 0;
}
输出:
testvector6 passed
resize
函数:改变大小resize
函数,测试增加或减少vector
大小,如果增加,用特定字符暂时覆盖。添加代码:
void resize(size_t n, const T& val = T()) {
if (n < size()) {
_finish = _start + n;
}
else {
// 扩容n
reserve(n);
// 传值
while (_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
测试用例:
void testvector7() {
xny::vector<int> v(5, 10);
v.resize(8, 20); // 扩展大小并填充新值
assert(v.size() == 8); // 验证扩展后大小
for (size_t i = 0; i < 5; ++i) {
assert(v[i] == 10); // 验证原值不变
}
for (size_t i = 5; i < 8; ++i) {
assert(v[i] == 20); // 验证新值
}
std::cout << "testvector7 passed" << std::endl;
}
int main()
{
testvector7();
return 0;
}
输出:
testvector7 passed
push_back
函数:尾插元素【实现步骤】:
_finish
指针,指向新的末尾。添加代码:
void push_back(const T& val){
if (_finish == _endofstorage) {
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; // 采用2倍扩容
reserve(newcapacity);
}
*_finish = val;
++_finish;
}
优化版本:
void push_back(const T& x){
insert(end(), x);
}
测试用例:
void testvector8() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
assert(v.size() == 3); // 验证插入后的大小
assert(v.capacity() >= 3); // 验证容量是否自动扩展
assert(v[0] == 1 && v[1] == 2 && v[2] == 3); // 验证插入的元素是否正确
std::cout << "testvector9 passed" << std::endl;
}
int main()
{
testvector8();
return 0;
}
输出:
testvector8 passed
pop_back
函数:尾删元素【实现步骤】:
_finish
指针向前移动一位,即删除最后一个元素。添加代码:
void pop_back() {
assert(_finish != _start); // 确保vector非空
--_finish; // 逻辑删除最后一个元素
}
优化版本:
void pop_back(){
erase(--end());
}
测试用例:
void testvector9() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.pop_back();
assert(v.size() == 2); // 验证删除后的大小
assert(v[0] == 1 && v[1] == 2); // 验证剩余元素是否正确
std::cout << "testvector9 passed" << std::endl;
}
int main()
{
testvector9();
return 0;
}
输出:
testvector9 passed
insert
函数:在指定位置插入元素【实现步骤】:
_finish
指针。添加代码:
iterator insert(iterator pos, const T& val) {
// 断言判断pos的有效性
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage) {
// 用临时变量存指定位置到起点的长度
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; // 采用2倍扩容
reverse(newcapacity);
// 解决pos迭代器失效问题
pos = len + _start;
}
// 将插入位置及其后的元素整体向后移动。
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
测试用例:
void testvector10() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.insert(v.begin() + 2, 3); // 在第2个位置插入3
assert(v.size() == 4); // 验证插入后的大小
assert(v[0] == 1 && v[1] == 2 && v[2] == 3 && v[3] == 4); // 验证插入的元素是否正确
std::cout << "testvector8 passed" << std::endl;
}
int main()
{
testvector10();
return 0;
}
输出:
testvector10 passed
【问题】:
pos
迭代器可能会发生改变,所以不能用原来的pos
。erase
函数:删除指定位置的元素【实现步骤】:
erase
位置之后的元素向前移动一位。_finish
指针。添加代码:
iterator erase(iterator pos) {
// 断言判断pos的有效性
assert(pos >= _start && pos <= _finish);
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
测试用例:
void testvector11() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.erase(v.begin() + 2); // 删除第2个元素
assert(v.size() == 3); // 验证删除后的大小
assert(v[0] == 1 && v[1] == 2 && v[2] == 4); // 验证删除后的元素顺序
std::cout << "testvector11 passed" << std::endl;
}
int main()
{
testvector11();
return 0;
}
输出:
testvector11 passed
【注意】:
#pragma once
#include<assert.h>
using namespace std;
namespace xny
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
// 解决vector<int> v(10, 1)
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last) // 迭代器区间左闭右开
{
push_back(*first);
++first;
}
}
vector()
{}
vector(const vector<T>& v)
{
size_t sz = v.size();
_start = new T[v.capacity()];
// memcpy(_start, v._start, sizeof(T) * v.size());
for (size_t i = 0; i < sz; i++)
{
_start[i] = v._start[i];
}
_finish = _start + sz;
_endofstorage = _start + v.capacity();
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
// v1 = v2
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& val = T()) // T类型的匿名对象
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
void push_back(const T& x)
{
/*if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
// 解决pos迭代器失效问题
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
void print(const vector<int>& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (size_t i = 0; i < v1.size(); i++)
{
v1[i]++;
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
print(v1);
}
void test_vector2()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(5);
v1.push_back(5);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
v1.insert(v1.begin(), 100);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
/*vector<int>::iterator p = v1.begin() + 3;
v1.insert(p, 300);*/
xny::vector<int>::iterator p = v1.begin() + 3;
//v1.insert(p+3, 300);
// insert以后迭代器可能会失效(扩容)
// 记住,insert以后就不要使用这个形参迭代器了,因为他可能失效了
v1.insert(p, 300);
// 高危行为
// *p += 10;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector3()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
// v1.erase(v1.begin());
auto it = v1.begin() + 4;
v1.erase(it);
// erase之后,迭代器失效了,不能访问
// vs进行强制检查,访问会直接报错
cout << *it << endl;
++it;
cout << *it << endl;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
vector<int> v;
v.resize(10, 0);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector5()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int> v2(v1);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v3 = v1;
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
};
void test_vector6()
{
vector<string> v;
v.push_back("11111");
v.push_back("22222");
v.push_back("33333");
v.push_back("44444");
v.push_back("55555");
// 自定义类型最好加引用
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
vector<string> v1(v);
for (auto& e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector7()
{
vector<int> v(10u, 1);
vector<string> v1(10, "111");
// vector<int> v2(10, 1);
}
}
#include"vector.h"
#include <bits/stdc++.h>
using namespace std;
int main()
{
xny::test_vector7();
// ...其他测试
return 0;
}