STL初识

        软件界一直希望建立可重复利用的东西，如C++的面向对象（封装、继承、多态）和泛性编程（模板）思想；为了建立数据结构和算法的一套标准，诞生了STL。

  基本概念：

• STL全名 Standard Template Library (标准模板库)
• STL从广义上分为：容器（container）算法（algorithm）迭代器（iterator）
• 容器和算法之间通过迭代器进行无缝连接
• STL几乎所有的代码都采用了 模板类或者模板函数

        容器将最广泛的一些数据结构实现了出来（数组，链表，树，集合等）；迭代器提供了一种方法，使之能够依序寻访各容器所含元素（无需暴露内部实现），每个容器有自己专属的迭代器（常用容器的迭代器种类是双向或随机访问迭代器）。

STL常用容器

1，string

        本质是一个类，类内部封装了char*，管理这个字符串

        还封装了很多成员方法，如：查找find，拷贝copy，删除delete，替换replace，插入insert

构造：

string s1; //创建空字符串，调用无参构造函数

const char* str = "hello world";

string s2(str); //把c_string转换成了string

string s3(s2); //调用拷贝构造函数

string s4(10, 'a'); //使用10个字符’a‘初始化

赋值：

string str1;        str1 = "hello world";

string str2;        str2 = str1;   //字符串赋值给当前

string str3;        str3 = 'a';     //字符赋值

string str4;        str4.assign("hello c++");

string str5;        str5.assign("hello c++",5);  //字符串前5个字符赋值给当前

string str6;        str6.assign(str5);

string str7;        str7.assign(5, 'x'); //5个字符'x'赋值给当前

拼接：

string str1 = "我";                   str1 += "爱玩游戏";                str1 += ':';

string str2 = "LOL DNF";        str1 += str2;

string str3 = "I";                      str3.append(" love ");        str3.append("game abcde", 4); //前4个字符拼接                             str3.append(str2, 3, 4); // 从下标3位置开始 ，截取4个字符

查找和替换：

//查找

string str1 = "abcdefgde";                        int pos = str1.find("de"); //从左往右找

if (pos == -1)        {cout << "未找到" << endl;}

else          {cout << "pos = " << pos << endl;}   //返回第一个字符位置

pos = str1.rfind("de"); //从右往左找         cout << "pos = " << pos << endl;

//替换

string str1 = "abcdefgde";            str1.replace(1, 3, "1111"); //从1开始的3个字符替换为"1111"

cout << "str1 = " << str1 << endl;   // str1 = a1111efgde

字符串比较：   （按ASCII码逐位比较，= 返回 0；> 返回 1 ；< 返回 -1

）

string s1 = "hello";                        string s2 = "aello";

int ret = s1.compare(s2);

if (ret == 0)        {cout << "s1 等于 s2" << endl; }

else if (ret > 0)   {cout << "s1 大于 s2" << endl; }

else                   {cout << "s1 小于 s2" << endl; }

字符存取：

string str = "hello world";

//通过[]方式获取

for (int i = 0; i < str.size(); i++)

{cout << str[i] << " "; }                         cout << endl;

//通过at方式获取

for (int i = 0; i < str.size(); i++)

{cout << str.at(i) << " "; }                     cout << endl;

//字符修改

str[0] = 'x';

str.at(1) = 'x';

插入和删除：

string str = "hello";

str.insert(1, "111");  //指定位置插入字符串

str.erase(1, 3);  //删除从1号位置开始3个字符

子串：

string str = "abcdefg";

string subStr = str.substr(1, 3);   //返回从1开始的3个字符组成的字符串

cout << "subStr = " << subStr << endl;

//实际运用(可以在实际开发中获取有效的信息)

string email = "hello@sina.com";                    int pos = email.find("@");

string username = email.substr(0, pos);         cout << "username: " << username << endl;

2，vector

        和数组非常相似，也称为单端数组；不同之处在于数组是静态空间而vector可动态扩展

构造：

vector<int> v1;                  //无参构造

for (int i = 0; i < 10; i++)    {v1.push_back(i); }

vector<int> v2(v1.begin(), v1.end());   //将[begin(), end())区间中的元素拷贝给本身

vector<int> v3(10, 100);   //将10个100拷贝给本身

vector<int> v4(v3);           //拷贝构造

赋值：

vector<int>v2;                v2 = v1;   //重载等号

vector<int>v3;                v3.assign(v1.begin(), v1.end());   //拷贝[begin(), end())区间中数据

vector<int>v4;                v4.assign(10, 100);    //10个100拷贝赋值给本身

容量和大小：

if (v1.empty())   //判空

{cout << "v1为空" << endl; }

else

{cout << "v1不为空" << endl;

cout << "v1的容量 = " << v1.capacity() << endl;   //容器容量

cout << "v1的大小 = " << v1.size() << endl;}         //元素个数

//resize 重新指定大小 ，若指定的更大，默认用0填充新位置，此处利用元素10填充

v1.resize(15,10);

//resize 重新指定大小 ，若指定的更小，超出部分元素被删除

v1.resize(5);

插入和删除：

vector<int> v1;

//尾插

v1.push_back(10);

v1.push_back(20);

v1.push_back(30);

 

//尾删

v1.pop_back();

//插入

v1.insert(v1.begin(), 100);         //首元素位置插入元素100

v1.insert(v1.begin(), 2, 1000);   //首元素位置插入2个元素1000

//删除

v1.erase(v1.begin());                 //删除迭代器指向元素

//清空

v1.erase(v1.begin(), v1.end());  //删除迭代器区间元素

v1.clear();

数据存取：

for (int i = 0; i < v1.size(); i++)

{cout << v1[i] << " "; }

for (int i = 0; i < v1.size(); i++)

{cout << v1.at(i) << " "; }

cout << "v1的第一个元素为： " << v1.front() << endl;

cout << "v1的最后一个元素为： " << v1.back() << endl;

互换容器：

v1.swap(v2);     //将v2与v1本身元素互换

//实际用途：收缩内存
void test02()
{
    // 1. 先定义vector，再插入元素
    vector<int> v;
    for (int i = 0; i < 100000; i++) {
        v.push_back(i); // 循环内插入10万个元素
    }

    // 2. 输出插入后的容量和大小
    cout << "插入10万元素后：" << endl;
    cout << "v的容量为：" << v.capacity() << endl; // 容量（已分配的内存能容纳的元素数）
    cout << "v的大小为：" << v.size() << endl;     // 实际存储的元素数（10万）
    cout << "------------------------" << endl;

    // 3. resize(3)：只保留前3个元素，大小变为3，但容量不变
    v.resize(3);
    cout << "resize(3)后：" << endl;
    cout << "v的容量为：" << v.capacity() << endl; // 容量仍为原来的大小（不会自动缩小）
    cout << "v的大小为：" << v.size() << endl;     // 大小变为3
    cout << "------------------------" << endl;

    // 4. 收缩内存：通过调用拷贝构造函数创建匿名对象交换释放多余容量
    // 原理：vector<int>(v) 创建匿名对象，仅拷贝v的有效元素（3个），容量也为3；
    // swap(v) 交换匿名对象和v的内部数据，原v的大内存被匿名对象接管，函数结束后匿名对象析构，释放大内存
    vector<int>(v).swap(v);
    cout << "收缩内存后：" << endl;
    cout << "v的容量为：" << v.capacity() << endl; // 容量变为3（和大小匹配）
    cout << "v的大小为：" << v.size() << endl;     // 大小仍为3
}

预留空间：   （可减少vector在动态扩展容量时的扩展次数）

v.reserve(100000);

void test(){
    vector<int> v;
    v.reserve(100000);//预留空间
    int num = 0;
    int* p = NULL;
    for (int i = 0; i < 100000; i++) {
        v.push_back(i);
        if (p != &v[0]) {
            p = &v[0];
            num++;
        }
    }
    cout << "num:" << num << endl;
}
//num是扩容次数，预留空间后num为1，不预留空间num为17~20

3，deque

        双端数组，可以对头端进行插入删除操作

    deque与vector区别：

• vector对头部的插入删除效率低（数据量越大效率越低）
• deque对头部的插入删除速度比vector快
• 而vector访问元素时的速度比deque快（与内部实现有关）

    deque内部工作原理：deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据。中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间。

构造：

deque<int> d1; //无参构造函数

for (int i = 0; i < 10; i++)

{d1.push_back(i); }

deque<int> d2(d1.begin(),d1.end()); //拷贝[beg,end)区间中的元素

deque<int>d3(10,100); //将10个100拷贝给本身

deque<int>d4 = d3; //拷贝构造函数

赋值：

deque<int> d1;                for (int i = 0; i < 10; i++)  {d1.push_back(i); }

deque<int>d2;                 d2 = d1; //重载等号操作符

deque<int>d3;                d3.assign(d1.begin(), d1.end()); //拷贝[beg,end)区间中的元素赋值

deque<int>d4;                d4.assign(10, 100);//将10个100拷贝赋值给本身

容量和大小：

if (d1.empty())   //判断容器是否为空

{ cout << "d1为空!" << endl; }

else {

cout << "d1的大小为：" << d1.size() << endl; }   //统计大小

d1.resize(15, 1);         //重新指定长度为15（默认值1填充新位置）

d1.resize(5);              //重新指定大小 （超出容器长度的元素被删除）

插入和删除：

//两端操作

deque<int> d;

//尾插                        d.push_back(10);                  d.push_back(20);

//头插                        d.push_front(100);                d.push_front(200);

//尾删                        d.pop_back();

//头删                        d.pop_front();

//指定位置插入          

d.insert(d.begin(), 1000); //插入位置，元素      d.insert(d.begin(), 2,10000); //中间项是个数

deque<int>d2={1,2,3};          

d.insert(d.begin, d2.begin(), d2.end()) //在某位置插入[begin,end)区间的数据

//指定位置删除

d.erase(d.begin());

//清除全部

d.erase(d.begin(), d.end());                              d.clear();

数据存取：

for (int i = 0; i < d.size(); i++)

{ cout << d[i] << " "; }                        //返回"[ ]"中索引所指的数据

for (int i = 0; i < d.size(); i++)

{ cout << d.at(i) << " "; }                   //返回 at 所指的数据

cout << "front:" << d.front() << endl;//返回第一个数据元素

cout << "back:" << d.back() << endl;//返回最后一个数据元素

排序：        【支持随机访问的迭代器容器，都可以用sort进行排序 要包含头文件 algorithm】

sort(d.begin(), d.end()); //默认排序（升序）

4，stack

        概念：stack是一种先进后出的数据结构，它只有一个出口

        栈只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为

stack<int> s; //创建栈容器 (必须符合先进后出) 

//入栈

s.push(10);

s.push(20);

s.push(30);

while (!s.empty()) {

//输出栈顶元素 (只支持访问栈顶)

cout << "栈顶元素为： " << s.top() << endl;

//弹出栈顶元素

s.pop();

}

cout << "栈的大小为：" << s.size() << endl;

入队 --- push；出队 --- pop ；返回队头元素 --- front；返回队尾元素 --- back ；

判断队是否为空 --- empty ；返回队列大小 --- size

6，list

        概念：链表 list 可将数据进行链式存储，是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序通过链表中的指针链接实现.

        链表由一系列结点组成，结点由存储元素的数据域和存储下一节点地址的指针域组成。

        STL中链表是一个双向循环链表，由于链表存储方式不是连续的内存空间，只支持前移和后移，属于双向迭代器。

优点

• 可以对任意位置进行快速插入或删除元素
• 动态存储分配，不会造成内存浪费和溢出

缺点

• 遍历速度略慢（于数组），占用空间较大（于数组）

重要性质：插入、删除操作不会造成原有list迭代器失效，在vector此性质不成立。

STL中 List 和 vector 是两个最常用的容器

构造：

list<int>L1;                L1.push_back(10);                L1.push_back(20);

 

list<int>L2(L1.begin(),L1.end());

list<int>L3(L2);

list<int>L4(10, 1000);        //list构造同其它几个STL常用容器

赋值和交换：

list<int>L1;                L1.push_back(10);                 L1.push_back(20);

//赋值

list<int>L2;                        L2 = L1;

list<int>L3;                        L3.assign(L2.begin(), L2.end());

list<int>L4;                        L4.assign(10, 100);

//交换

L1.swap(L4);

大小：

if (L1.empty())

{cout << "L1为空" << endl; }

else

{cout << "L1的大小为： " << L1.size() << endl; }

//重新指定大小

L1.resize(10, 1);

L1.resize(2);

插入和删除：

//两端操作

list<int> L;

//尾插                       L.push_back(10);                  L.push_back(20);

//头插                       L.push_front(100);                L.push_front(200);

//尾删                        L.pop_back();

//头删                        L.pop_front();

//指定位置插入          

L.insert(L.begin(), 1000);  //插入位置，元素      L.insert(L.begin(),2,10000); //中间项是个数

list<int> L2 = {1,2,3}    ;    

L.insert(L.begin(), L2.begin(), L2.end()); //在某位置插入[begin,end)区间的数据

//指定位置删除

L.erase(L.begin());

L.push_back(1000);  L.push_back(1000);       L.remove(1000); //删除所有与1000匹配的元素

//清除全部

L.clear();

数据存取：

// list 本质是链表，不支持随机访问，[ ] 和 at 访问方式不支持

list<int>::iterator it = L1.begin();

//it = it + 1;//错误，不可以跳跃访问，即使是+1 【只支持双向 ++ 或 --】

cout << "第一个元素为： " << L1.front() << endl;

cout << "最后一个元素为： " << L1.back() << endl;

反转和排序：        【注意：list不支持随机访问，也就不可以用 sort 的标准算法】

L.reverse();    //反转容器的元素

L.sort(); //默认的排序规则 从小到大        L.sort(myCompare); //指定规则，从大到小

//需提前定义规则 myCompare
bool myCompare(int val1, int val2)
{
    return val1 > val2;
}

        不支持随机访问迭代器的容器，内部会提供一些对应的算法，如list中有 sort 成员函数做排序

        区分 L.sort(); 【成员函数, ()可指定规则】        和         sort(L.begin(), L.end());【不支持】

7，set

        本质：set/multiset 所有元素都会在插入时被自动排序，属于关联式容器，底层是二叉树，

        区别：set不允许容器中有重复的元素；multiset 允许重复。

构造和赋值：

set<int> s1;    //默认构造

s1.insert(10); //插入数据只有 insert 方式        s1.insert(30);         s1.insert(20);  //自动排序

set<int> s2(s1);  //拷贝构造

set<int> s3;                                s3 = s2;  //赋值

大小和交换：

if (s1.empty())   // 判空

{cout << "s1为空" << endl; }

else

{cout << "s1的大小为： " << s1.size() << endl; }  // 统计大小

set<int> s2;        s2.insert(100);         s2.insert(300);

s1.swap(s2);  // 交换

插入和删除：

set<int> s1;

//插入

s1.insert(10);                s1.insert(30);                 s1.insert(20);

//删除

s1.erase(s1.begin());   //删除所指元素

s1.erase(30);   //删除值为30的元素 

//清空

//s1.erase(s1.begin(), s1.end());                s1.clear();

查找和统计：

//查找

set<int>::iterator pos = s1.find(30);   //若key=30存在返回该键元素的迭代器，不存在返回end

if (pos != s1.end())

{cout << "找到了元素 ： " << *pos << endl; }

else

{cout << "未找到元素" << endl; }

//统计

int num = s1.count(30);

cout << "num = " << num << endl;

set 和 multiset 的区别：【set不可插入重复数据，multiset可以】

//set 插入数据时返回插入结果，表示插入是否成功

set<int> s;

pair<set<int>::iterator, bool> ret = s.insert(10);

if (ret.second) {

cout << "插入成功!" << endl; }

else {

cout << "插入失败!" << endl; }  // 第二次insert(10)则失败

//multiset 不会检查数据，可以插入重复数据

multiset<int> ms;

ms.insert(10);

ms.insert(10);   // 第二次insert(10)成功插入重复数据

pair对组创建：        【成对出现的数据，有两种创建方式】

pair<string, int> p("Tom", 20);

cout << "姓名： " << p.first << " 年龄： " << p.second << endl;

pair<string, int> p2 = make_pair("Jerry", 10);

cout << "姓名： " << p2.first << " 年龄： " << p2.second << endl;

set容器排序：        【set容器默认排序规则是从小到大；需掌握如何改变排序规则】

class MyCompare{

public:

bool operator()(int v1, int v2) const{  // 关键添加const修饰，表示此函数不修改对象状态

return v1 > v2; }   };    // 排序规则改为从大到小

//默认从小到大

set<int> s1;

s1.insert(10);                 s1.insert(30);                 s1.insert(20);

//指定排序规则

set<int,MyCompare> s2;  //MyCompare仿函数可指定 set 排序规则

s2.insert(10);                 s2.insert(40);                 s2.insert(20);

8，map/multimap 容器     

    【常用，高性能高效率】

      介绍：map 中所有元素都是pair，第一个元素为key起索引作用，第二个元素为value放实值。所有元素根据元素的键值自动排序。属于关联式容器，底层是二叉树。

      map 不允许容器中有重复的 key 值元素；multimap允许。

      优点：可以根据 key 值快速找到 value 值。

构造和赋值：

map<int,int>m; //默认构造

m.insert(pair<int, int>(1, 10));                m.insert(pair<int, int>(2, 20));  // 插入时要有对组

map<int, int>m2(m);  //拷贝构造

map<int, int>m3;                 m3 = m2;  //赋值

大小和交换：

if (m.empty())

{cout << "m为空" << endl;}

else

{cout << "m的大小为： " << m.size() << endl; }

map<int, int>m2;        m2.insert(pair<int, int>(4, 100));         m2.insert(pair<int, int>(5, 200));

m.swap(m2);  // 交换

插入和删除：

//插入

map<int, int> m;

//第一种插入方式        m.insert(pair<int, int>(1, 10));

//第二种插入方式        m.insert(make_pair(2, 20));

//第三种插入方式        m.insert(map<int, int>::value_type(3, 30));

//第四种插入方式        m[4] = 40;    //【不建议用，[ ]会自动创建value为0的数据】

//删除

m.erase(m.begin());

m.erase(3);   // 按照key值删除

//清空

m.erase(m.begin(),m.end());

m.clear();

查找和统计：

//查找

map<int, int>::iterator pos = m.find(3);

if (pos != m.end())

{cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl; }

else

{cout << "未找到元素" << endl; }

//统计

int num = m.count(3);         //map不允许插入重复的key，count统计而言要么 0 要么 1

cout << "num = " << num << endl;

set容器排序：      【map容器默认排序规则是按key值从小到大；需掌握如何改变排序规则】

class MyCompare{

public:

bool operator()(int v1, int v2) const{  // 关键添加const修饰，表示此函数不修改对象状态

return v1 > v2; }   };    // 排序规则改为从大到小

//默认从小到大排序

//利用仿函数实现从大到小排序

map<int, int, MyCompare> m;

m.insert(make_pair(1, 10));         m.insert(make_pair(2, 20));       m.insert(make_pair(3, 30));

for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++)

{ cout << "key:" << it->first << " value:" << it->second << endl;}

对于自定义数据类型，map和set容器必须要指定排序规则。