STL学习笔记

#.string 建议
使用string 的方便性就不用再说了，这里要重点强调的是string的安全性。
string并不是万能的，如果你在一个大工程中需要频繁处理字符串，而且有可能是多线程，那么你一定要慎重(当然，在多线程下你使用任何STL容器都要慎重)。

string的实现和效率并不一定是你想象的那样，如果你对大量的字符串操作，而且特别关心其效率，那么你有两个选择，首先，你可以看看你使用的STL版本中string实现的源码；另一选择是你自己写一个只提供你需要的功能的类。

string的c_str()函数是用来得到C语言风格的字符串，其返回的指针不能修改其空间。而且在下一次使用时重新调用获得新的指针。

string的data()函数返回的字符串指针不会以'\0'结束，千万不可忽视。
对于c_str() data()函数，返回的数组都是由string本身拥有，千万不可修改其内容。其原因是许多string实现的时候采用了引用机制，也就是说，有可能几个string使用同一个字符存储空间。而且你不能使用sizeof(string)来查看其大小。

尽量去使用操作符，这样可以让程序更加易懂（特别是那些脚本程序员也可以看懂） 。

find()函数都返回一个size_type类型，这个返回值一般都是所找到字符串的位置，如果没有找到，则返回string::npos。有一点需要特别注意，所有和string::npos的比较一定要用string::size_type来使用，不要直接使用int 或者unsigned int等类型。

#.sort() 建议
默认的都是从小到大排序

1.若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort；

2.若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选. 如：前5个：partial_sort(vect.begin(), vect.begin()+5, vect.end());

3.若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序，nth_element是最理想的。如：找排在第5的位置
nth_element(vect.begin(), vect.begin()+4, vect.end()); //注意是begin()+4

partial_sort()和nth_element()都把5个最小的放在前面

4.若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition。如：student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

5.若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。

6.sort, stable_sort, partial_sort, 和nth_element算法都需要以随机迭代器(random access iterators)为参数，因此这些算法能只能用于vector, string, deque, 和array等容器，对于标准的关联容器map、set、multmap、multset等，这些算法就有必要用了，这些容器本身的比较函数使得容器内所有元素一直都是有序排列的。

7.对于容器list，看似可以用这些排序算法，其实也是不可用的（其iterator的类型并不是随机迭代器），不过在需要的时候可以使用list自带的排序函数sort(有趣的是list::sort函数和一个“稳定”排序函数的效果一样)。
对一个list容器使用partial_sort或nth_element，只能间接使用:
方法(1)：把list中的元素拷贝到带有随机迭代器的容器中，然后再使用这些算法；
方法(2)：生成一个包含list::iterator的容器，直接对容器内的list::iterator进行排序，然后通过list::iterator得到所指的元素；
方法(3)：借助一个包含iterator的有序容器，然后反复把list中的元素连接到你想要链接的位置。

list成员函数的行为和它们兄弟的行为经常不同。如想从容器删除对象，调用remove，remove_if和unique算法后，必须接着调用erase才能真正删除对象，但list的remove，remove_if和unique真的删除掉了对象。sort算法不能用于list，但list可以调用自己的sort成员函数。

8.partition和stable_partition与sort、stable_sort、partial_sort和nth_element不同，它们只需要双向迭代器。因此可以在任何标准序列迭代器上使用partition和stable_partition

9.时间和空间复杂度: stable_sort > sort > partial_sort > nth_element > stable_partition > partition

#.删除容器中的特定值：
1.如果容器是vector.string.deque，使用erase和remove的惯用法：
c.erase(remove(c.begin(),c.end(),value),c.end())
remove并不能“真的”删除元素，因为它做不到,如果你真的要删除元素，要在remove上接上erase
2.如果容器是list，使用list::remove （l.remove(value)）
3.如果容器是关联容器，用erase删除容器中满足一个特定条件的值：c.erase(c.begin())
1.如果容器是vector.string.deque，使用erase和remove_if的惯用法
2.如果容器是list，使用list::remove_if
3.如果容器是关联容器，用remove_copy_if和swap，或写一个循环遍历容器元素,把迭代器传给erase时后置递增它。
eg：

//顺序容器循环遍历容器元素删除值：
for(vector<int>::iterator i=c.begin(); i!=c.end(); )
if( condition(*i) ) i=c.erase(i);
else ++i;

//关联容器循环遍历容器元素删除值：
for(map<int,int>::iterator i=c.begin(); i!=c.end(); )
if( condition(*i) ) c.erase(i++);
else ++i;
关联容器的erase(i)会返回删除元素的个数，这里只关心删除的值

#.将容器传给C风格的指针：
vector<int> c; int *p=&c[0];（最好用if(!c.empty())检查一下再传入）
string s; char* p=s.c_str();

#.使用“交换技巧”来休整过剩容量：
class Contestant{....}
vector<Contestant> v;
.... //是v变大然后删除部分
vector<Contestant>(v).swap(v);//在v上“收缩到合适”（v.size()=v.capacity()）
vector<Contestant>( ).swap(v);//清除v而且最小化它的容量

string s;
..... //是s变大然后删除部分
string(s).swap(s);//在s上“收缩到合适”
string( ).swap(s);//清除s而且最小化它的容量

#.为指针的关联容器指定比较类型（不是比较函数）：
set<string*> ssp;
//建立一个指针的关联容器，容器会以指针的值排序，所以输出时候string不会按字典顺序

struct StringLess:
public binary_function<const string*,const string*,bool>
{
bool operator()(const string* ps1,const string* ps2) const
{
return *ps1<*ps2;
}
};
typedef set<string*,StringLess> StringPtrSet;
StringPtrSet ssp;

或者：
struct DereferenceLess
{
template<typename PtrType>
bool operator()(PtrType p1,PtrType p2) const
{
return *p1<*p2;
}
};
set<string*,DereferenceLess> ssp;
如果有一个智能指针或迭代器的关联容器，也得为它指定“比较类型”

#.equal_range的用法：
typedef vector<string>::iterator vit;
typedef pair<vit,vit> vitpair;
sort(svec.begin(),svec.end());
vitpair vp=equal_range(svec.begin(),svec.end(),"aaa");
if(vp.first!=vp.second) cout<<"\nFind the string\n";
else cout<<" Not find the string\n";
if(vp.first!=vp.second) cout<<"There are "<<distance(vp.first,vp.second)<<" aaa \n";

#.使iterator(i)指向const iterator(ci)：
typedef vector<int>::iterator Iter;
typedef vector<int>::const_iterator ConstIter;
从iterator到const iterator没有隐式类型转换，
也不能用Iter i(const_cast<Iter>(ci));//因为iterator(i)和const iterator(ci)是两种完全不同的类型
可以用以下技巧：
advance(i,distance<ConstIter>(i,ci)); //使i指向ci指向的元素
建议：尽量用iterator代替const_iterator和reverse_iterator

#.只能操作有序数据的算法：
搜索算法：binary_search,lower_bound,upper_bound,equal_range,
set_union,set_intersection,set_difference,set_symmetric_difference
merge, inplace_merge includes
一般用于有序区间：
unique,unique_copy

#.保证用于算法的比较函数和用于排序的一致：
sort(v.begin(),v.end(),greater<int>());
//bool it=binary_search(v.begin(),v.end(),5); //error 默认的是升序，会导致未定义的行为
bool it=binary_search(v.begin(),v.end(),5,greater<int>());

#.用accumulate和for_each来统计区间：
#include<numeric> //包含accumulate
double sum=accumulate(v.begin(),v.end(),0.0);

#.ptr_fun(),mem_fun()和mem_fun_ref()的用法:
ptr_fun()可以把指向一个函数的指针转化为一个函数对象。函数必须是一元或是二元函数（不是为无参的函数设计的）
transform(begin,end,dest,not1(ptr_fun(fun)));

mem_fun 与 mem_fun_ref 是为了使 STL 算法可以将成员函数（member functions ）当作参数， 而加入的，如下：
list<Widget *> lpw;
for_each(lpw.begin(), lpw.end(),mem_fun(&Widget::test)); // pw->test();

vector<Widget> vw;
for_each(vw.begin(), vw.end(),mem_fun_ref(&Widget::test)); // w.test();
mem_fun_ref的作用和用法跟mem_fun一样，唯一的不同就是：当容器中存放的是对象实体的时候用mem_fun_ref，当容器中存放的是对象的指针的时候用mem_fun。

#.避免对 set 及 multiset 的关键部分进行原地修改：

这里的“关键部分(key part)”指的是 set / multiset 存储的对象 T 中对 set / multiset 的 排序算法有影响的部分，或者说是参与排序的部分。比如下例中 User::ID：
class User {
public:
unsigned int ID;
string name;
unsinged int age;
const string& gettitle() const;
void settitle(string& title);
};
class UserIDLess : public binary_function<User, User, bool> {
public:
operator() (const User &lhs, const User &rhs) const {
return lhs.ID < rhs.ID;
}
};
typedef set<User, UserIDLess> IDUserSet;

修改 set / multiset 中的对象时，注意不要改变对象的关键部分(对set/multiset的排序算法有影响的部分)，否则容器会被破坏。
如果必须改变关键部分，采取如下策略：
1. 找到要修改的对象。*a = set.find();
2. 复制对象。 User b(*a);
3. 修改复制的对象。 b.changeSome();
4. 删除原对象。 set.erase(a++);
5. 插入复制的对象。 set.insert(a,b);

安全，可移植的方式写：
IDUserSet se; //是以ID号排序的set
User selectID; //带有需要ID号的User
....
IDUserSet::iterator i=se.find(selectID);
if(i!=se.end())
{
User e(*i);
se.erase(i++);
e.settitle("John");
se.insert(i,e);
}

#.copy_if的正确实现（STL里没有copy_if）：

#include<iostream>
#include<vector>
#include<iterator>
#include<cstdlib>
using namespace std;

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;
}
return destBegin;
}

int main()
{
int a[]={0,3,2,1,5,4,6,8,7,9};
vector<int> v(a,a+sizeof(a)/sizeof(int));
cout<<"\nOutput the number greater than 4:\n";
copy_if(v.begin(),v.end(),ostream_iterator<int>(cout," "),bind2nd(greater<int>(),4));
cout<<"\nOutput the number greater than 4:\n";
remove_copy_if(v.begin(),v.end(),ostream_iterator<int>(cout," "),bind2nd(less_equal<int>(),4));
//STl里没有copy_of，但有 remove_copy_of
system("pause");
return 0;
}

#.使仿函数类可适配：

ptr_fun可以使四个标准函数适配器（not1、not2、bind1st和bind2nd）存在某些typedef，提供这些必要的typedef的函数对象称为可适配的。
operator()带一个实参的仿函数类，要继承的结构是std::unary_function。operator()带有两个实参的仿函数类，要继承的结构是std::binary_function。
unary_function和binary_function是模板，所以你不能直接继承它们。取而代之的是，你必须从它们产生的类继承，而那就需要你指定一些类型实参。对于unary_function，你必须指定的是由你的仿函数类的operator()所带的参数的类型和它的返回类型。对于binary_function，你要指定三个类型：你的operator的第一个和第二个参数的类型，和你的operator地返回类型。
两个的例子：
template<typename T>
class MeetsThreshold: public unary_function<Widget, bool>
{
private:
const T threshold;

public:
MeetsThreshold(const T& threshold);
bool operator()(const Widget&) const;
...
};

struct WidgetNameCompare:public binary_function<Widget, Widget, bool>
{
bool operator()(const Widget& lhs, const Widget& rhs) const;
};
一般来说，传给unary_function或binary_function的非指针类型都去掉了const和引用。

当operator()的参数是指针时这个规则变了。这里有一个和WidgetNameCompare相似的结构，但这个使用Widget*指针：
struct PtrWidgetNameCompare:public binary_function<const Widget*, const Widget*, bool>
{
bool operator()(const Widget* lhs, const Widget* rhs) const;
};

#.查找算法：
Inputiterator find(Inputiterator first,Inputiterator last, const EqualityCompare& value)
//返回一个迭代器，指向value第一次出现的位置，找不到返回last。

Forwarditerator adjacent_find(Forwarditerator first, Forwarditerator last)
//查找两个邻近的相等元素，返回一个迭代器，指向两个元素中的第一个，找不到返回last。

Forwarditerator adjacent_find(Forwarditerator first,Forwarditerator last, BinaryPredicate binary_pred)
//查找两个邻近的相等元素，使binary_pred为true，返回一个迭代器，指向两个元素中的第一个，找不到返回last。

Forwarditerator1 find_first_of(Forwarditerator1 first1, Forwarditerator1 last1, Forwarditerator2 first2,Forwarditerator2 last2)
//在第二个范围内查找与第一个范围内某个相等的元素，返回的迭代器指向在第一个范围内那个元素，找不到返回last1。

Forwarditerator1 find_first_of(Forwarditerator1 first1,Forwarditerator1 last1,Forwarditerator2 first2,Forwarditerator2 last2,BinaryPredicate binary_pred)
//在第二个范围内查找与第一个范围内某个相等的元素，使binary_pred为true，返回的迭代器指向在第一个范围内那个元素，找不到返回last1。

Forwarditerator1 search(Forwarditerator1 first1,Forwarditerator1 last1, Forwarditerator2 first2,Forwarditerator2 last2)
Forwarditerator1 search(Forwarditerator1 first1,Forwarditerator1 last1,Forwarditerator2 first2,Forwarditerator2 last2,BinaryPredicate binary_pred)
//检查第二个范围内的元素是否与出现在第一个范围内（顺序也完全一致），返回指向在第一个范围内第二个序列出现的开始位置的迭代器，找不到返回last1。
第二种检测比较的每对元素是否使binary_pred为true。

Forwarditerator1 find_end(Forwarditerator1 first1,Forwarditerator1 last1,Forwarditerator2 first2,Forwarditerator2 last2)
Forwarditerator1 find_end(Forwarditerator1 first1,Forwarditerator1 last1, Forwarditerator2 first2,Forwarditerator2 last2,BinaryPredicate binary_pred)
//和search()用法相似，但是search()查找的是子集首次出现的位置，而find_end()则查找子集最后出现的位置。

template <class T1, class T2, class T3 = A>里面的class表示类型，不能用struct替换，但是可以用typename替换

当用某个模板类型下的成员前面需加上typename，但是不能用class更不能用struct
typename vector<T>::iterator it = v.begin();

vector<char> c;
.....
if(!c.empty()) size_t n=fun(&c[0],c.size()); //让fun把数据写入到c
string s(c.begin(),c.begin()+n); //通过c构造s

用empty()来代替检查size()是否为0
给map添加一个元素时，insert比operator[]效率高
更新已经在map的元素时，operator[]效率高
尽量用算法代替手写循环
尽量用成员函数代替同名算法

C++中重载[]要两个版本来满足需要：
char& String::operator[](int n)
{
return ch[n];
}
const char& String::operator[](int n) const
{
return ch[n];
}