C++ STL(标准模板库)是一套功能强大的c++模板类提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列、栈。包含以下三个组成部分
组件 描述 容器(Containers) 容器是一个与数组类似的单元,用来存储值,且存储的值的类型相同;比如deque、list、vector、map等 算法(Algorithms) 算法作用于容器,它们提供了执行各种操作的方法,包括对容器内容执行初始化、排序、搜索、转换等操作 迭代器(iterators) 迭代用于遍历对象集合的元素,这些集合可能是容器,也可能是容器的子集
零、 前言
1. 命名空间
当工程代码采用不同的程序和程序库时,针对不同的对象使用相同的标识符,就会出现名称冲突的现象,使用namespace就可以解决这个问题。标识符的可见范围namespace和class不同,namespace具有扩展开放性,可以出现在任意源码文件中。
C++ 标准程序库的所有标识符都被定义于一个名为std的namespace中,有以下三种方法使用:
直接指定标识符,例如
std::cout << std::hex << 3.4 << std::endl;
使用using declaration的方法,例如:
using std::cout;
using std::endl;
使用using directive,这是最简便的方法,就像被声明为全局标识符一样,但是由于某些重载的规格,这种方法可能导致意外地命名冲突,因此应避免使用第三种,除非程序很小为了方便。
using namespace std;
cout << hex << 3.4 << endl;
2. 通用工具
Pairs(对组)
class pair,凡需要将两个值视为一个单元的场景(例如必须返回两个值的某函数)就必须用到它,例如容器类别map和multimap,就是使用pairs来管理键值对元素
std::pair<int, float> p; // 初始化p.first 和 p.second为 0
std::pair<int, char *> p(42, "hello");
数值极限
标准库通过template numeric_limits提供极值,定义于,浮点数定义于
#include<iostream>
#include<string>
#include<limits> //头文件
using namespace std;
int main(){
cout<<"numeric_limits<unsigned short>::min()= "<<numeric_limits<unsigned short>::min()<<endl; //unsigned short的最小值
cout<<"numeric_limits<unsigned short>::max()= "<<numeric_limits<unsigned short>::max()<<endl; //unsigned short的最大值
cout<<"numeric_limits<int>::min()= "<<numeric_limits<int>::min()<<endl; //int的最小值
cout<<"numeric_limits<int>::max()= "<<numeric_limits<int>::max()<<endl; //int的最大值
cout<<"numeric_limits<short>::min()= "<<numeric_limits<short>::min()<<endl;
cout<<"numeric_limits<short>::max()= "<<numeric_limits<short>::max()<<endl;
cout<<"numeric_limits<double>::min()= "<<numeric_limits<double>::min()<<endl;
cout<<"numeric_limits<double>::lower()="<<numeric_limits<double>::lower()<<endl; //double最小值是lower,min只会返回e的负数次方
cout<<"numeric_limits<double>::max()= "<<numeric_limits<double>::max()<<endl;
cout<<"numeric_limits<int>::is_signed()= "<<numeric_limits<int>::is_signed<<endl;//是否有正负号
cout<<"numeric_limits<string>::is_specialized()= "<<numeric_limits<string>::is_specialized<<endl;//是否定义了数值极限
return 0;
}
辅助函数
定义在内的是哪个辅助函数,max()、min()、swap()。
namespace std {
template <class T>
inline const T& min(const T& a, const T& b) {
return b < a ? b : a;
}
template <class T>
inline const T& max(const T& a, const T& b) {
return a < b ? b : a;
}
template <class T>
inline void swap(T& a, T& b) {
T temp {a};
a = b;
b = temp;
}
}
非成员函数的方法
如果要为每一个容器类型,单独定义一个排序,查找的方法,则工作量会非常巨大,并且很多都是重复性的工作,因此STL定义了非成员函数,来完成通用的容器算法,如sort(),find(),swap().如果该容器类型vector.swap()存在,则代表要比普通的swap()函数效率更高.
for ( vector< int > :: iterator pr = test. begin ( ) ; pr != test. end ( ) ; pr++ )
替换为:
for_each ( test. begin ( ) , test. end ( ) , cout) ;
sort ( test. begin ( ) , test. end ( ) ) ;
1 > 如果要排序的对象是用户自己定义的, 则需要重载比较操作符
struct Review {
string title;
int rating;
}
bool operator< ( const Review & r1, const Review & r2)
{
if ( r1. title < r2. title) {
return true;
} else if ( ri. title == r2. title && r1. rating < r2. rating) {
return true;
} else {
return false;
}
}
然后就可以使用sort函数对自定义对象进行排序了.
sort ( book. begin ( ) , book. end ( ) ) ;
2 > 如果想按照其他排序方式, 则可以使用第三个入参
bool worseTahn ( const Review & r1, const Review & r2)
{
if ( r1. rating < r2. rating) {
return true;
} esle {
return false;
}
}
size : 是当前vector容器真实占用的大小,也就是容器拥有多少个元素,对应resize()
capacity : 是值发生在realloc前能允许的最大元素数,即预分配的内存空间,对应reserve(),对于list, map, set, deque由于内存是散列分布的,因此capacity()对于这些容器是没有意义的.在STL中,拥有capacity属性的只有vector和string.
# include <iostream>
# include <vector>
using std:: vector;
int main ( void )
{
vector< int > v;
std:: cout<< "v.size() == " << v. size ( ) << " v.capacity() = " << v. capacity ( ) << std:: endl;
v. reserve ( 10 ) ;
std:: cout<< "v.size() == " << v. size ( ) << " v.capacity() = " << v. capacity ( ) << std:: endl;
v. resize ( 10 ) ;
v. push_back ( 0 ) ;
std:: cout<< "v.size() == " << v. size ( ) << " v.capacity() = " << v. capacity ( ) << std:: endl;
return 0 ;
}
对于空的vector,如果直接用[]访问,可能会发生越界报错,建议用at()会首先进行越界检查.
3. 容器类型
总体容器可以分为两类:
序列式容器Sequence containers:表述为可序的群集,每个元素均有固定的位置,取决于插入时机和地点,和元素值无关,如vector, deque, list。 关联式容器Associative containers:表述为已序群集,元素位置取决于特定的排序准则,如果元素的位置取决于元素值,和插入次序无关,例如:set, multiset, map, multimap。 关联式容器在C++实现中,采用红黑树的方法,因此会自动对元素排序,其优点为当搜索元素时,可以放心的使用二分搜索法等有序要求的算法。
一、String容器
当程序需要处理字符串的时候,C语言在string.h和cstring里提供了一系列函数,但是不支持C++的string类。string类也是STL容器中的一种
1. string类构造函数
# 1. 按照C风格创建字符串
string one ( "hello world" ) ;
# 2. 创建由10 个C组成的字符串
string two ( 10 , 'c' ) ; // "cccccccccc"
# 3. 复制构造函数将string对象初始化为对象one
string three ( one) ; // "hello world"
# 4. 重载[ ] 运算符,可以用下标访问
three[ 0 ] = 'P'
# 5. 重载+= 运算符将字符串Oops附件到字符串one后
one += "Oops!" ;
string four; // 默认构造函数创建一个以后可以赋空值
four = two + three + '!' // 重载=运算符,可以给对象赋值
# 6. 将C风格字符串和整数作为参数,其中整数表示要复制多少个字符串
char alls[ ] = "All well that end well"
string five ( alls, 20 )
# 7. 迭代器模板拷贝,[ begin, end) 是迭代器,前闭后开
template< class Iter> string ( Iter begin, Iter end) ;
string six ( alls + 6 , alls + 10 ) ;
string six ( five + 6 , five + 10 ) ; //这种方法不可行,因为five是对象,并不是指针
# 8. 将另一个string对象的部分内容拷贝到构造的对象中
string seven ( four, 7 , 16 ) ;
2. string类输入
# 1. 按照C风格输入字符串
char info[ 100 ] ;
cin >> info; // 读取一个单词
cin. getline ( info, 100 ) ; // 读取一行,丢弃换行符
cin. get ( info, 100 ) ; // 读取一行,换行符保存在队列中
# 2. 对于string对象,有两种方式:使用cin读入字符串时,遇到空白就停止读取。比如程序输入的是
" Hello World"
那么我们得到的字符串将是"Hello" ,前面的空白没了,后面的world也读不出来。如果我们想把整个hello world读进来怎么办?那就这样做
cin >> s1 >> s2;
hello存在s1里,world存在s2里了。有时我们想把一个句子存下来,又不想像上面那样创建多个string来存储单词,怎么办?那就是用getline来获取一整行内容。
string str;
getline ( cin, str) ; // 会自动调整string的大小,使其刚好存下输入
cout << str << endl;
3. string类方法
# 1. 重载了比较操作符, '<' , '>' , '='
string one ( "gedit" ) ;
string two ( "name" ) ;
one > two || one < two || one != two
# 2. 判断字符串长度
one. size ( ) == one. length ( ) ; // size和length的函数行为一模一样,size是为了提供stl兼容性而后添加的
# 3.f ind方法
one. find ( 'e' ) ; // 返回字符串中第一次出现e的下标
one. find ( "dit" ) ; // 返回字符串中第一次出现子串的下标
one. rfind ( 'e' ) ; // 返回字符串中最后一次出现e的下标
one. find_first_of ( "eat" ) ; // 返回"eat"中任意一个字符最早出现的索引
one. find_last_of ( "eat" ) // 返回"eat"中任意一个字符最后出现的索引
one. find_first_not_of ( "eat" ) // 返回原字符串,在"eat"中第一个没有出现的索引
# 4. 内存块大小
程序将一个字符添加到字符串的末尾时,不能仅仅将已有的字符串加大,相邻的内存可能被占用了,因此可能需要分配一个新的内存块,并将原来的信息拷贝过去。
实现过程:
1 > 初始创建的时候,分配一个比实际字符串大的内存块。
2 > 如果超过了内存块的大小,程序将分配一个原来为两倍的新内存空间。
3 > 方法capacity ( ) 返回当前分配给字符串的内存块大小,reserve ( ) 获取内存块的最小长度
二、vector容器
vector表示了一组可以随机访问的值,可以通过[]运算符来直接访问矢量的第n个元素.
1. vector分配器
通常使用来表示使用的类型,同时vector是动态分配的内存
int n;
cin >> n;
vector< int > test ( n) ;
分配器可以在构造函数摸板的时候选择,该参数指定了使用哪个分配器来管理内存
template< class T, class Allocator = allocator< T> >
如果省略了Allocator的值, 则默认使用new和delete来管理内存.
2. vector方法
所有的STL容器都提供了一些基础方法,其中包括了size(),swap(),begin(),end()等.
# 1. 迭代器
vector< double > scores;
vector< double > :: iterator pd;
pd = score. begin ( )
for ( pd = score. begin ( ) ; pd != score. end ( ) ; pd++ ) { // 这里不能用pd<sorce.end()
* pd = 12.3 ;
cout << pd[ i] ;
}
# 2. 从尾部添加元素, 自动负责内存管理
vector< int > test;
while ( cin >> temp && temp >= 0 ) {
test. push_back ( temp) ;
}
# 3. 删除区间的元素, 左闭右开
test. erase ( test. begin ( ) , test. begin ( ) + 2 ) ;
# 4. 在某位置插入元素, 或插入一个区间
test. insert ( test. begin ( ) , 1 ) ;
test. insert ( test. begin ( ) , new. begin ( ) , new. end ( ) )
# 5. 插入和弹出从尾部的效率是O ( 1 ) , 其他从任意位置都是O ( n)
弹出的过程不能获得元素, 因此需要先获取, 再弹出
test. pop_back ( )
test. push_back ( )