526互联

C++ STL

发布时间 2023-08-03 18:50:40作者: ETHERovo

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。
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。
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可重复。
  • map/multimap
    每个节点有key和value；multimap表示key可重复。

不定序容器

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