C++ STL

etherovo / 2023-08-03 / 原文

一、体系结构

1.初始

头文件
c++标准库不包括.h，#include；c旧库需要包括.h，#include<stdio.h>；c新库在旧库前面加c，不需要包含.h，#include。
旧头文件不被封装在std命名空间中。
网站资源
www.cplusplus.com
cppreference.com
gcc.gnu.org
书籍

2.STL体系结构

部件
六大部件：容器、分配器、迭代器、适配器、算法、仿函式
容器用于管理内存。
分配器用于支持容器的内存管理。
除了容器模板类本身的操作之外，其他操作被独立出来作为算法；可见则不是面向对象编程，而是模板编程。
迭代器是泛化的指针，用于协助算法操作容器。
仿函数用于对类进行函数操作。
适配器可以转换容器、仿函数、迭代器。
复杂度
没有一种容器或者算法是最优的，而是根据需求选择。
前闭后开区间
begin()指向第一个元素，end()指向最后一个元素的下一个位置。无论是否是连续容器。因此，遍历容器可以：

Container<T> c;
...
Container<T>::iterator ite = c.begin();
for(;ite!=c.end();++ite)
...

除此之外，可以使用范围for循环。其中遍历对象是迭代器。

std::vector<int> vec;
...
for(auto elem:vec){ std::cout<<elem<<std::endl; }
for(auto& elem:vec){ elem*=2; }

3.容器分类与结构

序列容器、关联容器（key-value，适合快速查找）、不定序容器（一种关联容器，使用hash table实现）

序列容器

array
将array包装成了class，无法扩充。

array<long,Asize>c;
for(long i=0;i!=Asize;++i) c[i]=rand();
coud<<c.size()<<" "<<c.front()<<" "<<c.back()<<" "<<c.data();//尺寸、第一个元素、最后一个元素、地址
qsort(c.data(),Asize,sizeof(long),compareLongs);
long* pItem = (long*)bsearch(&tarhet,(c.data(),Asize,sizeof(long)));

vector
可以向后扩展与删除。

vector<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.push_back(string(buf));
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.front()<<" "<<c.back()<<" "<<c.data()<<" "<<c.capacity();
auto pItem = ::find(c.begin(),c.end(),target);cout<<*pItem;
sort(c.begin(),c.end());
string* pItem = (string*)bsearch(&target,(c.data()),c.size(),sizeof(string));

list
不连续空间，使用指针的双向环状链表。

list<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
   try{
    c.push_back(string(buf));
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.front()<<" "<<c.back()<<" "<<c.max_size();
auto pItem = ::find(c.begin(),c.end(),target);
c.sort();//当容器自身提供sort时要比全局sort更快。

forward-list
不连续空间，使用指针的单向链表。考虑到指针空间，单向链表比双向链表更节省内存。

forward_list<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
   try{
    c.push_front(string(buf));//需要使用push_front()，而非push_back()
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.front()<<" "<<c.max_size();//没有back、size
auto pItem = ::find(c.begin(),c.end(),target);
c.sort();//当容器自身提供sort时要比全局sort更快。

slist

#include<ext\slist>
__gnu_cxx::slist<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
   try{
    c.push_front(string(buf));//需要使用push_front()，而非push_back()
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.front()<<" "<<c.max_size();//没有back、size
auto pItem = ::find(c.begin(),c.end(),target);
c.sort();//当容器自身提供sort时要比全局sort更快。

deque
两端可进可出。
分段连续，段内部连续，段间不连续，操作符重载++使得使用者感觉是连续的。如果空间不够，当push_back，会在后面分配新的buffer，当push_front，会在前面分配新的buffer。因为是以buffer分配的，所以会比vector按倍数分配更节省空间，当然比list、forward_list、slist占用空间更多，但是查找效率更高。

deque<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.push_back(string(buf));
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.front()<<" "<<c.back()<<" "<<c.max_size();
auto pItem = ::find(c.begin(),c.end(),target);cout<<*pItem;
::sort(c.begin(),c.end());

stack
先进先出。使用deque实现。可以看作容器的adapter。不提供iterator，避免破坏容器先进后出。

stack<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.push(string(buf));
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.top()<<" "<<c.back();
c.pop();

queue
先进先出。使用deque实现。可以看作容器的adapter。不提供iterator，避免破坏容器后进先出。

queue<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.push(string(buf));
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.front()<<" "<<c.back()<<" "<<c.back();
c.pop();

关联容器

使用红黑树实现。

set/multiset
key就是value；multiset表示key可重复。

multiset<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.insert(string(buf));//插入到树中合适的位置
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.max_size();
auto pItem = ::find(c.begin(),c.end(),target);
auto pItem = c.find(target);//自我定义的更快
cout<<*pItem;

set<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.insert(string(buf));//插入到树中合适的位置
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.max_size();
auto pItem = ::find(c.begin(),c.end(),target);
auto pItem = c.find(target);//自我定义的更快
cout<<*pItem;

map/multimap
每个节点有key和value；multimap表示key可重复。

multimap<long, string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.insert(pair<long,string>(i,string(buf)));//插入到树中合适的位置，不可以使用[]插入
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.max_size();
auto pItem = ::find(c.begin(),c.end(),target);
auto pItem = c.find(target);//自我定义的更快
cout<<(*pItem).second;

map<long, string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    //c.insert(pair<long,string>(i,buf));//插入到树中合适的位置，可以使用[]插入
    c[i]=string(buf);
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<" "<<c.max_size();
auto pItem = ::find(c.begin(),c.end(),target);
auto pItem = c.find(target);//自我定义的更快
cout<<(*pItem).second;

不定序容器

使用hash table实现。根据计算来决定元素放在表中的位置，如果发生碰撞则分开放，但是不够理想，而是以链表保存碰撞的元素。如果碰撞次数太多，链表就会很长，查找效率很低，此时会重新打散。

unordered_multiset

unordered_multiset<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.insert(string(buf));//插入到树中合适的位置
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<std::endl;
cout<<c.max_size()<<endl;
cout<<c.bucket_count()<<endl;//槽位数量，如果元素数量比篮子数量多，就会让篮子数量翻倍，然后打散元素重新分配，因此篮子数量一定比元素数量多
cout<<c.max_bucket_count()<<endl;
cout<<c.load_factor()<<endl;
cout<<c.max_load_factor()<<endl;//1不变

auto pItem = ::find(c.begin(),c.end(),target);
auto pItem = c.find(target);//自我定义的更快
cout<<*pItem;

unordered_multimap

unordered_multimap<string>c;
char buf[10];
for(long i=0;i!=value;++i)
{
  try{
    c.insert(pair<long,string>(i,string(buf)));//插入到树中合适的位置
  }
  catch(exception& p)
  {
    abort();//退出程序
  }
}
cout<<c.size()<<std::endl;
cout<<c.max_size()<<endl;

auto pItem = ::find(c.begin(),c.end(),target);
auto pItem = c.find(target);//自我定义的更快
cout<<*pItem;

hash_set, hash_map, hash_multiset, hash_multimap是c++1.0不被采纳而被厂家实现的旧版本

4.分配器之测试

默认的是std::allocator<>，在memory中

其他分配器在ext扩展库中，不是标准库，其命名空间是__gnu_cxx。

应当用容器，而当有额外的空间分配需求时使用new或malloc，而不是使用分配器，因为delete或free不需要记住申请空间的大小。

二、内核分析

1.源代码分布

VC++：...\include\
GNU C++：...\4.9.2\include\c++\bits, ...\4.9.2\include\c++\ext

2.OOP与GP

GP将操作与数据分开，通过使用迭代器实现。
这就使得容器和算法团队可以各自做事，只要定义好接口。如下使用模板给出min的接口，而具体的算法实现通过操作符重载来完成。

template<class T>
inline const T& min(const T& a, const T& b){ return b<a?b:a; }

template<class T,class Compare>
inline const T& min(const T& a, const T& b, Compare comp){ return comp(a,b)?b:a; }

cout<<max("happy","test");//默认大小比较

bool strLonger(const string& s1, const string& s2){ return s1.size()<s2.size(); }
cout<<max("happy","test",strLonger);//自己实现大小比较

list将sort自我实现，这是因为全局sort进行了(first+last)/2操作，这只适用随机迭代器。