Giskard

(三十)标准模板库STL

2018-11-01

一般使用方法

  • 很少需要自己定义一个模板,只需要使用现成的模板库即可,STL就是频繁使用的一个库

  • STL封装了几乎所有常见的线性数据结构

模板 意义
vector 一维向量,相当于数组
list 链表
map 映射。提供(key,value)操作,相当于哈希表
string char字符串
queue 队列,先入先出的线性表
stack 栈,先入后出的线性表
set 集合
deque 双向链表
#include<stdio.h>
#include<vector>

using namespace std; //std为standard:标准
int main()
{
    vector<int> arr;
    arr.push_back(10);
    arr.push_back(11);
    for(int i=0;i<arr.size();i++)
    {
        int val = arr.at(i);
        printf(...);
    }
    return 0;
}

向量vector

vector用于实现数组的功能

vector的主要函数

函数名称 功能
push_back 在尾部添加元素
pop_back 在尾部删除元素
clear 清空所有元素
at 按索引访问某个位置的元素
front 返回头元素
back 返回尾元素
size 返回元素个数
capacity 返回当前容量
resize 改变容量大小
insert 在中间插入元素
erase 删除中间元素
vector<int> arr(128);
at/front/back
vector<int> arr(128);
for(int i=0;i<arr.capacity();i++)
{
    int& p = arr.at(i);
    p = 0;//全部初始化为0
}
  • vector还重载了操作符[],因此以下代码等价

    int& p = arr.at(0);
    int& p = arr[0];
    

arr.front()相当于arr[0]

arr.back()相当于arr[arr.capacity()-1]

push_back/pop_back/resize/clear
vector <int> arr;  //capacity:0, size:0
arr.push_back(1);  //capacity:4, size:1

if(arr.size>1024)
{
    arr.resize(2048);
}
#include<vector>
using namespace std;
int main()
{
    vector<int> arr(128);
    arr.clear(); //size清零,capacity为128
    ...
}
iterator/const_iterator

iterator迭代器,用于遍历

vector<int>::iterator iter;//其实iter为指针类型

for(vector<int>::iterator iter = arr.begin(); iter!=arr.end(); iter++)
{
    int& p = *iter;
    printf("%d\n",p);
}
void test(const vextor<int>& arr)
{
    for(vector<int>::const_iterator iter = arr.begin(); iter!=arr.end(); iter++)
    {
        const int& p = *iter;
        printf("%d\n",p);
    }
}
insert/erase

使用vector进行插入删除操作消耗资源大,建议用list链表进行插入删除,但这里依然放出代码

struct Object
{
    int id;
    char name[32];
};

vector<Object> obj(1000);

void AddObject(const Object& s)
{
    for(vector<Object>::iterator iter = obj.begin(); iter!=obj.end(), iter++)
    {
        Object& p = *iter;
        if(s.id<p.id)
        {
            objs.insert(iter,1,s);
            break;
        }
    }
}

void DelObject(int id)
{
    for(vector<Object>::iterator iter = obj.begin(); iter!=obj.end(), iter++)
    {
        Object& p = *iter;
        if(p.id == id)
        {
            obj.erase(iter);
            break;
        }
    }
}

####list

对应于数据结构中的单向链表,不支持随机访问,只支持顺序访问

push_back/pop_back/push_front/pop_front

分别为在尾部添加元素,在尾部删除元素,在头部添加元素,在头部删除元素

  • 当坚持只对list进行push_back和pop_front时,他就是队列
  • 当坚持只对list进行push_back和pop_back时,他就是栈

string

string是对字符串的封装,内部维护一个以0结尾2的char型数组

函数名称 功能
append 附加字符串
clear 清空
capacity 容量
size 实际长度
length 实际长度,等同于size
at 按索引访问
find 查找一个字符或字符串
rfind 从后往前查找一个字符或字符串
substr 取得一个子串
insert 插入字符或子串
replace 替换字符或子串
string str1 ("LiMing");
string str2 = "LiMing";
string str3 ("LiMing",6);

//空字符串
string str4;
string str5 = "";
//string str6 = NULL;  错误!!不能用NULL初始化string

//用c_str函数取得string内部的字符串指针
const char* str = str1.c_str();
append/clear
#include<string>
using namespace std;

int main()
{
    string str;
    str.append("something else");
    str.append("abcdef",5);  //附加一个字符串的前五个字符,即abcde
    str.append("abcdef"1,3); //附加一个字符串从1开始,长度3,即bcd

    str += "hello";  //string重载了操作符+=,也是用于附加字符串

    str.clear();
    return 0;
}
at

可以用at修改字符串的内容

str.at(0) = 'K';
char ch = str.at(0);

//已经重载了[],这个也正确
str[0] = 'K';
字符串比较

C风格字符串一般用strcmp比较,string重载了关系操作符,可以直接用==、<=比较

string str1 ("LiMing");
string str2 = "ZhangHua";
if(str1 < str2)
{
    printf(...);
}
字符串查找

C风格字符串一般用strchr查找字符,strstr查找子串,返回找到位置的指针

string使用find函数查找字符或子串,返回整型数字,没有找到则返回-1

string str = "LiMing";
int pos = str.find('i');  //返回1
int pos = str.find('i',2);//从位置2开始查找到的i,即位置3

int pos = str.find("ing");//返回3
int pos = str.find("ing",pos+3);//在第一次查找的基础上继续往后查找相同的子串

rfind从右往左查找,用法和find差不多

find_first_of函数用于查找若干字符中的一个,只要任意一个匹配,即返回此字符的位置

//查找第一个元音字符的位置
int pos = str1.find_first_of("aeiouAEIOU");
//查找第一个非元音字符的位置
int pos = str1.find_first_not_of("aeiouAEIOU");

find_last_of和find_last_not_of是从右往左的

substr

用于复制部分子串

string src ("abcdefg");
string str1 = src.substr(4);//返回efg
string str2 = src.substr(4,2);//返回ef
insert/replace

string不适合进行插入删除操作

//string插入的几种方式
string& insert(int pos, const char* str);//在pos处插入str
string& insert(int pos, const char* str, int count);//在pos处插入str[0,count-1]
string& insert(int pos, const char* str, int offset, int count);//在pos处插入str[offset,count-1]
string& insert(int pos, int count, char ch);//插入若干字符

//replace
string& replace(int pos, int num, const char* dest);//pos为要替换旧子串的位置,num为其长度
void DoReplace(string& str, const string& src, const string& dst)//str为要修改的,不用const修饰,而src和dst需要
{
    while(1)
    {
        int pos = str.find(src);//查找旧子串src的位置
        if(pos < 0)break;
        src.replace(pos,src.length(),dst);
    }
}

string SQL = "SELECT * FROM student WHERE id = {0} AND...";
DoReplace(SQL,"{0}","1");
//删除子串
DoReplace(SQL,"{0}","");//替换为空串就是删除
string作为函数参数
void test(const string& str);
void test(string& str);
void test(string str);

在正规代码中一般只使用前两种方式。

因为传引用的效率比传值要高,传引用不需要数据复制,而传值需要,所以不要使用第三种

当需要修改参数的时候使用第二种,当不需要修改的时候使用第一种

map

map表示的是映射表

主要设计目标是快速查找,内部有键和值(Key-Value),每一项的Key是不同的

对于数组和链表,数据项越多查找越慢,但是对于映射表来说查找速度几乎不变

//map在定义时要指定Key和Value的类型
map<int,Object> obj;
使用[]插入数据
#include<map>
using namespace std;

struct Object
{
    int id;
    char name[64];
};

typedef map<int,Object> ObjctMap;

int main()
{
    ObjectMap obj;
    Object a = {1,"aaa"};
    obj[1] = a;
    return 0;
}
使用insert插入数据
ObjectMap obj;
Object a = {1,"aaa"};
obj.insert(ObjectMap::value_type(1,a));

#####查找

根据Key值查找Value值

ObjectMap::iterator iter = obj.find(1);//Key的值是1,求Value
if(iter != obj.end())
{
    Object& s = iter->second;
}
//map的iterator类指向的是value_type,故iter->first返回的是Key,iter->second返回的是value
遍历
for(ObjectMap::iterator iter = obj.begin(); iter!=obj.end(); iter++)
{
    const int& key = iter->first;
    Object& val = iter->second;  //iter->second返回的不是const引用类型,而是普通的引用类型
}
删除
ObjectMap::iterator iter = obj.find(1);
if(iter != obj.end())
{
    obj.erase(iter);
}
Tags: C/C++