STL components: Container, Allocators, Algorithms, Iterators, Adapters, Functors
标准序列容器：vector，string，queue，list；标准关联容器：set，multiset，map，multimap
迭代器分类：
输入迭代器：只读迭代器，在每个被遍历到的位置上只能被读取一次(istream_iterator)
输出迭代器：只写迭代器，只能被写入一次(ostream_iterator)
前向迭代器：可以对同一位置重复读写，只能向前移动，不支持operator--。
? 所有的标准STL容器都支持比前向迭代器更强大的迭代器。
双向迭代器(bidirectional iterator)：向前向后都可以
随机访问迭代器
所有重载了函数调用操作符(operator())的类都是一个函数子类(functor class)，从这些类创建的对象被称为函数对象或函数子。函数bind1st和bind2st被称为绑定器。
容器的选择
vector是默认使用的序列类型；当需要频繁在序列中间做插入和删除操作时，使用list；当大多数删除插入发生在序列的头部和尾部，使用deque。
连续内存容器(array-based)：vector，string，deque
基于节点的容器(node-based)：list，关联容器
针对连续内存容器的插入删除操作一般会使指向该容器的迭代器、指针和引用无效。
STL容器中进去的是副本，出来的也是副本（copy in，copy out）。smartPtr
优先选择区间成员函数而不是单元素成员函数。
区间创建：
? container::container(InputIterator begin, InputIterator end);
区间插入：
? 标准序列容器：void container::insert(iterator position, InputIterator begin, InputIterator end);//何处插入
? 关联容器：void container::insert(InputIterator begin, InputIterator end);
区间删除：
? 序列容器：iterator container::erase(iterator begin, iterator end);
? 关联容器：void container::erase(iterator begin, iterator end);
区间赋值：
? void container::assign(InputIterator begin, InputIterator end);
C++编译器的分析机制
list
第二个参数会被解释为函数参数。解决办法：给第一形参加上括号？或者避免使用匿名对象。
当你使用指针的容器时，而其中的指针应该被删除时，为了避免资源泄漏，应该使用引用计数形式的智能指针对象（如boost的shared_ptr）代替指针，或者当容器被析构时手工删除器中的每个指针。
typedef boost::shared_ptr<T> SPT;
vector<SPT> a;
复制一个auto_ptr时，它所指向的对象的所有权被移交到拷入的auto_ptr上，而它自身被置为NULL。所以切勿创建包含auto_ptr的容器对象。
删除元素的方法
删除容器中有特定值的所有对象：
// vector, deque, string: erase-remove
c.erase(remove(c.begin(), c.end(), value), c.end());
// list
c.remove(value)
// 关联容器,基于等价而不是相等
c.erase(value)
删除容器中满足特定判别式的所有对象：
bool badValue(int x);
// 序列容器 remove_if
c.erasa(remove_if(c.begin(), c.end(), badValue), c.end());
c.remove_if(badValue);
// 关联容器
- remove_copy_if and swap
assocContainer<int> c;
assocContainer<int> goodValues;
remove_copy_if(c.begin(), c.end(), inserter(goodValues, goodValues.end()), badValue);
c.swap(goodValues);
- for (assocContainer<int>::iterator i = c.begin(); i != c.end();) {
if (badValue(*i)) c.erase(i++);//后缀递增
else ++i;
}
要在循环内部做某些操作：
// 标准序列容器
for (SeqContainer<int>::iterator i = c.begin(); i != c.end();) {
if (badValue(*i)) i = c.erase(i);//一旦erase完成，它是指向紧随被删除元素的下一个元素的有效迭代器
else ++i;
}
Resource acquisition is initialization
使用reserve来避免不必要的重新分配。
将vector和string数据传给C API。
void dosomething(const int* plnts, size_t numInts);
if (!v.empty()) dosomething(&v[0], v.size());
void dosomething(const char* pString);
dosomething(s.c_str());
// 用来自C API的元素初始化一个vector
size_t fillArray(double* pArray, size_t arraySize);
vector<double> vd(maxNumDoubles);
vd.resize(fillArray(&vd[0], vd.size()));
// 初始化string, 将数据放到一个vector<char>中，然后将数据从该矢量复制到相应字符串中
size_t fillString(char* pArray, size_t arraySize);
vector<char> vc(maxNumChars);
size_t charsWritten = fillString(&vc[0], vc.size());
string s(vc.begin(), vc.begin() + charsWritten);
使用swap技巧除去多余的容量
vector<Contestant> v;
string s;
...
vector<Contestant>(v).swap(v);
string(s).swap(s);
避免使用vector
关联容器中，理解相等和等价的区别。
为包含指针的关联容器指定比较类型。总是让比较函数在等值情况下返回false。
// set<string*> ssp <-> set<string*, less<string*>, allocator<string*> > ssp;
struct DereferenceLess {
template<typename PtrType>
bool operator() (PtrType pT1, PtrType pT2) const {
return *pT1 < *pT2;
}
}
set<string*, DereferenceLess> ssp;
struct Dereference {
template<typename T>
const T& operator()(const T* ptr) const {
return *ptr;
}
}
transform(ssp.begin(), ssp.end(),
ostream_iterator<string>(cout,"\n"),
Dereference());
当效率至关重要时，如果要更新一个已有的映射表元素，应该优先选择operator[]，如果要添加一个新的元素，那么最好还是选择insert。
在使用容器时，尽量用iterator来代替const或reverse型的迭代器。
如果要在一个reverse_iterator ri指定的位置上插入新元素，则只需在ri.base()位置处插入元素即可。对于茶与操作而言，ri和ri.base()是等价的，ri.base()是真正与ri对应的iterator。如果要在ri指定的位置上删除一个元素，则需要在ri.base()前面的位置上执行删除操作，v.erase((++ri).base())。
对于非格式化的逐字符输入过程，你总是应该考虑使用istreambuf_iterator，输出ostreambuf_iterator。
ifstream inputFile("Data.txt");
string fileData((istreambuf_iterator<char>(inputFile)), istreambuf_iterator<char>());
要在算法执行过程中增大目标区间，使用插入型迭代器，比如ostream_iterator, 或者由back_inserter, front_inserter, inserter返回的迭代器。
int transmogrify(int x);//根据x生成一个新值
vector<int> values;
list<int> res;// vector无push_front,不可用front_inserter
transform(values.begin(), values.end(),
back_insert(res),
transmogrify);
transform(values.rbegin(), values.rend(),
front_insert(res),
transmogrify);
transform(values.begin(), values.end(),
inserter(res, res.begin()+res.size()/2),
transmogrify);
排序算法的选择
vector<int> va;
partitial_sort(va.begin(), va.begin()+k, va.end());//找前k个最棒的，第二个参数表示目标区间外的第一个元素
nth_element(va.begin(), va.begin()+k-1, va.end());//最棒的k个放在前面
vector<int>::iterator goodEnd = partition(va.begin(), va.end(), Compare);
除了list::remove / list::unique，其他容器调用remove / unique后都需要再调用erase真正删除。
vector<int> v;
v.erase(remove(v.begin(), v.end(), value), v.end());
对包含指针的容器使用remove类算法时，或者通过引用计数的智能指针，或者在调用remove之类算法之前先手工删除指针并将它们置为空。
// 要求排序区间的STL算法：
binary_search, lower_bound, upper_bound
equal_range, set_union, set_intersection
set_difference, set_symmetric_difference
merge, inplace_merge, includes
unique, unique_copy // 这俩不一定要求排序，但删除所有重复元素，必须保证所有相等的元素连续存放
// copy_if的实现
template<typename InputIterator,
typename OutputIterator,
typename Predicate>
OutputIterator copy_if(InputIterator begin,
InputIterator end,
OutputIterator destBegin,
Predicate P) {
while (begin != end) {
if (p(*begin)) *destBegin++ = *begin;
++begin;
}
}
使用accumulate(#include
accumulate(istream_iterator<int>(cin), istream_iterator<int>(),0);
使用函数对象而不是函数作为STL算法的参数。
函数对象在STL中作为参数传递或返回时总是按值方式被复制的。这意味着两件事：使它们小巧，使它们成为单态的。对于用作判别式的函数对象，必须是纯函数（返回值仅仅依赖其参数的函数，所能访问到数据仅仅局限于参数以及常量）。
原文：https://www.cnblogs.com/leapxx/p/14655071.html