-
STL五大件 标准模板库
-
vector容器：
-
vector 容器：构造函数也能接受迭代器！
-
重载cout输出流格式
-
vector 迭代器模式
-
迭代器的精髓:把连续的访问映射到链表的不连续访问上 首迭代器+尾迭代器
STL五大件 标准模板库
vector 就是一个连续的数据 C++11 std::vector a ={1,4,2,6,7}; 可以使用花括号来定义
容器的功能就是存储数据 迭代器的功能就是指向数据，并且可以实现前后移动（指针）算法和容器的接口的存在
auto n = std::count_if(a.begin(),a.end(),std::bind2nd(std::less<int>),4);
count\_if 数数 a.begin 指向第一个元素 迭代器类似于指针 可以++ 指向下一个元素
a.end指向最后一个元素的下一位
构成一个区间 less<int>仿函数（functor）
int 类型的小于符号 小于int的数值 会给int类型的数比较一个大小
bind2nd把它的第二个参数始终绑定为4 hascode <4）
allocator 分配器 用于vector第二个参数 或最后一个参数 如：
std::vector<int ,std::allcoator<int>> a ={1,4,,2,8,5,7};
vector容器：
vector功能是长度可变的数组， 身在栈上 里面的数据存储在堆上 因为栈不可动态扩容
vector 里面有3个指针
第一个指针是指向堆上的地址（起始地址）
第二个指针标志着结束位
第三个指针就是实际有元素的地址
vector 声明初始化
vector是一个模板类，第一个模板参数就是数组里元素的类型
如：声明一个元素是int类型的动态数组a; vector<int> a;
vector 可以在构造时指定初始长度 vector(size_t n)
例如，要创建一个长度为4元素为 0 的int型数组 vector<int>a(4);
之后可以通过 a.size()获取数组的长度
explicit vector(size_t n); 显式构造函数
explicit vector （size_t n ,int const &val);
vector初始化表达式的等号可以不写
vector<int>a ={4,12,32,4};
vector<int>a{4,12,32,4};
vector<int>a{4}; 代表你创建了一个长度为1只有一个元素4的数组。 vector(initializer_list<int>list);
vector<int>a(4); 得到长度为4元素为0的数组
对于只能用花括号初始化的类成员来说就有很大问题 vector<int>a{4};
会得到一个长度为1只有一个元素4的数组
struct C{
vector<int> a = vector<int>(4);
};
可以用这种写法强制调用显示构造函数 vector<int> a = vector<int>(4);
得到长度为4元素为0的数组
explicit vector （size_t n ,int const &val);
显式构造函数还可以指定第二个参数，这样就可以用0以外的值初始化整个数组了
例如：创建4个233组成的数组 vector<int>a(4,233);
等价于 vector<int> a = {233.233,233,233}
vector 容器 ：push_back
void push_back(int const &val);
void push_back(int &&val); C++11新增
push_back函数可以在数组的末尾追加一个数。
例如： vector<int>a = {1,2}; a.push_back(3); 等价于vector<int>a = {1,2,3};
vector 容器 ：push_back的问题
int main()
{
vector<int> a ;
for(int i =0 ; i<100;i++)
{
a.push_back(i);
}
cout<<a<<endl;
return 0;
}
由于不知道你会push_back多少个元素，vector的初始容量为0
push_back和resize一样，每次遇到容量不足时，都会扩容2倍。
这也体现出了实际容量(capacity)数组大小(size)分离的好处
当容量不足的时候就可以一次性扩容2倍，只需重新分配logn次，移动元素2N-1次
malloc是按照字节来计算 即char类型大小
p=malloc(1000);
q=malloc(10);
memcpy(q,p);
free(p);
vector容器：push_back的问题，reserve解决
int main()
{
vector<int> a ;
a.reserve(100);
for(int i =0 ; i<100;i++)
{
a.push_back(i); // i是int类型 reserver（100） 相当于400
}
cout<<a<<endl;
return 0;
}
因此，如果你早知道要插入元素的数量，可以调用reserve函数先预留那么多的容量，等待接下来的推入。
这样之后push_back时，就不会一次次地扩容两倍慢慢成长到128 避免重新分配内存和移动元素，更高效。
比如这里我们可以提前知道循环会执行100次，因此reserve（100）就可以了
可以看到只有一次malloc（400），之后malloc(1024)是cout造成的
vector容器：insert函数
iterator insert(const_iterator pos, int const &val);
iterator insert(const_iterator pos, int &val);//C++11
iteratot insert(const_iterator pos,size_t n , int const &val); (插入位置，重复多少次，插入的值)
iterator insert(const_iterator pos, initalizer_list<int> lst); //初始化列表对应的类型只能是initalizer_list<int> list
int main()
{
vector<int> a ={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
a.insert(a.begin(),233);
cout<<"a="<<a<<endl;
return 0;
}
push_back可以往尾部插入数据，insert可以往头部插入数据
insert第一个参数是插入的位置(迭代器表示)第二个参数是要插入的值。
这个函数的复杂度为O(n)，n是从插入位置pos到数组末尾end的距离，他会插入位置后方的元素整体向后移动一格，是比较低效的为了尽可能高效尽量在尾部插入元素
如果需要高效的头部插入，可以考虑用deque容器，他有高效的push_front函数代替，insert在容量不足时，同样会造成重新分配以求扩容，会移动其中所有元素，这时之前保存的迭代器都会失效的。
iterator insert(const_iterator pos, int const &val);
vector容器：insert函数,插到指定的元素前方
插入到一个特定位置，可以用迭代器的加法来获取某一位置的迭代器
例如a.begin()+3就会指向第三个元素，那么用这个作为insert的参数就会把233这个值插回到第三个元素的位置之前。
例如a.end()可以插入到最末尾appendd，a.end()-1则是插入到倒数第一个元素前。
例如 a.insrt(插入的位置,重复次数,插入的数据);
int main()
{
vector<int> a ={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
a.insert(a.begin()+3,233);
a.insert(a.end()-2,4,233);
a.insert(a.end()-2,233);
cout<<"a="<<a<<endl;
return 0;
}
vector容器：insert函数,直接插入一个初始化列表
iterator insert(const_iterator pos, initalizer_list<int> lst);
insert还可以直接插入一个{}的列表！这个花括号{}形成的列表就是传说中的初始化列表(initializer-list)是C++11新增的功能类 std::initializer_list<int>
a.insert(插入位置，{插入值1，插入值2，.....};
这个最坏的复杂度也是O(n)并且因为其内部预先知道了要插入列表的长度，会一次性完成扩容，比重复调用push_back重复扩容高效很多。
int main()
{
vector<int> a ={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
a.insert(a.begin(),{233,666,984,221});
cout<<"a="<<a<<endl;
return 0;
}
vector容器：insert函数,直接插入另一个vector？
如果你试图用一个vector作为这个参数，就会出错！报错会说因为vector和initializer_list不是同一个类型
那么如何插入另一个vector，或者说，把a和b这个两个数组合并起来呢?
int main()
{
vector<int> a ={1,2,3,4,5,6} ;
vector<int> b ={12,23,34,45,52,16} ;
cout<<"a="<<a<<endl;
cout<<"b="<<b<<endl;
a.insert(a.begin(), b);
cout<<"a="<<a<<endl;
return 0;
}
报错信息：
vector容器：insert函数，插入另一个vector需要他的两个迭代器
template<class It> //这里It可以是其他容器的迭代器类型
iterator insert(const_iterator pos,It beg,It end);
C++迭代器思想是，
容器和算法之间的交互不是通过容器对象本身，而是他的迭代器
因此insert设计时就决心不支持直接接受vector做参数，而是接受他的两个迭代器组成的区间！好处有：
1.可以批量插入才能够来自另一个不同类型的容器，例如list,只要元素类型相等，且符合迭代器规范
2. 可自由选择对方容器的一个子区间(通过迭代器加减法)内的元素来插入，而不是死板的只能全部插入。
int main()
{
vector<int> a ={1,2,3,4,5,6} ;
vector<int> b ={12,23,34,45,52,16} ;
cout<<"a="<<a<<endl;
cout<<"b="<<b<<endl;
a.insert(a.begin(), b.begin(),b.end()); //从头部插入 会把b插入在原先a元素之前，相当于牌神的a=b+a;
a.insert(a.end(), b.begin(),b.end()); //从尾部插入 把b插入到a元素之后，相当于a+=b; 性能好，只要容量组后无需移动a的全部元素
cout<<"a="<<a<<endl;
return 0;
}
对方容器也可以是不同类型的，最底线的要求只要他的迭代器有++和*运算符即可。
例如：list::iterator
int main()
{
vector<int> a ={1,2,3,4,5,6} ;
list<int> b ={12,23,34,45,52,16} ;
cout<<"a="<<a<<endl;
a.insert(a.begin(), b.begin(),b.end()); //成员函数
cout<<"a="<<a<<endl;
return 0;
}
string s;
vector<char> v; //把一个string转换为vector 这两个东西里面的值是一样的 assign接受任意迭代器作为参数
v.assign(s.begin(),s.end());
vector容器：insert函数，作为数据源的对方容器可以是不同类型
template<class T>auto begin(T &&t);
template<class T>AUTO end(T &&t);
对方容器还可以是个C语言风格的数组，因为C语言类型没有办法加成员函数begin和end
可以用std::begin和std::end这两个全局函数代替
如果用了using namespace std 可以不写前缀std:: 还有全局函数std::size()获取它的长度 和std::data()
这两个函数会对于具有begin和end成员函数的容器直接调用
对于C语言数组则被特化为返回b和b+sizeof(b)/sizeof(b[0])
如果是C语言数组 b.begin()先判断是否合法 不合法则让begin(b) ->b end(b)->b+szie(b);
int main()
{
vector<int> a ={1,2,3,4,5,6} ;
int b[] ={12,23,34,45,52,16} ;
cout<<"a="<<a<<endl;
a.insert(a.begin(), std::b.begin(),std::b.end()); //成员函数
cout<<"a="<<a<<endl;
return 0;
}
vector 容器：构造函数也能接受迭代器！
template<class It>
explicit vector(It beg,It end);
其实vector的构造函数也接受一堆迭代器做参数，来初始化其中的元素，同样可以是不同容器的迭代器对象，只要具有++和*即可
int main()
{
int b[] ={12,23,34,45,52,16} ;
vector<int>a(std::begin(b),std::end(b));
cout<<"a="<<a<<endl;
return 0;
}
vector容器：assign函数
template<class It>
void assign(It beg,It end);
void assign(size_t n ,int const&val);
void assign(initializer_list<int> val);
vector<int>&operator(initializer_list<int> val);
vector<int>&operator(vector<int>const& val);
vector<int>&operator(vector<int> &&val);
assign这个成员函数也能够在后期把元素覆盖进去，和insert不同的是，他会把原来的数组完全覆盖掉，变成一个新的数组。
a.assign(beg,end)基本和a=vector<int>(beg,end)等价，唯一的区别是后者会重新分配内存，而前者会保留原来的容量不会释放掉。
int main()
{
vector<int>a={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
int b[] ={12,23,34,45,52,16} ;
a.assign(std::begin(b).std::end(b));
cout<<"a="<<a<<endl;
return 0;
}
void assign(size_t n ,int const&val);这个重载，可以把vector批量填满一个特定的值，重复的次数(度)也是参数里指定。
a.assign(n,val)基本和a=vector<int>(n,val)等价，唯一的区别是后者会重新分配内存，而前者会保留原来的容量。
int main()
{
vector<int>a={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
a.assign(4,233);
cout<<"a="<<a<<endl;
return 0;
}
void assign(initializer_list<int> val);
vector<int>&operator(initializer_list<int> val);
vector<int>&operator(vector<int>const& val);
vector<int>&operator(vector<int> &&val);
assign还可以直接接受一个初始化列表作为参数
a.assign({x,y,...})和a={x,y,...}完全等价,都会保留原来的容量。
而和a=vector<int>{x,y,....}就不等价了，这个会重新分配内存。
int main()
{
vector<int>a={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
a.assign(233,666,985,211});
cout<<"a="<<a<<endl;
a={2 ,11};
cout<<"a="<<a<<endl;
cout<<"a.capacity()="<<a.capacity()<<endl;
a= vector<int>{2,11};
cout<<"a.capacity()="<<a.capacity()<<endl;
return 0;
}
vector 容器 ：pop_back back front
void pop_back();
int &back();
int const &back();
int &front();
int const &front();
void pop_back(); 函数返回类型是void没有返回值如果需要获取删除的值可以在pop_back之前先通过back()获取末尾元素的值实现pop的效果
pop_back函数在数组的末尾删除一个数。 只是大小 减1
例如： vector<int>a = {1,2,3}; a.pop_back(3); 等价于vector<int>a = {1,2};
back()函数返回末尾元素的引用
a.back(); 等价于 a[a.szie()-1];
front()函数返回首个元素的引用
a.front() 等价于 a[0];
vector 容器：erase函数
iterator erase(const_iterator pos);
erase函数可以删除指定位置的一个元素(通过迭代器指定)
a.erase(a.begin())就是删除第一个元素相当于pop_front
a.erase(a.end()-1)就是删除最后一个元素相当于pop_back
a.erase(a.begin()+2)就是删除第三个元素
a.erase(a.end()-2)就是删除倒数第二个元素
erase的复杂度最坏情况是删除第一个元素O(n)
如果删除的是最后一个元素则复杂度为O(1) 这是因为erase会移动pos之后的哪些元素
int main()
{
vector<int>a={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
a.erase(a.begin()+3);
cout<<"a="<<a<<endl;
a.erase(a.end()-1);
cout<<"a="<<a<<endl;
return 0;
}
vector 容器：erase函数,批量删除一个区间
C++里面的区间都是前面的是包含的后面是不包含的 [beg,end)
iterator erase(const_iterator beg,const_iterator end);
erase也可以指定两个迭代器作为参数，表示把这个区间内的对象都删除了。
比如这里a.erase(a.begin()+1,a.begin()+3)就删除了a的第二个和第三个元素
相当于a= a[:1]+a[3:], C++的insert和erase都是就地操作的。
例如：a.erase(a.begin()+n,a.end())就和a.resize(n)等价，前提是n小于a.size();
批量删除的最坏复杂度依然是O(n)，不过这里的两个作为erase参数的迭代器必须是这个自己这个对象的迭代器，不是其他容器的
他返回删除后最后一个元素之后那个位置的迭代器。
int main()
{
vector<int>a={1,2,3,4,5,6} ;
cout<<"a="<<a<<endl;
a.erase(a.begin+1,a.begin()+3); //迭代器的参数 前面必须是起始位置后面必须是终止位置
cout<<"a="<<a<<endl;
a.erase(a.begin+4,a.end()); //删除5 6 相当于resize(4) a.erase(a.begin+1,a.begin()+3);
cout<<"a="<<a<<endl;
cout<<"a="<<a<<endl;
return 0;
}
vector 容器：data()获取首地址指针
int *data();
int const *data()
data()会返回指向数组中首个元素的指针也就等价于&a[0]
由于vector是连续存储的数组，因此只要得到了首地址，下一个元素的地址只需要+1即可，
因为指针的p[i]相当于*(p+i)，因此可以把data()返回的首地址指针当一个数组来访问。
vector<int>a ={1,2,3,4,5,6}; int *p =a.data(); cout <<p[0]<< endl;
data()返回的首地址指针，配合size()返回的数组长度一起使用，(连续的动态数组只需要知道首地址和数组长度就可以确定)
用他来获取一个C语言原始指针int * ，很方便用于调用C语言函数的和API同时还能享受vector容器RAII的安全性
vector<int>a ={1,2,3,4,5,6};
int *p =a.data();
int n = a.size();
memset(p,-1,sizeof(int)*n);
cout <<a<< endl;
vector容器： RAII避免内存泄漏
vector会在离开作用域时，自动调用析构函数释放内存们就不必手动释放，能安全。
vector容器：生命周期由主对象管理
C++中运算符{} }标志着一个语句块的结束，在这里会调用所有身处其中的对象的析构函数
比如这里的vector 他的析构函数会释放动态数组的内存(既自动delete)
int main(){
int* p ;
{
vector<int> a ={1,2,3,4,5};
p=a.data();
cout<<p[0]<<endl;
cout<<p[0]<<endl;
}
cout<<p[0]<<endl; //空指针
return 0;
}
vector 会在退出作用域时释放内存，这时候所有指向其中元素的指针，包括data()都会失效
因此如果你是在语句块内获取的data指针，语句块外就无法访问了，
可见data()指针是对vector的一种引用 实际对象生命周期仍由vector类本身管理
vector容器：延续生命周期
int main(){
int* p ;
vector<int> holder;
{
vector<int> a ={1,2,3,4,5};
p=a.data();
cout<<p[0]<<endl;
cout<<p[0]<<endl;
holder = std::move(a); //只有移动时才是带着指针移动 拷贝的话开辟新空间赋值数据
}
cout<<p[0]<<endl; //空指针
return 0;
}
如果需要在一个语句块外仍然保持data()对数组的弱引用有效，可以把语句块内的vector对象移动到外面的一个vector对象上
vector在移动时指针不会失效， 例如： holder = move(a);
则会把a变成空数组，holder指向原来a所包含的元素数组，且地址不变，之后即使不直接使用外面的临时对象holder，也可以继续提高data()指针访问数据。
vector 容器：resize
void resize(size_t n)
void resize(size_t n ,int const &val);
除了可以在构造函数中指定数组的大小，还可以之后再通过resize函数设置大小
适用于一开始无法指定大小的情况
vector<int>a(4) 等价于 vector<int>a; a.resize(4);// 默认填充4个0
resize也接受第二参数的重载 ，会用这个参数的值填充所有新建的元素
vector<int>a(4,233); 等价于 vector<int>a; a.resize(4,233); //填入第二参数 4次
调用resize(n)的时候，如果数组已有超过n个元素假设是m个，则他会删除多出来的m-n个元素，前n个元素保持不变
vector<int>a]={1,2} a.resize(4) 等价于 vector<int>a ={1,2,0,0}
vector<int>a ={1,2,3,4,5,6}; a.resize(4) 等价于 vector<int>a ={1,2,3,4}
调用resize(n,val)的时候，如果数组已有超过n个元素假设是m个，则第二参数val会被无视，删除多出来的m-n个元素，前n个元素保持不变
vector<int>a]={1,2} a.resize(4，233) 等价于 vector<int>a ={1,2,233,233}
vector<int>a ={1,2,3,4,5,6}; a.resize(4，233) 等价于 vector<int>a ={1,2,3,4}
vector 容器：clear
void clear()
vector的clear函数可以清空该数组，也就是相当于把长度设为0 变成空数组。
例如： a.clear(); 等价于 a.resize(0) 或a{};
通常用于后面需要重新push_back，因此可以clear来把数组设为空。
vector 容器：clear的问题
int main(){
vector<int>a ={1,2,3,4};
cout<<"before clear,capaciy="<<a.capacity()<,endl;
a.clear();
cout<<"after clear,capaciy="<<a.capacity()<,endl;
}
clear相当于resize(0),所以他也不实际释放掉内存，容量(capacity)还是摆在那里
clear仅仅只是把数组大小(size)标记0而已。
vector容器： shrink_to_fit释放多余容量
size_tshrink_to_fit();
int main()
{
vector<int>a={1,2,3,4,5};
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.resize(12);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(4);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.shrink_to_fit();
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
return 0;
}
当resize到一个更小的大小上时，多余的容量不会释放，而是继续保留
如担心内存告急可以用shrink_to_fit释放掉多余的容量，只保留刚好为size()大小的容量。
shrink_to_fit会重新分配一段更小内存，它同样是会把元素移动到新内存中，因此迭代器和指针也会失效。
vector 容器：clear的问题，shrink_to_fit解决
int main(){
vector<int>a ={1,2,3,4};
cout<<"before clear,capaciy="<<a.capacity()<,endl;
a.clear();
a.shrink_to_fit();
cout<<"after clear,capaciy="<<a.capacity()<,endl;
}
要真正释放掉内存，可以在clear之后在调用shrink_to_fit
(这样才会让容量变成0,这时vector的data会返回nullptr)
当然，vector对象析构时也会彻底释放内存，clear配合shrink_to_fit只是提前释放
clear配合resize
resize会保留元素的1前面部分不变只在后面填充上0
如果需要把源数组前面的部分也填充上0，可以先clear再resize
vector<int>a]={1,2};
cout <<a << endl;
a.clear();
a.resize();
cout <<a << endl;
vector 容器:resize到更大尺寸会导致data失效
push_back = resize()+1; //扩容1写入
int main(){
vector<int> a ={1,2,3,4,5};
int* p=a.data();
cout<<p[0]<<endl;
cout<<p[0]<<endl;
a.resize(1024);
cout<<p[0]<<endl;
return 0;
}
当resize的目标长度大于原有的容量时，就需要重新分配一段更大的连续内存，
并把原数组长度的部分移动过去，多出来的部分则用0来填充，这就导致了元素的地址会有所改变
从而过去data返回的指针以及所有的的迭代器对象，都会失效。
vector 容器:resize到更小尺寸不会导致data失效
int main(){
vector<int> a ={1,2,3,4,5};
int* p=a.data();
cout<<p[0]<<endl;
cout<<p[0]<<endl;
a.resize(2);
cout<<p[0]<<endl;
a.resize(5);
return 0;
}
当resize的目标长度小于原有的容量时，不需要重新分配一段连续的内存，
也不会造成元素的移动(主要为了性能考虑)，所以指向元素的指针不会失效，
他只是会把数组的长度标记为新长度，后面空闲出来那一段内存不会释放掉
继续留在那里，直到vector对象被析构。
调用了a.resize(2);之后，数组的容量仍然是5，
因此重新扩容到5是不需要重新分配内存的，也就不会移动元素导致指针失效。
vector容器： capacity函数查询实际的最大容量
szie_t capacity() const noexcept();
int main()
{
vector<int>a={1,2,3,4,5};
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(2);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(5);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(7);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(12);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
return 0;
}
可以用capacity()函数查询已经分配内存的大小，即最大容量。
而szie()返回的其实是已经存储了数据的数组长度。
可以发现当resize指定的新长度一个超过原来的最大容量时，就会重新分配一段更大容量的内存来存储数组，只有这时才会移动元素的位置(data指针失效)。
注意这里resiez(7)之后容量实际上扩充到了10而不是刚好为7，为什么呢？
因为标准库的设计者为了减少重复分配的次数，他有一个策略：当resize后的新尺寸变化较小时，则自动宽容到原尺寸的两倍。
这里我们的原大小是5，所以resize(7)会扩充容量到10，但是尺寸为7.
尺寸总是小于等于容量 尺寸范围内都是已初始化的内存(0) 尺寸到容量之间的范围是未初始化的。
如果resize后的尺寸还超过了原先尺寸的两倍就没有这个效果了
实际上resize(n)的逻辑是扩容到max(n,capacity*2);
vector容器：reserve预留一定容量，避免之后重复分配 只会扩容不会减容
size_t reserve(szie_t n);
int main()
{
vector<int>a={1,2,3,4,5};
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reserve(12);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(2);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(5);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
a.reszie(12);
cout<<a.data()<<' ' <<a.szie();<<'/'<<a.capacity()<<endl;
return 0;
}
内存分配是需要一定时间的，可以用reserve函数预留一定的容量
这样之后就不会出现容量不足而需要动态扩容影响性能了
如这里一开始预留了12格容量，从5到12的时候就不必重新分配，reserve时也会移动元素
vector读取写入
vector 容器：operator[] 要访问vector里的元素，只需要[]运算符；
int& operator[](size_t n)
int const &operator[](size_t n)
vector<int>a(4);
cout<<"a[0] = " <<a[0]<<endl;
例如 a[0]访问第0个元素（人类的第一个）
cout<<"a[1000] = " <<a[1000]<<endl; 越界访问并不会直接保存 会导致异常
为了防止不小心越界 可以用 a.at(i) 代替 a[i] at函数会检测索引i是否越界 如果索引i>=a.szie()则会抛出异常 std::out_of_range
operator[]和at 除了读取还可以写入 因为他们返回的是元素的引用int&
例如：给第i个元素赋值val a[i] =val cout<<a[i]<<endl;
vector容器：构造函数
vector这个显式构造函数，默认会把所有元素初始化为0（不必手动去memset）
如果是自定义类，则会调用元素的默认构造函数（例如：数字类型初始化为0 ，string会初始化为空字符串，指针类型会初始化为nullptr）
重载cout输出流格式
重载cout输出流格式
main.cpp
#include "printer.h"
using namespace std;
int main()
{
vector<
int>a(4);
cout <<a << endl;
return 0;
}
printer.h
#pragma once
#include<iostream>
#include<vector>
/*在c++标准库命名空间std中，为 vector<t> 类型定义了一个输出流运算符重载函数，重载了 << 操作符
重载函数的功能是将vector对象的元素输出到一个输出流 其中 os 表示输出流 v 表示要输出的vector对象
函数体中使用迭代器遍历 vector 对象并将每个元素序列化为字符流，并将其连接成一个逗号分隔的字符串形式
*/
namespace std {
template <class T>
ostream& operator<<(ostream& os, vector<T> const& v)
{
os << '{';
auto it = v.begin();
if (it!=v.end())
{
os << *it;
for (++it; it != v.end(); ++it)
{
os << ',' << *it;
}
}
os << '}';
return os;
}
}
vector 迭代器模式
将这个打印的操作封装起来怎么做？
int main(){
vector<char> a ={'h','j','k','l'};
for(int i =0;i<a.size();i++){
cout<<a[i]<<endl;
}
return 0;
}
可以用一个函数来封装打印操作：void Print(vector<char> const &a)
void Print(vector<char> const &a){ //a不用被改写所以加了const引用 改写的话非const的即可
for(int i =0;i<a.size();i++){
cout<<a[i]<<endl;
}
}
int main(){
vector<char> a ={'h','j','k','l'};
Print(a);
return 0;
}
将这个打印的操作封装起来怎么做？
void Print(vector<char> const &a) //只能打印vector类型，没有打印string类型
//要支持只能再写一遍一样的print函数
void Print(vector<char> const &a){
for(int i =0;i<a.size();i++){
cout<<a[i]<<endl;
}
}
int main(){
vector<char> a ={'h','j','k','l'};
Print(a);
string b = {'h','j','k','l'};
print(b);
return 0;
}
string 和vector 都是连续的数组 内存都是连续的 他们都有data()和size()函数
所以可以把他们的初始地址和长度获取出来改用首地址指针和数组长度做参数
void print(char const *a,size_t n){
/*a不是数组对象 而是首地址指针 指针也可以访问数组，这样就可以不用知道它是什么类型只需要知道它是连续的就*/
for(int i =0;i<n;i++）
cout<<a[i]<<endl;
}
int main(){
vector<char> a ={'h','j','k','l'};
Print(a.data(),a.size());
string b = {'h','j','k','l'};
print(b.data(),b.szie());
return 0;
}
使用指针和长度做接口的好处可以通过指针加减运算，选择其中一部分连续的元素来打印，
而不一定全部打印出来。
比如说我们选择打印前三个元素去点最后一个元素，但不必用pop_back修改数组，只要传参数的时候修改一下长度即可
void print(char const *a,size_t n){
for(int i =0;i<n;i++）
cout<<a[i]<<endl;
}
int main(){
vector<char> a ={'h','j','k','l'};
Print(a.data()+1,a.size()-1); //打印了jkl
return 0;
}
//可以添加stride为步长
void print(char const *a,size_t n，i nt stride){
for(int i =0;i<n;i++）
cout<<a[i]*stride<<endl;
}
int main(){
vector<char> a ={'h','j','k','l'};
Print(a.data(),a.size()-1,1);
return 0;
}
为什么尾指针要往后移动一格？
让尾地址指针往后移动一格的设计，使得数组长度为0就是begptr==endptr的清空
非常容易判断，同时可以通过endptr-begptr算出数组的长度
//首尾对称指针
void print(char const *begptr ,char const *endptr){
for(char const*ptr =begptr;ptr!=endptr;ptr++)
{
char value =*ptr;
cout<<value<<endl;
}
}
int main(){
vector<char> a ={'h','j','k','l'};
char const *begptr = a.data();
char const *endle = a.data()+a.size(); //尾指针指向的是不可访问的，是多一个的 尾指针-头指针=size()实际数组大小
size_t size =endptr-begptr;
cout<<"begptr-endptr = "<<size<<endl;
print(begptr,endptr);
return 0;
}
模板函数
可以让首指针和尾指针声明为模板参数这样不论指针是什么类型
都可以使用print这个模板函数来打印
template<class Ptr>
void print(Ptr begptr,Ptr endptr){
for(Ptr ptr =begptr;ptr!=endptr;ptr++)
{
auto value =*ptr;
cout<<value<<endl;
}
}
int main(){
vector<char> a ={'h','j','k','l'};
char const *begptr = a.data();
char const *endle = a.data()+a.size();
print(begptr,endptr);
vector<int> b ={1,2,3,5};
int const *begptr = a.data();
int const *endle = a.data()+a.size();
print(begptr,endptr);
return 0;
}
C++运算符重载，它可以让你的返回值不是一个指针而是一个特殊的类(迭代器) ++运算符的内部其实不是给指针++反而是把它的结点指针指向结点的next
list的iterator类 重载了++运算符实际上是对应链表的curr=curr->next
template<class Ptr>
void print(Ptr begptr,Ptr endptr){
for(Ptr ptr =begptr;ptr!=endptr;ptr++) //!=是否到达位置 ++代表往后走一格 *结点引用
{
auto value =*ptr;
cout<<value<<endl;
}
}
list提供了begin()和end()函数 他们会返回两个list<char>::iteratr对象
list<char>::iterator是一个特殊定义过的类型，其具有！=和++以及*这些运算符的重载，所以用起来就像普通的指针一样。而这些运算符的重载，却会把++对应到链表的curr= curr->next上。
这样一个用起来就像普通的指针，但内部却通过运算符重载适配不同容器的特殊类就是迭代器(iterator)，迭代器是STL容器和算法之间的桥梁。
int main(){
list<char> a ={'h','j','k','l'};
list<char>::iterator begptr = a.begin();
list<char>::iterator endptr= a.end();
print(begptr,endptr);
return 0;
}
迭代器的精髓:把连续的访问映射到链表的不连续访问上 首迭代器+尾迭代器
template<class T>
struct list{
struct Node{
T value;
Node *next;
};
struct Interator{
Node *curr;
Iterator &operator++(){ //++p
curr =curr->next;
return *this;
}
Iterator operator++(int){ //p++
Iterator tmp =*this;
this->operator++();
return tmp;
}
T &operator*() const{
return curr->value;
}
bool operator!=(Iterator const *that)const{
return curr!=that.curr;
}
};
Node *head;
Iterator begin(){ return {head}; }
Iterator end(){ return {nullptr}; }
}
迭代器模式：++的前置和后置
++p与p++都会产生p=p+1的效果，区别在于他们被作为表达式时的返回值。
++p会返回自增后的值p+1这和p+=1完全一样，同样因为返回的是一个左值引用所还可以继续自增比如+++++p
p++会返回自增前的值p，但是执行完以后p又是p+1了
正因为如此，后置自增需要先保存旧的迭代器，然后自增自己，在返回旧迭代器可能会比较低效。
Iterator operator++(int){ //p++
Iterator tmp =*this;
this->operator++();
return tmp;
}
例如： p=1; int x =++p; x=2 p=2;
p=1 int x =p++; x=1 p=2;
vector容器：begin end 区间可以方便切片
begin可以获取指向第一个元素所在位置的迭代器
end可以获取指向最后一个元素下一个位置的迭代器 迭代器的作用类似于一个位置标记符
C++的特色就是采用了迭代器(iterator)来标记位置，他实际上时一个指针，
这样的好处是：不需要指定1原来的容器本身，就能知道指定的位置。
一队迭代器begin和end就表及了一个区间range，区间可以是一个容器的全部
例如：{a.begin()+1,a.end()-1}相当于去头去尾后的列表相当于python中的a[1:-1 ]
int main(){
vector<int> a ={1,2,3,4,5,6};
vector<int>::iterator b = a.begin();
vector<int>::iterator e = a.end();
cout<<"a="<<a<<endl;
cout<<"*b="<<*b<<endl;
cout<<"*(b+1)="<<*(b+1)<<endl;
cout<<"*(b+2)="<<*(b+2)<<endl;
cout<<"*(e-2)="<<*(e-2)<<endl;
cout<<"*(e-1)="<<*(e-1)<<endl;
cout<<"*e="<<*e<<endl;
return 0;
}
begin可以获取第一个元素所在位置的迭代器，可以提供*a.begin()来访问第一个元素
迭代器支持加法运算，例如*（a.begin()+1)就是访问数组的第二个元素了，和a[1]等价
end可以获取指向最后一个元素下一个位置的迭代器，也就是说end指向的位置是不可用的！
如需访问最后一个元素必须用*(a.end()-1)才行。
int main(){
vector<int> a ={1,2,3,4,5,6};
vector<int>::iterator b = a.begin();
vector<int>::iterator e = a.end();
cout<<"a="<<a<<endl;
cout<<"b[0]"<<b[0]<<endl;
cout<<"b[1]="<<b[1]<<endl;
cout<<"b[2]="<<b[2]<<endl;
cout<<"e[-2]="<<e[-2]<<endl;
cout<<"e[-1]="<<e[-1]<<endl;
cout<<"e[0]="<<e[0]<<endl;
return 0;
}
迭代器实际上可以用[]运算符访问，例如 b[i] =*(b+i)等价
不过只有vector这种连续的可随机访问容器的迭代器有+和[]运算符，对于list则只有*和++,--运算符可以用
迭代器和容器本身的主要区别在于：迭代器不掌握生命周期，从而迭代器的拷贝是平凡的浅拷贝，方便传参。
浅拷贝：拷贝数据 深拷贝：复制地址
同时的缺点，因为迭代器是一个原容器的弱引用，如原容器解构或者发生内存重新分配，迭代器就会失效。
版权声明：本文为Jcrry原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。