广东网站建设联系电话,上海注册公司电话咨询,网站制作自己接单,高端网站定制方案目录
前言
1.STL是什么
2.vector使用
2.1 vector简介
2.2 常用接口函数
1. 构造函数
2.operator[ ]和size#xff0c;push_back
3. 用迭代器进行访问和修改
4. 范围for遍历
5.修改类型函数 pop_back find insert erase
6. 容量相关函数capacity resize reserve
3.…目录
前言
1.STL是什么
2.vector使用
2.1 vector简介
2.2 常用接口函数
1. 构造函数
2.operator[ ]和sizepush_back
3. 用迭代器进行访问和修改
4. 范围for遍历
5.修改类型函数 pop_back find insert erase
6. 容量相关函数capacity resize reserve
3. vector模拟实现
3.1 模版问题
3.2 vector成员变量和迭代器
3.3 capacitysizeoperator[ ]
3.3 push_back和reserve函数
3.5 构造函数析构函数
3.6 拷贝构造函数和赋值拷贝函数
3.7 insert和erase
3.8 迭代器失效问题
总结 前言
今天将开启对CSTL的学习STL作为强大的模版库十分值得我们学习在此途中提升自己的C代码能力。 1.STL是什么
标准模板库Standard Template LibrarySTL是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。STL是C标准库的重要组成部分不仅是一个可复用的组件库而且是一个包罗数据结构与算法的软件框架。
STL版本
原始版本Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本并且是开源的HP 版本--所有STL实现版本的始祖。P. J. 版本由P. J. Plauger开发继承自HP版本不开源。RW版本由Rouge Wage公司开发继承自HP版本不开源。SGI版本由Silicon Graphics Computer SystemsInc公司开发继承自HP版 本。被GCC(Linux)采用是开源的。
STL有六大组件 2.vector使用
2.1 vector简介
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。
因为vector内部实现没有使用具体类型而是给出模版所以实例化一个vector变量时需要给出具体类型。记得包含头文件vector。 2.2 常用接口函数
1. 构造函数
vector(const allocator_type alloc allocator_type());//函数原型void test_vector()
{vectorint v1;
}
默认构造函数构造一个没有元素的空容器。在test_vector函数内定义一个int类型的空容器。
tip其中的allocator是空间适配器用于分配内存空间的暂时不用深究。 vector (size_type n, const value_type val value_type(),const allocator_type alloc allocator_type());void test_vector()
{vectorint v1(10, 1);
}
填充构造函数:构造一个包含n个元素的容器。每个元素都是val的一个副本。test_vector函数中实例化了一个int类型的vector容器里面有10个1整型变量。 template class InputIteratorvector (InputIterator first, InputIterator last,const allocator_type alloc allocator_type());void test_vector()
{vectorint v1(10, 1);vectorint v2(v1.begin(), v1.end());
}
迭代器构造函数构造一个包含与[first,last)范围相同数量元素的容器每个元素以相同的顺序从该范围内的相应元素构造。 vector (const vector x);void test_vector()
{vectorint v1(10, 1);vectorint v2(v2);
} 拷贝构造函数用x中每个元素的副本按相同顺序构造一个容器。 2.operator[ ]和sizepush_back
vector是一个类似数组的容器物理存储上是连续的那自然少不了下标访问。
push_back函数望文生义就是在尾部插入一个元素。size函数是获取当前容器元素个数。[ ]是可以访问填入下标的元素并进行修改。
void test_vector1()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;
} 运行结果如下 3. 用迭代器进行访问和修改
使用迭代器前我们需要了解什么是迭代器。
在C中迭代器Iterator是一种检查容器中元素并遍历元素的数据类型。迭代器提供了一种通用的方式来访问容器中的元素而不需要关心容器底层的具体数据结构。通过迭代器可以对容器进行遍历、读取、修改和删除元素等操作。
使用迭代器时需要定义一个变量变量类型就是int类型下的vector容器中的iterator类。不管vector容器中具体类型是什么。在vector中约定俗成迭代器类型名是iterator。定义迭代器变量后赋值为vector成员函数begin在vector中指向第一个元素。还有end函数表示最后一个元素的下一个位置。还有!前置!和*操作符表示往后指向下一个元素*操作类似于指针的解引用操作代表该元素。但是自定义类型没有这些操作都是通过运算符重载的方式将其的行为编程跟指针变量相类似的操作。你可以类比成指针但是iterator这个类型不一定是指针可能还是一个类。
void test_vector2()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vectorint::iterator it1 v1.begin();while (it1 ! v1.end()){cout *it1 ;it1;}cout endl;it1 v1.begin();while (it1 ! v1.end()){*it1;//对容器元素进行修改cout *it1 ;it1;}cout endl;//全部展开成运算符重载函数it1.operator(v1.begin());while (it1.operator!(v1.end())){cout it1.operator*() ;it1.operator();}cout endl;
}上面最后一段代码将这些运算符写成调用函数的形式也可以进行遍历但是代码的可读性比较差。运行结果如下 但是有些情况下只是遍历数据进行打印不想修改元素。如果使用一般迭代器iterator会导致权限放大误改其中的元素。我们可以使用const_iterator对该类型的容器进行访问即使不小心修改系统也会报错。
void test_vector3()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vectorint::const_iterator it1 v1.begin();while (it1 ! v1.end()){//*it 5 error,不可以修改cout *it1 ;it1;}cout endl;
}
运行结果如下 迭代器不仅可以正向遍历还有反向迭代器倒着遍历。跟正向迭代器类似也有可修改和不可修改两种反向迭代器。
void test_vector4()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vectorint::reverse_iterator it1 v1.rbegin();while (it1 ! v1.rend()){*it1 4;cout *it1 ;it1;}cout endl;vectorint::const_reverse_iterator it2 v1.rbegin();while (it2 ! v1.rend()){//*it2 1 errorcout *it2 ;it2;}cout endl;
}
运行结果如下 4. 范围for遍历
范围for是一个比较实用的语法支持遍历各种容器但是只能正向遍历。
范围for看起来十分高级但是最终的底层逻辑还是跟迭代器相关只要相关容器提供了begin和end函数就支持遍历。
void Test()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;//想要修改内容需要使用引用for (auto e : v1){e;cout e ;}cout endl;
}
运行结果如下 5.修改类型函数 pop_back find insert erase
pop_back函数是删除最后一个元素效率高。如果容器为空继续删除会直接终止程序。发出断言警告。
之后的Print函数就是正向输出容器中的所有元素。
void Print(vectorint v)
{vectorint::iterator it1 v.begin();while (it1 ! v.end()){cout *it1 ;it1;}cout endl;
}void test_vector5()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);Print(v1);v1.pop_back();v1.pop_back();Print(v1);
}
运行结果如下 findinsert和erase
template class InputIterator, class T
InputIterator find (InputIterator first, InputIterator last, const T val); find函数给两个相同的类型的迭代器范围是从first位置的元素到last前一个位置的元素是一个左闭右开的区间[first, last)寻找与val相同的元素并返回该元素位置的迭代器。如果没有找到返回last迭代器。 //1.
iterator insert (iterator position, const value_type val);
//2.
void insert (iterator position, size_type n, const value_type val);
//3.
template class InputIterator
void insert (iterator position, InputIterator first, InputIterator last);insert函数原型如下有三种类型。
第一种是传插入位置的迭代器变量插入值为val。第二种是传插入位置的迭代器变量但是插入n个val元素进去。第三种是传插入位置的迭代器变量但插入的元素是别的容器的元素范围是从first位置的元素到last前一个位置的元素是一个左闭右开的区间[first, last)。 //1.
iterator erase (iterator position);
//2.
iterator erase (iterator first, iterator last);
erase函数有两种类型第一种是删除一个指定位置的元素只用传该元素位置的迭代器。第二种是删除某个范围内的元素传入first迭代器和last迭代器是一个左闭右开的区间[first, last)。
void test_vector6()
{int arr[] { 1,2,3,4,5,6,};vectorint v1(arr, arr 6);Print(v1);vectorint::iterator pos find(v1.begin(), v1.end(), 4);v1.insert(pos, 20);Print(v1);pos find(v1.begin(), v1.end(), 5);v1.insert(pos, 2, 10);Print(v1);vectorint v2;v2.insert(v2.begin(), v1.begin(), v1.end());Print(v2);pos find(v1.begin(), v1.end(), 6);v1.erase(pos);Print(v1);v2.erase(v2.begin(), --v2.end());Print(v2);
}
运行结果如下 6. 容量相关函数capacity resize reserve
capacity函数是获取该容器的容量大小。我们设计一个函数测试vector的扩容机制分别在VS和Linux环境下进行测试。
void TestExpand()
{size_t sz;vectorint v;sz v.capacity();cout making v grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
}
在VS环境下扩容情况如下图所示。一开始插入四个元素时每次扩容只增加一个容量。插入第五个元素开始就是1.5倍扩容的速度。 在Linux环境下我们可以看到是遵循2倍扩容的原则进行扩容。 void resize (size_type n, value_type val value_type());
resize可以调整容器元素个数的大小使其包含n个元素。如果n小于当前容器元素个数则内容减少到前n个元素并删除超出的元素。如果n大于当前容器元素个数则通过尾插插入所需元素扩展内容以达到n的大小。如果有给定val插入元素就为val否则将其进行值初始化自定义类型调用默认构造函数自定义类型也有自己的初始化。如果超过容器容量大小会扩容。
比如说你创建了一个含有四个元素容器。如果用下标访问该容器元素下标值范围是0~3不能超出这个范围。当你想使用下标给第五个元素赋值就会断言报错。此时就可以使用resize函数将容器元素个数扩充便可以使用下标给之后的元素赋值。
void test_vector7()
{int arr[] { 1,2,3,4 };int size sizeof(arr) / sizeof(int);vectorint v1(arr, arr size);//v1[4] 0; //errorv1.resize(8);v1[4] 1;v1[5] 2;v1[6] 3;v1[7] 4;Print(v1);
}
运行结果如下 void reserve (size_type n);
reserve是调整容器容量大小。只用传一个无符号整型参数。如果n大于当前容器的容量会给该容器重新分配存储空间将其容量增加到n。在其他情况下函数调用不会导致重新分配容器容量不变。reserve不会对容器里的元素做出改变容器元素个数不变。
在上面测试不同平台下vector的扩容机制扩容的本质是开辟新空间将原来容器的内容拷贝过去再释放原有的空间。如果要频繁插入数据就会频繁的扩容会造成许多消耗所以如果知道要插入数据个数可以一次性扩容完毕减少不必要的消耗。
void TestExpand()
{size_t sz;vectorint v;sz v.capacity();v.reserve(100); // 提前将容量设置好可以避免一遍插入一遍扩容cout making v grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
}
在VS中运行结果如下 3. vector模拟实现
3.1 模版问题 模拟实现vector会用到类型模版一般建议将实现的函数内容都放在一个头文件中。因为给定一个参数类型实例化vector容器时这个过程发生编译的期间如果函数的声明和定义分离放在两个文件中编译器无法根据这个类型进行代码分发。直接创建一个vector.h的头文件。还有为了不和C标准库里面的vector发生命名冲突可以自己创建一个命名空间User。再包含上需要的头文件。 #include assert.hnamespace User
{template class Tclass vector{//...};} 3.2 vector成员变量和迭代器
vector类内部通常有三个迭代器类型的成员变量。_start指向第一个元素_finish指向末尾元素的后一位_end_of_storage表示容器容量末尾。
#include assert.hnamespace User
{template class Tclass vector{private:iterator _start;iterator _finish; iterator _end_of_storage; };} 因为vector物理存储和逻辑存储都是连续的所以我们可以将他的迭代器类型用原生指针实现。
typedef T* iterator;
typedef const T* const_iterator;
再提供begin和end函数返回容器第一个元素的位置和末尾元素的后一位。其中const_iterator类型的迭代器需要保证容器元素不能被修改需要在函数后加上const成为const成员函数。
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}iterator begin()
{return _start;
}iterator end()
{return _finish;
} 3.3 capacitysizeoperator[ ]
指针相减可以得到其中该类型元素个数之差。因此size和capacity分别用_finish和 _end_of_storage指针减去_start指针就可以实现。
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _end_of_storage - _start;
}
operator[ ]实际上返回_start指针用下标访问的元素即可及得要先检查i的大小是否符合要求。还提供了const类型的[ ]重载。
T operator[](size_t i)
{assert(i size());return _start[i];
}T operator[](size_t i) const
{assert(i size());return _start[i];
} 3.3 push_back和reserve函数
我们先完成一个尾插和扩容的函数之后的构造函数就依靠这个接口进行初始化。
push_back是在末尾插入元素一开始需要检查容器容量大小够不够在插入多一个元素。如果_finish指针与_end_of_storage指针相等时说明容量不够需要扩容。扩容时先判断capacity是否为零为零还没插入数据给四个元素空间之后就是两倍扩容。再讲一下扩容的逻辑首先判断传递的参数n是否大于当前容量如果大于才能继续扩容出现其他情况不做处理。扩容一般动态开辟一块为n个T类型参数大小的内存空间然后将原有的数据拷贝过来在释放原有空间内存。其重要注意需要先记录之前空间的元素个数方便之后调整_finish指针的位置。
void reserve(size_t n)
{if (n capacity()){T* tmp new T[n];size_t oldsize size();if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start tmp;_finish _start oldsize;_end_of_storage _start n;}
}void push_back(const T x)
{if (_finish _end_of_storage){//两倍速扩容size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish x;_finish;
}
写一个测试函数测试一下之前实现的各种接口函数用正常的for循环遍历迭代器遍历还有范围for进行遍历。
void test_vector1()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;vectorint::iterator it v1.begin();while (it ! v1.end()){cout *it ;it;}cout endl;for (auto e : v1){cout e ;}cout endl;
}
测试结果如下 但是reserve函数实现就没有问题吗看看下面的测试函数
void test_vector2()
{vectorstring v1;v1.push_back(xxxxxxxxxx);v1.push_back(xxxxxxxxxx);v1.push_back(xxxxxxxxxx);v1.push_back(xxxxxxxxxx);v1.push_back(xxxxxxxxxx);for (auto e : v1){cout e ;}cout endl;
}
当你运行这段代码的时候打印前面四个元素会出现乱码。这是为什么呢
如下图所示tmp拷贝过来的内容把指针变量也原封不动按字节拷贝导致_start和tmp中的_str指针指向同一块空间。之后会delete[ ] _start而delete释放空间之前会调用里面自定义类型的析构函数再释放这个空间这就会造成我们数据的丢失。 所以要进行一个深拷贝写一个for循环传统写法是赋值如果是内置类型直接赋值如果是自定义类型调用该类型的赋值拷贝函数。现代的写法是直接将tmp[i]与_start[i]进行交换直接调用C标准库里的交换函数交换的好处是不用再拷贝值并且delete掉_start里面没有自定义类型不用调用析构函数。
void reserve(size_t n)
{if (n capacity()){T* tmp new T[n];size_t oldsize size();if (_start){for (size_t i 0; i oldsize; i){//tmp[i] _start[i];//传统写法std::swap(tmp[i], _start[i]);}delete[] _start;}_start tmp;_finish _start oldsize;_end_of_storage _start n;}
} 3.5 构造函数析构函数
vector构造函数我们三个其中一个是给定个数n给定T类型的x变量进行初始化。
为什么这个会重载成两个呢因为有的时候传参可能是int或者size_t类型,编译器无法判断需要重载成两个构造函数。我们可以用传统的方式开辟空间进行赋值然后再赋值成员变量。不过也可以使用我们实现好的push_back函数接口因为符合尾插的特点不过在尾插时可以先扩容这样就不会频繁扩容提升效率。
vector(size_t n, const T x T())
{reserve(n);for (size_t i 0; i n; i){push_back(x)}
}vector(int n, const T val T())
{reserve(n);for (int i 0; i n; i){push_back(val);}
}
写一个测试函数用一个Print函数实现打印整个容器元素之后打印就用这个Print函数。
template class T
void Print(const vectorT v)
{for (auto e : v){cout e ;}cout endl;
}void test_vector3()
{vectorint v1(4, 10);Print(v1);} vector构造函数还有给定一个容器迭代器区间进行初始化也是跟上面的类似复用push-back函数。不过需要再使用一个函数模版定义first和last变量用while循环类似我们使用迭代遍历容器一样其他的容器都会对!*和进行重载。
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}
写一个测试函数。
void test_vector4()
{vectorint v1(4, 10);Print(v1);vectorint v2(v1.begin(), v1.end());Print(v2);
} 我们来看看这段代码在STL的Vector可以支持带花括号的初始化。
void test_vector5()
{std::vectorint v1 { 1,2,3,4,5,6 };for (auto e : v1){cout e ;}cout endl;
}
结果如下 这是为什么呢因为C有一个类型叫做initializer_list如下面的代码实例任何一个带花括号的里面是相同元素用逗号分隔就会是该类型。这个类型里面只有两个指针维护一个指向第一个元素另外一个指向最后一个元素。
void Test()
{auto il { 1,2,3,4,5,6 };initializer_listint il1 { 1,2,3,4,5,6 };cout typeid(il).name() endl;cout sizeof(il) endl;
} 这个构造函数跟之前也是类似只是传递的参数是initializer_list直接用范围for尾插。
vector(initializer_listT il)
{reserve(il.size());for (auto e : il){push_back(e);}
} 最后别忘了实现默认构造函数,可以使用关键字default强制生成默认构造函数还有可以给成员变量一个缺省值。
class vector
{public:vector() default;private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;
} 析构函数先判断_start是否不为空然后再释放空间成员变量赋值为空指针。
~vector()
{if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}
} 3.6 拷贝构造函数和赋值拷贝函数
拷贝构造函数跟之前的构造函数类似先扩容再复用push_back函数。
vector(const vectorT v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
} 赋值拷贝函数可以借鉴上面写reserve的现代写法可以实现一个swap函数专门交换vectorT类型的变量里面套用标准库里的swap函数直接交换成员变量不需要再开辟新空间并拷贝数据。然后赋值拷贝函数参数写成一个普通vectorT类型的变量传递参数过来就会调用vector的拷贝构造函数然后再用我们刚实现swap进行交换不会涉及浅拷贝的问题。并且v还是个临时变量出了作用域自动调用析构函数并销毁变量。
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}vectorT operator(vectorT v)
{swap(v);return *this;
} 3.7 insert和erase
insert和erase函数实现跟顺序表类似都需要移动数据。insert中当容量不足要扩容时需要先记录pos相对于_start差多少个元素个数因为扩容之后原有空间被释放pos指向的就是一块被释放的空间变成野指针。
void insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);if (_finish _end_of_storage){size_t len pos - _start;//记录pos相对于start的位置size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);pos _start len;}iterator end _finish;while (end pos){*end *(end - 1);--end;}*pos x;_finish;
}void erase(iterator pos)
{assert(pos _start pos _finish);iterator end pos 1;while (end _finish){*(end - 1) *end;end;}--_finish;
} 3.8 迭代器失效问题
void test_vector2()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int x;cin x;std::vectorint::iterator pos find(v1.begin(), v1.end(), x);if (pos ! v1.end()){v1.insert(pos, 1000);}for (auto e : v1){cout e ;}cout endl;
}
我们运行下面的代码会发现程序崩溃了这是为什么呢这是因为当再插入一个元素的话会发生扩容。扩容时我们insert扩容时注意到pos指向一块被释放的空间更新了pos。但是在insert函数中会创建一个形参pos形参是实参的一份临时拷贝改变形参不会对外部的pos实参有影响因此pos迭代器失效。解决的办法就是让insert函数的返回类型为iterator像下面一样更新pos的值。 //...if (pos ! v1.end()){pos v1.insert(pos, 1000);}//... 所以insert的函数返回参数需要修改返回第一个新插入的元素。
iterator insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);if (_finish _end_of_storage){size_t len pos - _start;//记录pos相对于start的位置size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);pos _start len;}iterator end _finish;while (end pos){*end *(end - 1);--end;}*pos x;_finish;
} 再看一下下面的代码与insert类似我们删除一个元素会造成迭代器失效吗
pos指向的位置不变但是某些平台会缩容或者造成野指针现象所以一般认为是erase迭代器失效的erase后会返回被删除元素的后一位。
void test_vector3()
{std::vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;int x;cin x;std::vectorint::iterator pos find(v1.begin(), v1.end(), x);if (pos ! v1.end()){v1.erase(pos);cout *pos endl;}for (auto e : v1){cout e ;}cout endl;
}
erase函数也需要修改一下返回删除元素的后一个位置。
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator end pos 1;while (end _finish){*(end - 1) *end;end;}--_finish;return pos 1;
} 总结
通过这篇文章你应该了解了vector的使用和一些简单的底层模拟实现。不过纸上得来终觉浅绝知此事要躬行需要多加练习
创作不易希望这篇文章能给你带来启发和帮助如果喜欢这篇文章请留下你的三连你的支持的我最大的动力
