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