阿里云1m 宽带做网站服务器,淄博网站制作公司,关于网站开发人员的薪资,抖音小程序源码listlist的介绍list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向其前一个元素和后一个元素。list与…listlist的介绍list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。list的使用list中的接口比较多此处类似只需要掌握如何正确的使用然后再去深入研究背后的原理已达到可扩展的能力。以下为list中一些常见的重要接口。list的构造构造函数接口说明list()构造空的listlist(size_type n,const value_type valvalue_type())构造的list中包含n个值为val的元素list(const list x)拷贝构造函数list(inputlterator first,inputlierator last)用{firstlast}区间中的元素构造list// constructing lists
#include iostream
#include list
int main ()
{std::listint l1; // 构造空的l1std::listint l2 (4,100); // l2中放4个值为100的元素std::listint l3 (l2.begin(), l2.end()); // 用l2的[begin(), end()左闭右开的区间构造l3std::listint l4 (l3); // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] {16,2,77,29};std::listint l5 (array, array sizeof(array) / sizeof(int) );// 用迭代器方式打印l5中的元素for(std::listint::iterator it l5.begin(); it ! l5.end(); it)std::cout *it ;std::coutendl;// C11范围for的方式遍历for(auto e : l5)std::cout e ;std::coutendl;return 0;
}list iterator迭代器的使用函数声明接口说明beginend返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbeginrend返回第一个元素reverse_iterator即end位置返回最后一个元素下一个reverse_iterator即begin的位置【注意】begin与end为正向迭代器对迭代器执行操作迭代器向后移动rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动#include iostream
using namespace std;
#include list
void print_list(const listint l)
{// 注意这里调用的是list的 begin() const返回list的const_iterator对象for (listint::const_iterator it l.begin(); it ! l.end(); it){cout *it ;// *it 10; 编译不通过}cout endl;
}
int main()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素for (listint::iterator it l.begin(); it ! l.end(); it)cout *it ;cout endl;// 使用反向迭代器逆向打印list中的元素for (listint::reverse_iterator it l.rbegin(); it ! l.rend(); it)cout *it ;cout endl;return 0;
}list capacity函数声明接口说明empty检测list是否为空是返回true否则返回flasesize返回list中有效节点的个数list element access函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用list modifiers函数声明接口说明push_front在list首元素前插入值为vai的元素pop_front删除list中的第一个元素push_back在list尾部插入值为val的元素pop_back删除list中的最后一个元素insert在list position位置中插入值为val的元素erase删除list position位置的元素swap交换两个list中的元素clear清空list中的元素#include list
void PrintList(listint l)
{for (auto e : l)cout e ;cout endl;
}
//// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] { 1, 2, 3 };listint L(array, arraysizeof(array)/sizeof(array[0]));// 在list的尾部插入4头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}
//// insert /erase
void TestList3()
{int array1[] { 1, 2, 3 };listint L(array1, array1sizeof(array1)/sizeof(array1[0]));// 获取链表中第二个节点auto pos L.begin();cout *pos endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vectorint v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}
// resize/swap/clear
void TestList4()
{// 用数组来构造listint array1[] { 1, 2, 3 };listint l1(array1, array1sizeof(array1)/sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();coutl2.size()endl;
}list的迭代器失效前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代 器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给
其赋值l.erase(it); it;}
}
// 改正
void TestListIterator()
{ int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);}
}list的模拟实现namespace bite
{// List的节点类templateclass Tstruct ListNode{ListNode(const T val T()): _pPre(nullptr), _pNext(nullptr), _val(val){}ListNodeT* _pPre;ListNodeT* _pNext;T _val;};/*List 的迭代器迭代器有两种实现方式具体应根据容器底层数据结构实现1. 原生态指针比如vector2. 将原生态指针进行封装因迭代器使用形式与指针完全相同因此在自定义的类中必须实现以下
方法1. 指针可以解引用迭代器的类中必须重载operator*()2. 指针可以通过-访问其所指空间成员迭代器类中必须重载oprator-()3. 指针可以向后移动迭代器类中必须重载operator()与operator(int)至于operator--()/operator--(int)释放需要重载根据具体的结构来抉择双向链表可
以向前 移动所以需要重载如果是forward_list就不需要重载--4. 迭代器需要进行是否相等的比较因此还需要重载operator()与operator!()*/templateclass T, class Ref, class Ptrclass ListIterator{typedef ListNodeT* PNode;typedef ListIteratorT, Ref, Ptr Self;public:ListIterator(PNode pNode nullptr): _pNode(pNode){}ListIterator(const Self l): _pNode(l._pNode){}T operator*(){return _pNode-_val;}T* operator-(){return (operator*());}Self operator(){_pNode _pNode-_pNext;return *this;}Self operator(int){Self temp(*this);_pNode _pNode-_pNext;return temp;}Self operator--();Self operator--(int);bool operator!(const Self l){return _pNode ! l._pNode;}bool operator(const Self l){return _pNode ! l._pNode;}PNode _pNode;};templateclass Tclass list{typedef ListNodeT Node;typedef Node* PNode;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T value T()){CreateHead();for (int i 0; i n; i)push_back(value);}template class Iteratorlist(Iterator first, Iterator last){CreateHead();while (first ! last){push_back(*first);first;}}list(const listT l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换listT temp(l.cbegin(), l.cend());this-swap(temp);}listT operator(const listT l){this-swap(l);return *this;}~list(){clear();delete _pHead;_pHead nullptr;}///// List Iteratoriterator begin(){return iterator(_pHead-_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin(){return const_iterator(_pHead-_pNext);}const_iterator end(){return const_iterator(_pHead);}///// List Capacitysize_t size()const;bool empty()const;// List AccessT front();const T front()const;T back();const T back()const;// List Modifyvoid push_back(const T val){insert(begin(), val);}void pop_back(){erase(--end());}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){PNode pNewNode new Node(val);PNode pCur pos._pNode;// 先将新节点插入pNewNode-_pPre pCur-_pPre;pNewNode-_pNext pCur;pNewNode-_pPre-_pNext pNewNode;pCur-_pPre pNewNode;return iterator(pNewNode);}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){// 找到待删除的节点PNode pDel pos._pNode;PNode pRet pDel-_pNext;// 将该节点从链表中拆下来并删除pDel-_pPre-_pNext pDel-_pNext;pDel-_pNext-_pPre pDel-_pPre;delete pDel;return iterator(pRet);}void clear();void swap(ListT l);private:void CreateHead(){_pHead new Node;_pHead-_pPre _pHead;_pHead-_pNext _pHead;}private:PNode _pHead;};
}// 正向打印链表
templateclass T
void PrintList(const bite::listT l)
{auto it l.cbegin();while (it ! l.cend()){cout *it ;it;}cout endl;
}
// 测试List的构造
void TestList1()
{bite::listint l1;bite::listint l2(10, 5);PrintList(l2);int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };bite::listint l3(array, arraysizeof(array)/sizeof(array[0]));PrintList(l3);bite::listint l4(l3);PrintList(l4);l1 l4;PrintList(l1);PrintListReverse(l1);
}
// PushBack()/PopBack()/PushFront()/PopFront()
void TestList2()
{// 测试PushBack与PopBackbite::listint l;l.push_back(1);l.push_back(2);l.push_back(3);PrintList(l);l.pop_back();l.pop_back();PrintList(l);l.pop_back();cout l.size() endl;// 测试PushFront与PopFrontl.push_front(1);l.push_front(2);l.push_front(3);PrintList(l);l.pop_front();l.pop_front();PrintList(l);l.pop_front();cout l.size() endl;
}
void TestList3()
{int array[] { 1, 2, 3, 4, 5 };bite::listint l(array, arraysizeof(array)/sizeof(array[0]));auto pos l.begin();l.insert(l.begin(), 0);PrintList(l);pos;l.insert(pos, 2);PrintList(l);l.erase(l.begin());l.erase(pos);PrintList(l);// pos指向的节点已经被删除pos迭代器失效cout *pos endl;auto it l.begin();while (it ! l.end()){it l.erase(it);}cout l.size() endl;
}vectorvector的介绍vector是表示可变大小数组的序列容器。 就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。与其它动态序列容器相比deques, lists and forward_lists vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起lists和forward_lists统一的迭代器和引用更好。vector的使用https://cplusplus.com/reference/vector/vector/vector的定义构造函数声明接口说明vector()无参构造vector(size_type n,const value_type valvalue_type())构造并初始化n个valvector(const vector x);拷贝构造vector(inputlterator first,inputlterator last)使用迭代器进行初始化构造// constructing vectors
#include iostream
#include vector
int main ()
{// constructors used in the same order as described above:std::vectorint first; // empty vector of intsstd::vectorint second (4,100); // four ints with value 100std::vectorint third (second.begin(),second.end()); // iterating through secondstd::vectorint fourth (third); // a copy of third// 下面涉及迭代器初始化的部分我们学习完迭代器再来看这部分// the iterator constructor can also be used to construct from arrays:int myints[] {16,2,77,29};std::vectorint fifth (myints, myints sizeof(myints) / sizeof(int) );std::cout The contents of fifth are:;for (std::vectorint::iterator it fifth.begin(); it ! fifth.end(); it)std::cout *it;std::cout \n;return 0;
}vector iterator的使用说明iterator的使用接口说明beginend获取第一个数据位置的iterator/const_iterator获取最后一个数据下一个位置的iterator/const_iteratorrbeginrend获取最后一个数据位置的iterator/const_iterator获取第一个数据前一个位置的iterator/const_iterator#include iostream
#include vector
using namespace std;
void PrintVector(const vectorint v)
{// const对象使用const迭代器进行遍历打印vectorint::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}
int main()
{// 使用push_back插入4个数据vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器进行遍历打印vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;// 使用迭代器进行修改it v.begin();while (it ! v.end()){*it * 2;it;}// 使用反向迭代器进行遍历再打印vectorint::reverse_iterator rit v.rbegin();while (rit ! v.rend()){cout *rit ;rit;}cout endl;PrintVector(v);return 0;
}vector的空间增长问题容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize改变vector的sizereserve改变vector放入capacitycapacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为顺序表增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。// vector::capacity
#include iostream
#include vector
int main ()
{ size_t sz;std::vectorint foo;sz foo.capacity();std::cout making foo grow:\n;for (int i0; i100; i) {foo.push_back(i);if (sz!foo.capacity()) {sz foo.capacity();std::cout capacity changed: sz \n;}}
}
vs运行结果
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
g运行结果
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128// vector::reserve
#include iostream
#include vector
int main ()
{size_t sz;std::vectorint foo;sz foo.capacity();std::cout making foo grow:\n;for (int i0; i100; i) {foo.push_back(i);if (sz!foo.capacity()) {sz foo.capacity();std::cout capacity changed: sz \n;}}std::vectorint bar;sz bar.capacity();bar.reserve(100); // this is the only difference with foo abovestd::cout making bar grow:\n;for (int i0; i100; i) {bar.push_back(i);if (sz!bar.capacity()) {sz bar.capacity();std::cout capacity changed: sz \n;}}return 0;
}// vector::resize
#include iostream
#include vector
int main ()
{std::vectorint myvector;// set some initial content:for (int i1;i10;i)myvector.push_back(i);myvector.resize(5);myvector.resize(8,100);myvector.resize(12);std::cout myvector contains:;for (int i0;imyvector.size();i)std::cout myvector[i];std::cout \n;return 0;
}vector的增删查改函数声明接口说明push_back尾插pop_back头插find查找insert在position之前插入valerase删除position位置前的数据swap交换两个vector的数据空间operator[]像数组一一昂访问// push_back/pop_back
#include iostream
#include vector
using namespace std;
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, asizeof(a)/sizeof(int));vectorint::iterator it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;v.pop_back();v.pop_back();it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;return 0;
}// find / insert / erase
#include iostream
#include algorithm
#include vector
using namespace std;
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);// 在pos位置之前插入30v.insert(pos, 30);vectorint::iterator it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;pos find(v.begin(), v.end(), 3);// 删除pos位置的数据v.erase(pos);it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;return 0;
}// operator[]index 和 C11中vector的新式forauto的遍历
// vector使用这两种遍历方式是比较便捷的。
#include iostream
#include vector
using namespace std;
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 通过[]读写第0个位置。v[0] 10;cout v[0] endl;// 通过[i]的方式遍历vectorfor (size_t i 0; i v.size(); i)cout v[i] ;cout endl;vectorint swapv;swapv.swap(v);cout v data:;for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;cout swapv data:;for (size_t i 0; i swapv.size(); i)cout swapv[i] ;cout endl;// C11支持的新式范围for遍历for(auto x : v)cout x ;coutendl;return 0;
}vector迭代器失效的问题迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T*。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。对于vector可能会导致其迭代器失效的操作有会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等。#include iostream
using namespace std;
#include vector
int main()
{vectorint v{1,2,3,4,5,6};auto it v.begin();// 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间可能会引起扩容而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值可能会引起底层容量改变v.assign(100, 8);/*出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉
而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的
空间而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新
赋值即可。*/while(it ! v.end()){cout *it ;it;}coutendl;return 0;
} 指定位置元素的删除操作--erase#include iostream
using namespace std;
#include vector
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);// 删除pos位置的数据导致pos迭代器失效。v.erase(pos);cout *pos endl; // 此处会导致非法访问return 0;
}erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是没有元素的那么pos就失效了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效 了。vector的模拟实现#include iostream
using namespace std;
#include assert.h
// 注意这里namespace大家下去就不要取名为bit了否则出去容易翻车。^^
namespace bit
{
templateclass T
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator cbegin() const { return _start; }
const_iterator cend() const { return _finish; }// construct and destroy
vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{}
vector(int n, const T value T()): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{reserve(n);while (n--){push_back(value);}
}
// 如果使用iterator做迭代器会导致初始化的迭代器区间[first,last)只能是vector的迭代器
// 重新声明迭代器迭代器区间[first,last]可以是任意容器的迭代器
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{reserve(last - first);while (first ! last){push_back(*first);first;}
}
vector(const vectorT v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{reserve(v.capacity());iterator it begin();const_iterator vit v.cbegin();while (vit ! v.cend()){*it *vit;}
}
vectorT operator(vectorT v)
{swap(v);return *this;
}
~vector()
{delete[] _start;_start _finish _endOfStorage nullptr;
}// capacitysize_t size() const { return _finish - _start; }size_t capacity() const { return _endOfStorage - _start; }bool empty() const {return _first _finish; }
void reserve(size_t n)
{if (n capacity()){size_t oldSize size();T* tmp new T[n];// 这里直接使用memcpy?//if (_start)// memcpy(tmp, _start, sizeof(T)*size);if (_start){for (size_t i 0; i oldSize; i)tmp[i] _start[i];}_start tmp;_finish _start size;_endOfStorage _start n;}
}
void resize(size_t n, const T value T())
{// 1.如果n小于当前的size则数据个数缩小到nif (n size()){_finish _start n;return;}// 2.空间不够则增容if (n capacity())reserve(n);// 3.将size扩大到niterator it _finish;iterator _finish _start n;while (it ! _finish){*it value;it;}
}///access///T operator[](size_t pos){return _start[pos];}const T operator[](size_t pos)const {return _start[pos];}///modify/
void push_back(const T x){insert(end(), x);}
void pop_back(){erase(--end());}void swap(vectorT v)
{swap(_start, v._start);swap(_finish, v._finish);swap(_endOfStorage, v._endOfStorage);
}iterator insert(iterator pos, const T x)
{assert(pos _finish);// 空间不够先进行增容if (_finish _endOfStorage){size_t size size();size_t newCapacity (0 capacity())? 1 : capacity() * 2;reserve(newCapacity);// 如果发生了增容需要重置pospos _start size;}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;
}
// 返回删除数据的下一个数据
// 方便解决:一边遍历一边删除的迭代器失效问题
iterator erase(Iterator pos)
{// 挪动数据进行删除iterator begin pos 1;while (begin ! _finish) {*(begin - 1) *begin;begin;}--_finish;return pos;
}
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
}
// constructing vectors
void TestVector1()
{// constructors used in the same order as described above:bite::vectorint first; // empty vector of ints
bite::vectorint second(4, 100); // four ints with value
100bite::vectorint third(second.Begin(), second.End()); // iterating through
secondbite::vectorint fourth(third); // a copy of third// the iterator constructor can also be used to construct from arrays:int myints[] { 16, 2, 77, 29 };bit::vectorint fifth(myints, myints sizeof(myints) / sizeof(int));std::cout The contents of fifth are:;for (bit::vectorint::iterator it fifth.begin(); it ! fifth.end(); it)std::cout *it ;std::cout endl;// 测试T是string时拷贝问题bit::vectorstring strV;strV.PushBack(1111);strV.PushBack(2222);strV.PushBack(3333);strV.PushBack(4444);for (size_t i 0; i strV.size(); i){cout strV[i] ;}cout endl;
}
//vector iterator的使用
void PrintVector(const bite::vectorint v)
{// 使用const迭代器进行遍历打印bit::vectorint::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}
void TestVector2()
{// 使用push_back插入4个数据bite::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);PrintVector(v);// 使用迭代器进行修改
auto it v.begin();while (it ! v.end()){*it * 2;it;}PrintVector(v);// 这里可以看出C11支持iterator及接口就支持范围forfor(auto e : v)coute ;
}
// find / insert / erase
void TestVector3()
{int a[] { 1, 2, 3, 4 };bite::vectorint v(a, a sizeof(a) / sizeof(a[0]));// 使用find查找3所在位置的iteratorauto pos find(v.begin(), v.end(), 3);// 在pos位置之前插入30v.insert(pos, 30);PrintVector(v);// 删除pos位置的数据pos find(v.begin(), v.end(), 3);v.Erase(pos);PrintVector(v);
}
// iterator失效问题
void TestVector4()
{int a[] { 1, 2, 3, 4 };bite::vectorint v(a, a sizeof(a) / sizeof(a[0]));// 删除pos位置的数据导致pos迭代器失效auto pos find(v.begin(), v.end(), 3);v.erase(pos);cout *pos endl; // 此处会导致非法访问// 在pos位置插入数据导致pos迭代器失效。// insert会导致迭代器失效是因为insert可// 能会导致增容增容后pos还指向原来的空间而原来的空间已经释放了。pos find(v.begin(), v.end(), 3);v.insert(pos, 30);cout *pos endl; // 此处会导致非法访问// 实现删除v中的所有偶数// 下面的程序会崩溃掉如果是偶数erase导致it失效// 对失效的迭代器进行it会导致程序崩溃auto it v.begin();while (it ! v.end()){if (*it % 2 0)v.erase(it);it;}// 以上程序要改成下面这样erase会返回删除位置的下一个位置it v.begin();while (it ! v.end()){if (*it % 2 0)it v.erase(it);elseit;}
}list与vector对比vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素效率o1不支持随机访问效率on插入和删除任意位置插入和删除效率低需要搬移元素时间复杂度为on擦汗如是可能需要增容开辟新的空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率不高不需要搬移元素时间复杂度为01空间利用率底层连续空间不易形成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生态指针对原生态指针结点指针进行封装迭代器失效再插入元素时要给所有迭代器重新赋值因为插入元素可能会导致重新扩容导致迭代器失效删除时当前迭代器需要重新赋值插入元素不会导致迭代器失效删除会导致失效其他不受影响使用场景需要高效率存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问
