About STL

STL是C++一套C++软件库, 原本是惠普实验室的几位大佬所开发的, 它一开始并不是专为C++设计的,但它对C++产生了巨大影响, 并在1994年正式加入C++标准中.

STL组件

STL包括6大组件:

1. 容器
2. 算法
3. 迭代器
4. 仿函数
5. 适配器
6. 空间配置器

容器

容器是可以存放数据的类, STL中的常见容器有vector, list等等
需要注意的是, 不同的容器会有不同的头文件.

算法

STL提供了非常多的数据结构算法, 这些算法大多在std命名空间内定义. 所有的算法都是基于模板实现的.

迭代器

迭代器类似于C语言中的指针, 我们在学习数据结构时, 都需要定义各种指针来进行遍历, 查找操作, 但有了迭代器,我们就不用那么麻烦了

适配器

适配器是对常用序列式容器的封装, 针对不同的应用场景封装出不同的适配器以满足日常使用需求. STL的适配器有queue, stack, priority_queue分别对应队列, 栈, 优先级队列.

内存配置器

内存配置器时特定的内存模型, 能够将内存的申请转变为内存的调用.

string的构造

模板库是使用类来封装的, 所以每个容器都可以看成是一个独立的类. 既然有了类, 那么就会有构造函数了.string类也是通过构造函数来进行实例化的.
string常用的构造函数有:

string();//构造一个空的string类对象
string(const char* s);//用C风格字符串构造string类对象
string(size_t size,char c);//构造一个string类对象, 包含size个c字符
string(const string& s);//通过拷贝构造string类对象

string申请的是堆上的空间, 所以STL提供了一些函数让我们获取它的容量属性:

string s;
s.size();//获取有效字符串长度
s.length();//同上,没有区别
s.capacity(); //获取空间总大小,空间会自动扩容,不需要我们操作
s.empty();//判断字符串是否为空
s.clear();//清空有效字符
s.reserve(x);//为字符串预留x个字节的空间
s.resize(size_t n, char c);//改变有效字符个数到n个,增加时,使用c来进行填充, 
                           //如果没有参数c,就用0来填充,
                           //有效字符增加可能会产生扩容

string的迭代器和访问操作

string可以使用迭代器对数据进行访问:

string s("kishere");
string::iterator it;//定义一个string类对象的迭代器(正向)

同时, string还提供了一些操作让我们更方便地对数据进行访问:

s[1];//获取第二个位置的字符
it = s.begin();//获取第一个位置的迭代器
string::reverse_iterator rit;//定义一个string类对象的迭代器(反向)
it = s.end();//获取最后一个字符下一个位置的迭代器
it = s.rbegin();//获取最后一个字符位置的反向迭代器
it = s.rend();//获取第一个位置的反向迭代器

迭代器支持’++’, ‘- -‘操作来获取下一个位置, 但是要注意的是反向迭代器++是获取当前字符的前一个字符.

string的修改

通过STL提供的相关函数可以进行相关的修改操作.

s.pushback('C');//向string类对象s的末尾插入字符C
s.append(str);//向string类对象s末尾追加字符串str
s+=str;//同上
s.c_str();//将string类对象s转为c_str返回

深拷贝

在类和对象中我们讨论了关于浅拷贝的问题. 在类中有资源管理时, 使用默认的拷贝构造函数. 拷贝和被拷贝的两个指针指向同一块内存空间, 在释放内存时, 会使内存被释放两次, 导致程序崩溃. 这就是所谓的浅拷贝.
在涉及资源管理的类中, 拷贝构造函数必须显式给出:

class string{
public:
    string(const string& s)
        :_str(new char[strlen(s._str)+1])
    {
        strcpy(_str,s._str);
    }
private:
    char* _str;
}

vector简介

vector的头文件是< vector >, 它类似于我们之前实现的线性表和C语言里的动态数组. 和string的存储方式也有些类似.

vector使用

vector的操作与string类似

构造函数

vector<int> num;//实例化一个vector类对象,存放的元素的数据类型是int型,num里面是空的
                //<>里不一定要放默认的类型, 放string型或者自定义类型都是可以的
vector<int> num2(4,2);//实例化构造,并将num2内的元素初始化为4个2
vector<int> num3(num);//拷贝构造

迭代器

vector<int>:iterator it1 = num.begin();//begin, end, rbegin, rend和string里的一样
const vector<int> num4;
const vector<int>:const_iterator it2 = num4.begin();//const对象使用const迭代器

迭代器失效

要注意的是, vector中很容易产生迭代器失效的问题.

//删除数据导致的迭代器失效
int arr[] ={1,2,3,4};
vector<int> num(arr,arr + sizeof(arr)/sizeof(int));
vector<int>::iterator pos = find(num.begin(), num.end(), 3);
num.erase(pos);
cout << *pos <<endl;//此时会导致非法访问

//插入数据导致的迭代器失效
pos = find(num.begin(), num.end(), 3);
num.insert(pos, 30);
cout << *pos << endl; //insert可能会触发扩容,扩容后原有的空间被释放,
                      //num指向新的空间,而此时pos还是指向原来的空间
                      //此时会导致非法访问

list简介

list是由双向链表实现的, 每个节点存储一个元素, 它可以实现C++数据结构中链表的所有功能.

构造函数

list<int>ls;//创建空list对象
list<int>ls2(size);//创建初始大小为size的list对象
list<int>ls3(size, value);//创建初始大小为size, 每个元素初始值为value的list对象
list<int>ls4(ls3);//拷贝构造

元素修改

list给我们提供了4种修改元素的函数:

ls.push_back(2);//向链表头部插入2
ls.push_front(1);//向链表末尾插入1
ls.pop_front();//删除链表开头的第一个元素
ls.pop_back();//删除链表的末尾元素
list<int>::iterator pos;
ls.insert(pos,1);//插入元素到指定位置
ls.erase(pos);//删除pos位置的元素
ls.erase(pos,pos+2);//删除pos和pos+1位置的元素
ls.clear();//清空链表

其他成员函数

ls.merge(ls2);//将两个链表合成一个链表
ls.sort();//升序排序
ls.sort(greater<int>());//降序排序
ls.remove(1);//删除链表中多有值为1的元素

list和vector的区别

vector	list
可以随机访问, 访问元素效率为O(1)	不能随机访问, 访问效率为O(n)
插入, 删除的效率低, 时间复杂度为O(n)	插入, 删除效率高, 时间复杂度为O(1)
底层为连续空间不容易造成内存碎片, 空间利用率高, 缓存利用率高	底层节点动态开辟, 容易造成内存碎片, 空间利用率低, 缓存利用率低
插入, 删除时会导致所有迭代器失效	只有删除时才会导致被删除的节点的迭代器失效
适用于经常访问, 不经常增删的场合	适用于经常需要增删, 访问比较少的场合