深圳进入政策最新/seo零基础教学
list
list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。
list的使用
list中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展的能力。以下为list中一些常见的重要接口。
list的构造
构造函数 | 接口说明 |
list() | 构造空的list |
list(size_type n,const value_type& val=value_type()) | 构造的list中包含n个值为val的元素 |
list(const list& x) | 拷贝构造函数 |
list(inputlterator first,inputlierator last) | 用{first,last}区间中的元素构造list |
// constructing lists
#include <iostream>
#include <list>
int main ()
{std::list<int> l1; // 构造空的l1std::list<int> l2 (4,100); // l2中放4个值为100的元素std::list<int> l3 (l2.begin(), l2.end()); // 用l2的[begin(), end())左闭右开的区间构造l3std::list<int> l4 (l3); // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = {16,2,77,29};std::list<int> l5 (array, array + sizeof(array) / sizeof(int) );// 用迭代器方式打印l5中的元素for(std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)std::cout << *it << " ";std::cout<<endl;// C++11范围for的方式遍历for(auto& e : l5)std::cout<< e << " ";std::cout<<endl;return 0;
}
list iterator(迭代器)的使用
函数声明 | 接口说明 |
begin+end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
rbegin+rend | 返回第一个元素reverse_iterator,即end位置,返回最后一个元素下一个reverse_iterator,即begin的位置 |
【注意】
begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动
#include <iostream>
using namespace std;
#include <list>
void print_list(const list<int>& l)
{// 注意这里调用的是list的 begin() const,返回list的const_iterator对象for (list<int>::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 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素for (list<int>::iterator it = l.begin(); it != l.end(); ++it)cout << *it << " ";cout << endl;// 使用反向迭代器逆向打印list中的元素for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)cout << *it << " ";cout << endl;return 0;
}
list capacity
函数声明 | 接口说明 |
empty | 检测list是否为空,是返回true,否则返回flase |
size | 返回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(list<int>& l)
{for (auto& e : l)cout << e << " ";cout << endl;
}
//=====================================================================================
====
// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] = { 1, 2, 3 };list<int> L(array, array+sizeof(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 };list<int> L(array1, array1+sizeof(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)区间中的元素vector<int> 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 };list<int> l1(array1, array1+sizeof(array1)/sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout<<l2.size()<<endl;
}
list的迭代器失效
前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代 器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(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 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}
list的模拟实现
namespace bite
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};/*List 的迭代器迭代器有两种实现方式,具体应根据容器底层数据结构实现:1. 原生态指针,比如:vector2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下
方法:1. 指针可以解引用,迭代器的类中必须重载operator*()2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可
以向前 移动,所以需要重载,如果是forward_list就不需要重载--4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()*/template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, 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;};template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, 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 Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换list<T> temp(l.cbegin(), l.cend());this->swap(temp);}list<T>& operator=(const list<T> 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(List<T>& l);private:void CreateHead(){_pHead = new Node;_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}private:PNode _pHead;};
}
// 正向打印链表
template<class T>
void PrintList(const bite::list<T>& l)
{auto it = l.cbegin();while (it != l.cend()){cout << *it << " ";++it;}cout << endl;
}
// 测试List的构造
void TestList1()
{bite::list<int> l1;bite::list<int> l2(10, 5);PrintList(l2);int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };bite::list<int> l3(array, array+sizeof(array)/sizeof(array[0]));PrintList(l3);bite::list<int> l4(l3);PrintList(l4);l1 = l4;PrintList(l1);PrintListReverse(l1);
}
// PushBack()/PopBack()/PushFront()/PopFront()
void TestList2()
{// 测试PushBack与PopBackbite::list<int> 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::list<int> l(array, array+sizeof(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;
}
vector
vector的介绍
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& val=value_type()) | 构造并初始化n个val |
vector(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::vector<int> first; // empty vector of intsstd::vector<int> second (4,100); // four ints with value 100std::vector<int> third (second.begin(),second.end()); // iterating through secondstd::vector<int> fourth (third); // a copy of third// 下面涉及迭代器初始化的部分,我们学习完迭代器再来看这部分// the iterator constructor can also be used to construct from arrays:int myints[] = {16,2,77,29};std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );std::cout << "The contents of fifth are:";for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
vector iterator的使用说明
iterator的使用 | 接口说明 |
begin+end | 获取第一个数据位置的iterator/const_iterator,获取最后一个数据下一个位置的iterator/const_iterator |
rbegin+rend | 获取最后一个数据位置的iterator/const_iterator,获取第一个数据前一个位置的iterator/const_iterator |
#include <iostream>
#include <vector>
using namespace std;
void PrintVector(const vector<int>& v)
{// const对象使用const迭代器进行遍历打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}
int main()
{// 使用push_back插入4个数据vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器进行遍历打印vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;// 使用迭代器进行修改it = v.begin();while (it != v.end()){*it *= 2;++it;}// 使用反向迭代器进行遍历再打印vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;PrintVector(v);return 0;
}
vector的空间增长问题
容量空间 | 接口说明 |
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize | 改变vector的size |
reserve | 改变vector放入capacity |
capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,顺序表增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化,影响size。
// vector::capacity
#include <iostream>
#include <vector>
int main ()
{ size_t sz;std::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i=0; i<100; ++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::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i=0; i<100; ++i) {foo.push_back(i);if (sz!=foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}std::vector<int> bar;sz = bar.capacity();bar.reserve(100); // this is the only difference with foo abovestd::cout << "making bar grow:\n";for (int i=0; i<100; ++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::vector<int> myvector;// set some initial content:for (int i=1;i<10;i++)myvector.push_back(i);myvector.resize(5);myvector.resize(8,100);myvector.resize(12);std::cout << "myvector contains:";for (int i=0;i<myvector.size();i++)std::cout << ' ' << myvector[i];std::cout << '\n';return 0;
}
vector的增删查改
函数声明 | 接口说明 |
push_back | 尾插 |
pop_back | 头插 |
find | 查找 |
insert | 在position之前插入val |
erase | 删除position位置前的数据 |
swap | 交换两个vector的数据空间 |
operator[] | 像数组一一昂访问 |
// push_back/pop_back
#include <iostream>
#include <vector>
using namespace std;
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a+sizeof(a)/sizeof(int));vector<int>::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 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 在pos位置之前插入30v.insert(pos, 30);vector<int>::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 和 C++11中vector的新式for+auto的遍历
// vector使用这两种遍历方式是比较便捷的。
#include <iostream>
#include <vector>
using namespace std;
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> 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;vector<int> 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;// C++11支持的新式范围for遍历for(auto x : v)cout<< x << " ";cout<<endl;return 0;
}
vector迭代器失效的问题
迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装,比如:vector的迭代器就是原生态指针T*。因此迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有:
会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等。
#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> 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;}cout<<endl;return 0;
}
指定位置元素的删除操作--erase
#include <iostream>
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::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
{
template<class 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]可以是任意容器的迭代器
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{reserve(last - first);while (first != last){push_back(*first);++first;}
}
vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{reserve(v.capacity());iterator it = begin();const_iterator vit = v.cbegin();while (vit != v.cend()){*it++ = *vit++;}
}
vector<T>& operator=(vector<T> 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(vector<T>& 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::vector<int> first; // empty vector of ints
bite::vector<int> second(4, 100); // four ints with value
100bite::vector<int> third(second.Begin(), second.End()); // iterating through
secondbite::vector<int> fourth(third); // a copy of third// the iterator constructor can also be used to construct from arrays:int myints[] = { 16, 2, 77, 29 };bit::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));std::cout << "The contents of fifth are:";for (bit::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)std::cout <<*it<< " ";std::cout << endl;// 测试T是string时,拷贝问题bit::vector<string> 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::vector<int>& v)
{// 使用const迭代器进行遍历打印bit::vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}
void TestVector2()
{// 使用push_back插入4个数据bite::vector<int> 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);// 这里可以看出C++11支持iterator及接口,就支持范围forfor(auto e : v)cout<<e<<" ";
}
// find / insert / erase
void TestVector3()
{int a[] = { 1, 2, 3, 4 };bite::vector<int> 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::vector<int> 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);else++it;}
}
list与vector对比
vector | list | |
底层结构 | 动态顺序表,一段连续空间 | 带头结点的双向循环链表 |
随机访问 | 支持随机访问,访问某个元素效率o(1) | 不支持随机访问,效率o(n) |
插入和删除 | 任意位置插入和删除效率低,需要搬移元素,时间复杂度为o(n),擦汗如是可能需要增容:开辟新的空间,拷贝元素,释放旧空间,导致效率更低 | 任意位置插入和删除效率不高,不需要搬移元素,时间复杂度为0(1) |
空间利用率 | 底层连续空间不易形成内存碎片,空间利用率高,缓存利用率高 | 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低 |
迭代器 | 原生态指针 | 对原生态指针(结点指针)进行封装 |
迭代器失效 | 再插入元素时,要给所有迭代器重新赋值,因为插入元素可能会导致重新扩容,导致迭代器失效,删除时当前迭代器需要重新赋值 | 插入元素不会导致迭代器失效,删除会导致失效,其他不受影响 |
使用场景 | 需要高效率存储,支持随机访问,不关心插入删除效率 | 大量插入和删除操作,不关心随机访问 |
相关文章:

【C++】30h速成C++从入门到精通(STL容器listvector)
listlist的介绍list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。list与…...

操作系统---存储管理
存储管理 操作系统将外存的文件调入到内存中,以便CPU调用,如果调用的内容不在内存中,则会产生缺页中断;产生缺页中断后,这事需要从外存调数据到内存中,然后CPU接着从断点继续调用内存中的数据;在…...

华为OD机试题 - 好朋友(JavaScript)| 含思路
华为OD机试题 最近更新的博客使用说明本篇题解:好朋友题目输入输出示例一输入输出说明示例二输入输出说明Code解题思路华为OD其它语言版本最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典...

socket本地多进程通信基本使用方法和示例
目录 前言: socket是什么 socket基本原理框图 socket基本函数 1 socket() 函数 2 bind()函数 3 connect()函数 4 listen() 函数 5 accept() 函数 6 read() write() send() recv()函数 7 close()函数 8 字节序转换(hton) 示例代码 …...

Python 算法交易实验51 Step2 Signals 信号生成
说明 不可不读书 先从经典的一些超简单信号开始 使用移动平均指标SMA(算术) 给出了信号的产生方法,还有一些测算结果,反正看起来都是盈利的 首先使用离线方法实验一组结果,然后就使用ADBS来进行类似的处理。 内容 1 原理分析…...

app上架专用软著认证电子版权在主流应用商店的使用说明2023年最新版
软著认证电子版权在主流应用商店的使用说明 目录 一、 华为应用商店 二、 腾讯应用宝 三、 小米开放平台 小米应用提交: 小米游戏提交: 四、 OPPO开放平台 OPPO应用提交: OPPO游戏(App)提交: OPPO小游戏(快应…...

[Mybatis2]Mapper代理开发
文章目录 问题情境 代理开发 遵循的三条原则 1.定义与SQL映射文件同名的Mapper接口,并且将Mapper接口和SQL映射文件放置在同一目录下 2.设置SQL映射文件的namespace属性为Mapper接口的全限定名 3.在Mapper接口中定义方法,方法名就是SQL映射文件中sql…...

第十一届蓝桥杯大赛青少组国赛Python真题2
第十一届蓝桥杯大赛青少组Python 真题 第二题 提示信息: 杨辉三角形,是二项式系数在三角形中的一种几何排列。中国南宋数学家杨辉在 1261 年所著的《详 解九章算法》一书有明确记载。欧洲数学家帕斯卡在 1654 年发现这一规律,所以又叫做帕斯卡…...

创建springboot项目文件报红
目录 一、遇到问题 二、出现这个问题的原因 三、解决办法 三种方法 四、操作步骤 一、遇到问题 创建springboot项目的时候,会发现一些重要文件都变成红色了,但是不影响程序的运行。只是看起来会有点不舒服。 二、出现这个问题的原因 因为这个spr…...

gma 地理空间绘图:(1) 绘制简单的世界地图-3.设置地图框
内容回顾 gma 地理空间绘图:(1) 绘制简单的世界地图-1.地图绘制与细节调整 gma 地理空间绘图:(1) 绘制简单的世界地图-2.设置经纬网 方法 SetFrame(FrameColor ‘black’, FrameWidth 0.6, ShowFrame True, ShowLeft True, ShowBottom True, Sho…...

Java Web 实战 03 - 多线程基础(2)
Java Web 实战 03 - 多线程基础篇 2二 . Thread类常见方法2.1 Thread 的常见构造方法2.2 Thread 的几个常见属性getId()getName()getState()getPriority()isDaemon()案例 : 实现 getId()、getName()、 getState()、getPriority()、isDaemon()、isAlive()2.3 启动一个线程-start…...

Linux命令·cat
cat命令的用途是连接文件或标准输入并打印。这个命令常用来显示文件内容,或者将几个文件连接起来显示,或者从标准输入读取内容并显示,它常与重定向符号配合使用。 1.命令格式:cat [选项] [文件]...2.命令功…...

WPF WrapPanel、UniformGrid、DockPanel介绍
WPF WrapPanel、UniformGrid、DockPanel介绍 WrapPanel WrapPanel , 具有在有限的容器范围内, 可以自动换行, 或者换列处理。具体则取决于WrapPanel的排列方式 (Orientation)。 Orientation"Horizontal"时各控件从左至右罗列,当面板长度不够时ÿ…...

华为OD机试题 - TLV 编码(JavaScript)| 含思路
华为OD机试题 最近更新的博客使用说明本篇题解:TLV 编码题目输入输出描述示例一输入输出说明Code解题思路华为OD其它语言版本最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流…...

【华为OD机试真题java、python、c++】开心消消乐【2022 Q4 100分】(100%通过)
代码请进行一定修改后使用,本代码保证100%通过率。本文章提供java、python、c++三种代码 题目描述 给定一个N行M列的二维矩阵,矩阵中每个位置的数字取值为0或1。矩阵示例如: 1100 0001 0011 1111 现需要将矩阵中所有的1进行反转为0,规则如下: 1) 当点击一个1时,该1便被…...

IDEA搭建vue-cli | vue-router | 排错思路、Webpack、Axios、周期、路由、异步、重定向
💗wei_shuo的个人主页 💫wei_shuo的学习社区 🌐Hello World ! Vue.js概述 Vue 是一套用于构建用户界面的渐进式JavaScript框架。 与其它大型框架不同的是,Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层…...

HashSet原理
HashSet原理HashSet原理1.概述2.底层代码3.原理图解4.总结4.1: 1.7原理总结4.2: 1.8原理总结HashSet原理 1.概述 HashSet 实现 Set 接口,由哈希表(实际上是一个 HashMap 实例)支持。它不保证 set 的 迭代顺序;特别是它不保证…...

【C#进阶】C# 特性
序号系列文章10【C#基础】C# 正则表达式11【C#基础】C# 预处理器指令12【C#基础】C# 文件与IO文章目录前言1,特性的概念1.1 特性的属性1.2 特性的用途2,特性的定义2.1 特性参数2.2 特性目标3,预定义特性3.1 AttributeUsage3.2 Conditional3.2…...

Java速成篇-Day01笔记
提示:这里只记录我个人不熟悉的知识,并非所有内容 笔记目录课程:04-第一行代码① jshell② 对象.方法课程:05-第一份源码① Java开发程序的流程② 入口方法课程:06-常见问题-中文乱码① 乱码原因② 解决方法课程&#…...

从源码开始精通spring-security1
参考b站up主:传送门 前沿: 本章:spring-security 重要的成员 WebSecurity、HttpSecurity、SecurityBuilder、SecurityFilterChain、FilterChainProxy 重点:WebSecurity、HttpSecurity 他们都实现了 SecurityBuilder 接口 用来构建对象 WebSe…...

你应该优化的JavaScript代码,以及前端工程师日常使用的小技巧。使之更加简洁,可读性更强,更易维护。
本文主要是分享一下平时前端工程师,在写前端代码过程中的一些代码优化,以及使用的一些小技巧,来使我们的代码更加简洁,可读性更强,更易维护。 1. 字符串的自动匹配(includes的优化) includes是…...

自动化测试
文章目录前言一、什么是自动化测试?一个简单的自动化实例二、自动化测试的分类1.接口自动化测试2.UI自动化测试(界面测试)移动端自动化测试web端自动化测试(主要学习)三、selenium工具1.为什么选择selenium作为web自动…...

leetcode-每日一题-807(中等,数组)
正常情况第一眼看这道题,看懂意思的话很简单就可以解出来。给你一座由 n x n 个街区组成的城市,每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ,其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。城市的…...

【Linux】Linux项目自动化构建工具make makefile
文章目录1. 背景2.实例3.原理4.项目清理5. 文件属性中的三个时间6. Linux下第一个小程序——进度条6.1 前置知识1:缓冲区6.2前置知识2:回车换行6.3进度条的实现7 Linux下git的”三板斧“1. 背景 一个工程中的源文件不计其数,其按类型、功能、…...

华为OD机试题 - IPv4 地址转换成整数(JavaScript)| 含思路
华为OD机试题 最近更新的博客使用说明本篇题解: IPv4 地址转换成整数题目输入输出示例一输入输出说明示例一输入输出说明Code解题思路华为OD其它语言版本最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | …...

spring整合通用mapper
1.使用通用mapper可以更快速的进行数据库的增删查改操作,加入springboot的管理,常规的SQL都可以复用 2.整合 a)引入依赖 <dependencies><dependency><groupId>tk.mybatis</groupId><artifactId>mapper-spring-boot-starter</artifactId>…...

一天什么时间发抖音浏览量高?5个抖音最佳发布时间段
抖音作为现在一款现象级的软件,已经不知不觉地影响着我们生活的方方面面。那抖音想要被更多人看到,就需要掐准哪些时间活跃数最多,今天就来和大家分享一下一天什么时间发抖音浏览量高,又该如何抓住最佳投放契机呢?一、一天什么时…...

华为OD机试题 - 关联子串(JavaScript)| 含思路
华为OD机试题 最近更新的博客使用说明本篇题解:关联子串题目输入输出示例一输入输出说明示例二输入输出说明Code解题思路华为OD其它语言版本最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典...

【代码随想录训练营】【Day33休息】【Day34】第八章|贪心算法|1005.K次取反后最大化的数组和|134. 加油站|135. 分发糖果
K 次取反后最大化的数组和 题目详细:LeetCode.1005 这道题比较简单,这里直接给出贪心策略: 局部最优解: 按照 负数 > 0 > 正数 的优先级次序,依次对nums中的较小数值进行取反因为负负得正,负值越小…...

<c++> const 常量限定符
文章目录什么是 const 常量限定符const 的初始化const 的默认作用域const 的引用例外情况const 与指针const指针的声明指向 const 的指针const指针指向 const 的 const指针什么是 const 常量限定符 Q:什么是 const 常量限定符? A:const名叫常…...