C++【STL】 | STL Effective C++

vector不属于STL容器，其内部不存储bool，存储二进制位，无法使用bool来接收；
可使用deque替代，其内部保存真正的bool类型，相比于vector缺少了reserve和capacity；
可使用bitset不支持插入和删除元素，以及迭代器的使用；

若有两个值中的任何一个都不在另一个的前面，则该两个值为等价关系；

我们都知道关联容器会自动提供排序准则将数据进行排序，若我们设置的是指针类型，则它将无法准确的按照我们想要的进行排序，故我们将自定义排序准则；

/* 不要提供比较函数，因为它需要一个类型，类型内部创建一个函数，如下 */
struct StringPtrLess : public
        binary_function<const string*, const string*, bool>{
    bool operator()(const string *p1, const string *p2) const {
        return *p1 < *p2;
    }
};

void test() {
    typedef set<string*, StringPtrLess> sset;
    string s1 = "Java", s2 = "C++", s3="python";
    sset ss {&s1, &s2, &s3};
    set<string*>  s {&s1, &s2, &s3};

    cout << "my set" << endl;
    for(auto i: ss) {
        cout << *i << " ";
    }
    cout << endl;
    cout << "set" << endl;
    for(auto i:s) {
        cout << *i << " ";
    }
    cout << endl;
}

任何一个定义了严格弱序化的函数必须对相同值的两个拷贝返回false；
比较函数的返回值时按照函数定义的排序顺序，一个值是否在另一个之前，且相等值不会有前后顺序关系，故对于相等值返回false；
否则将会破坏容器；

在map和multimap中，键是const，是不允许修改的；
而set和multiset不是const说明还是可以修改的：
	- 但修改的时候需要注意不能修改到键的部分，否则会破坏容器的有序性；
	- 当然不同的编译器对它采取的措施并不一样，有些或许可以修改，有些或许禁止，可能会导致降低移植性；

以下测试中，使用强制类型转换，解决该上述问题：
const_cast成功将其修改非键部分；
static_cast没有将其修改成功；
	由于该静态转换只是作用于临时对象上，该临时对象是(*i)的拷贝，只是修改临时对象，故结果没有改变

class Employee {
public:
    Employee(int i) : m_id(i) {}
    Employee(int i, string n, string m) : m_id(1), m_name(n), m_title(m) {}
    const string& getTitle() const { return m_title; }
    void setTitle(const string& title) { m_title=title; }
    const int getId() const { return m_id; }
    const string& getName() const { return m_name; }
    void setName(const string& name) { m_name = name; }
private:
    string m_name;
    string m_title;
    int m_id;
};
/* 键为id */
struct IDNumLess : public binary_function<Employee, Employee, bool> {
    bool operator()(const Employee& lhs, const Employee& rhs) const {
        return lhs.getId() < rhs.getId();
    }
};

void test() {
    typedef set<Employee, IDNumLess> mySet;
    mySet s;
    s.insert(Employee(1, "1", "1"));
    auto i = s.find(1);
    if(i != s.end()) {
        //i->setName("one"); // 'this' argument to member function 'setName' has type 'const Employee', but function is not marked const
        //const_cast(*i).setName("one");       // ret: one
        //static_cast(*i).setName("one");     // ret: 1
    }
    cout << i->getName() << endl;
}

int main() {
    test();

    return 0;
}

如何安全修改关联容器种的元素

- 先查找到该元素；
- 为将要修改的元素做一份拷贝，且不要将其修改为const；
- 修改该拷贝；
- 将该元素在容器种删除；
- 将新值插入到容器内；
该方法将不会受移植性的限制；

void modify() {
    typedef set<Employee, IDNumLess> mySet;
    mySet s;
    s.insert(Employee(1, "1", "1"));
    auto i = s.find(1);
    if( i != s.end()) {
        Employee e(*i);
        e.setTitle("one");
        s.erase(i++);   // 此处递增保持迭代器的有效性
        s.insert(i, e);
    }
}

虽然说关联容器的查找性能很好，但如果散列函数选择得不适合等因素性能将会显著降低；
关联式容器一般的经历以下三个阶段：
- 设置阶段：插入数据；
- 查找阶段：查询数据；
- 重组阶段：删除数据，在插入新数据；
以上 *** 作相比于已排序的vector可能性能较低；
对于已排序的vector能够使用binary_search、lower_bound、equal_range等；

vector在哪些地方胜于关联容器

【大小】：关联容器是以红黑树为基础，其需要内部数据结构需要有左、右、父节点，至少比vector多出3个指针；
	当数据量大时，将会影响系统速度；
【速率】：排序的vector查找速度可能比关联容器更快；

如何使用vector替代关联容器

若使用vector代替map则需要使用pair，且需要自定义比较函数；
比较函数需要提供两个，一个用于排序，一个用于查找，或两个查找，为了兼容根据键还是pair来查找；

typedef pair<string, int> Data;
class DataCompare {
public:
    /* 用于排序 */
    bool operator()(const Data& lhs, const Data& rhs) const {
        return keyLess(lhs.first, rhs.first);
    }
    /* 用于查找 */
    bool operator()(const Data& lhs, const Data::first_type& k) const {
        return keyLess(lhs.first, k);
    }
    
    /* 第二种查找 */
    bool operator()(const Data::first_type& k, const Data& rhs) const {
        return keyLess(k, rhs.first);
    }
private:
    bool keyLess(const Data::first_type& k1, const Data::first_type& k2)const {
        return k1 < k2;
    }
};

void test() {
    vector<Data> vd;
    sort(vd.begin(), vd.end());
    string s("Hello");
    // 二分查找
    if(binary_search(vd.begin(), vd.end(), s, DataCompare())) {
        // ...
    }
    // 查找
    auto i = lower_bound(vd.begin(), vd.end(), DataCompare());
    if(i != vd.end() && !DataCompare()(s, *i)) {
        // ...
    }
    // 判断区间查找
    auto range = equal_range(vd.begin(), vd.end(), s, DataCompare());
    if(range.first != range.second){
        // ...
    }
}

map中的[] *** 作符提供了更新和插入的功能；
	- 当map中存在该对象将返回一个已有值对象的引用，
	- 当没有时将会默认构造新对象，作为当前索引的值，在将其做为引用返回，在赋值；【开销，临时对象的创建、析构、赋值】
若在插入的 *** 作中使用insert，将会提高程序的效率，节省上述的开销；

template<typename MapType, typename KeyArgType,
        typename ValueArgType>
typename MapType::iterator AddOrUpdate(MapType& m, const KeyArgType& k, 
                                       const ValueArgType& v) {
    /* 先确定在什么位置 */
    typename MapType::iterator lb = m.lower_bound(k);
    /* 是否存在 */
    if(lb != m.end() && !(m.key_comp()(k, lb->first))) {
        lb->second = v;
        return lb;
    }
    else{   // 不存在，则插入
        typedef typename MapType::value_type MVT;
        return m.insert(lb, MVT(k, v));
    }
}

hash_set、hash_multiset、hash_map、hash_multimap

STL中提供4中迭代器iterator、const_iterator、reverse_iterator、const_reverse_iterator；
迭代器间存在->即可通过隐式转换，也通过base()转换；
但无法通过const_iterator转换到iterator，也无法通过const_reverse_iterator转换到reverse_iterator；

在插入或删除 *** 作中，const_iterator一般不适用；
尽量使用iterator不适用const或reverse；

void test() {
    typedef deque<int> Intq;
    typedef Intq::iterator Iter;
    typedef Intq::const_iterator ConstIter;
    
    Iter i;
    ConstIter ci;
    /* 当编译器不通过时，尝试ci==i，若与const，则将iterator转换为const，可使用static_cast转换 */
    if(i == ci) {}
}

当只有const_iterator时，如何插入通过迭代器插入新数据？？？
我们创建一个与const_iterator指向同一位置的iterator；
	- 先创建一个新的iterator指向容器起点；
	- 在通过与const_iterator的距离移动相同的偏移量；
上述过程可能需要线性时间的代价，且需要访问const_iterator容器；

distance获取偏移量，advance移动距离

typedef deque<int> Intq;
typedef Intq::iterator Iter;
typedef Intq::const_iterator CIter;

void test() {
    Intq d;
    CIter ci;
    
    Iter i(d.begin());
    advance(i, distance<CIter>(i, ci));
}

insert

若在reverse_iterator插入元素，则将其转化为base，在插入；

void test() {
    vector<int> v;
    v.reserve(5);
    for (int i = 1; i <= 5; ++i) {
        v.push_back(i);
    }
    vector<int>::reverse_iterator ri = (vector<int>::reverse_iterator)find(v.begin(), v.end(), 3);
    vector<int>::iterator i(ri.base());
    cout << "ri:" << *ri << " r:" << *i << endl;
    v.insert(i, 10);
    for(auto x : v) {
        cout << x << " ";
    }
    cout << endl;
}

erase

由于不能对函数返回的指针进行修改，故将先递增在进行base转换；
(--ri.base()) ==>((++ri).base)
注意ri和ri.base()不等价，则需要通过移动；

void test() {
    vector<int> v;
    v.reserve(5);
    for (int i = 1; i <= 5; ++i) {
        v.push_back(i);
    }
    vector<int>::reverse_iterator ri = (vector<int>::reverse_iterator)find(v.begin(), v.end(), 3);
    v.erase((++ri).base());
    for(auto x : v) {
        cout << x << " ";
    }
    cout << endl;
}

istream_iterator通过>>来读取，当读取到空白字符时会默认跳过；
若需要保留空白，则需要通过设置标志位skipws即可；

ifstream inputFile("xxx.txt");
inputFile.unset(ios::skipws);
string fileData(istream_itreator<char>(inputFile), istream_itreator<char>());

对于上述 *** 作每次都需要设置标志位，STL中提供另一个方法istreambuf_iterator，用法和istream_iterator类似；
速度相比于istream_iterator提高了些许；

虽然STL能够正确管理它的存储空间，但使用某些算法时，容易忽略出现在无效对象使用赋值行为；
注意reverse()只是事先分配好空间，但并不对空间进行初始化；
resieze()会将其进行初始化 *** 作；

/** 由于ret中没有对象时，对其赋值无效，若使用resize则会给对象都进行初始化，即可 */
int op_increase (int i) { return ++i; }

void test() {
    vector<int> values {1, 3, 4, 6};
    vector<int> ret;
    //ret.resize(4);

    transform(values.begin(), values.end(), ret.begin(), op_increase);

    for(auto i : ret) {
        cout << i << endl;
    }
}

改进

使用back_inserter它将调用push_back()；

void test() {
    vector<int> values {1, 3, 4, 6};
    vector<int> ret;

    transform(values.begin(), values.end(), back_inserter(ret), op_increase);

    for(auto i : ret) {
        cout << i << endl;
    }
}

- STL提供partial_sort，当你只需要top前几的时候使用该函数即可，不需要对整个数组进行排序；
- nth_element提供和上述类似的功能，但它只挑取前几的元素，于前部，不对该区块进行排序；
	- 可以用来找到一个区间的中间值，或百分比上的值；
- stable_sort稳定的算法，排序后等价的元素相对位置不会发生变化；
以上算法以及sort都需要随机访问迭代器，只能应用于vector、string、deque、array；

- partition将所有满足条件的元素放置区间前部，由于完全排序需要大量的交换和比较，为了减少这些开销；
	- 将满足条件的元素放置前部至返回的迭代器区间，至结尾放置与条件不相符合的元素；
- stable_paritition提供稳定的版本；
partition只需由双向迭代器即可；

而对于list它由自己的成员函数能够进行排序，若需要使用以上的排序算法，则将其拷贝至其他容器即可；

算法效率根据时间、空间排序：
partition - stable_parition - nth_element -  partial_sort - sort - stable_sort；
在选择想要的算法前，需要先明确好实现功能；

nth_element

void test() { // 1 9 10 13 16 17 22 24
    vector<int> values {1, 13, 24, 16, 10, 9, 17, 22};
    auto begin(values.begin());
    auto end(values.end());
    vector<int>::iterator goalPos = begin + values.size() / 2;
    nth_element(begin, goalPos, end);
    for(auto i : values) {
        cout << i << " ";
    }
    cout << endl;
    cout << "goalPos mid: " << *goalPos << endl;

    vector<int>::size_type goalPosSet= 0.25 * values.size();
    nth_element(begin, begin + goalPosSet, end);
    cout << "in 25% : " << *(begin + goalPosSet) << endl;
}

partition

void test() { // 1 9 10 13 16 17 22 24
    vector<int> values{1, 13, 24, 16, 10, 9, 17, 22};

    auto it = partition(values.begin(), values.end(),[](int x){return x%2==0 ? true : false; } );

    for(auto i = values.begin(); i != it; ++i) {
        cout << *i << " ";
    }
    cout << endl;

    for(auto i = it; i != values.end(); ++i) {
        cout << *i << " ";
    }
    cout << endl;
}

remove不能推断出是什么容器，故删除容器中的元素时，不知道它删除哪个容器的元素，故容器元素数目不会减少；
它将所有要被删除的元素放在尾部，不用删除的元素放在前部；

remove实现

void test() {
    vector<int> values {1, 10, 24, 16, 10, 9, 10, 22};
    for(auto i: values) {
        cout << i << " ";
    }
    cout << endl;
    remove(values.begin(), values.end(), 10);

    for(auto i : values) {
        cout << i << " ";
    }
    cout << endl;
}

结合erase

// 由于返回下一个要覆盖的迭代器
void test() {
    vector<int> values {1, 10, 24, 16, 10, 9, 10, 22};
    for(auto i: values) {
        cout << i << " ";
    }
    cout << endl;
    auto it = remove(values.begin(), values.end(), 10);
    values.erase(it, values.end());
    for(auto i : values) {
        cout << i << " ";
    }
    cout << endl;
}

与之同类的算法还有remove_if和unique；

当容器中存放指针类型，在删除时容易造成资源泄漏；
在要remove前，我们应该将其指针置空，然后再删除；
v.erase(remove(begin, end, static_cast(0)), end);
当然，如果使用智能指针即可直接删除；
v.erase(remove_if(begin, end, not1(mem_fun(&class::icVarify))), end);

要求区间排序的算法：
binary_search、lower_bound、upper_bound、equal_range、set_union、set_intersection、set_difference、
set_symmetric_difference、merge、inplace_merge、includes
unique、unique_copy不一定需要排序；

binary_search、lower_bound、upper_bound、equal_range此类函数只有在已排序且随机迭代器下才具有对数时间的查找效率
否则需要线性时间；【注意在排序使用的排序准则，在后续的算法中也要使用相同的排序准则】
set_union、set_intersection、set_difference、set_symmetric_difference【集合 *** 作】在已排序的情况下，此类为线性时间的效率；
merge、inplace_merge在已排序的情况下，此类为线性时间的效率；

许多字符转换函数的返回值为int，由于在内部进行强制转换为unsigned char；
mismatch的第一参数接收短的字符串；

mismatch

int ciStrCmpImpl(const string& s1, const string& s2);

int ciStringCmp(const string& s1, const string& s2) {
    if(s1.size() <= s2.size()) return ciStrCmpImpl(s1, s2);
    else return -ciStrCmpImpl(s1, s2);
}

int ciStrCmpImpl(const string& s1, const string& s2) {

    auto p = mismatch(s1.begin(), s1.end(), s2.begin(), not2(ptr_fun(ciStringCmp)));
    if(p.first == s1.end()) {
        if(p.second == s2.end()) return 0;
        else return -1;
    }
    return ciStringCmp(*p.first, *p.second);
}

lexicographical_compare

该函数时strcmp的泛化版本，可以与任何类型值一起使用，可接受一个判别式

bool ciCharLess(char c1, char c2) {
    return tolower(static_cast<unsigned char>(c1)) <
            tolower(static_cast<unsigned char>(c2));
}

bool ciStringCmp(const string& s1, const string& s2) {
    return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), ciCharLess);
}

使用cstring函数

int ciStringCmp(const string& s1, const string& s2) {
	return strcmp(s1.c_str(), s2.c_str());
}

STL中copy算法：
copy、copy_backward、repalce_copy、reverse_copy、replace_copy_if、unique_copy、remove_copy、rotate_copy、
remove_copy_if、paritial_sort_copy、uninitialized_copy；
但STL中弃用了copy_if，那如果我们想要使用该如何实现？

template<typename InputIter, typename OutputIter, typename Predicate>
OutputIter copy_if(InputIter begin, InputIter end, 
                   OutputIter destBegin, Predicate p) {
    while (begin != end) {
        if(p(*begin)) *destBegin++ = *begin;
        ++begin;
    }
    return destBegin;
}

STL中对于数值的 *** 作算法一般使用：count、count_if、min_element、max_element；
对于区间中的统计处理由accumulate；

【for_each和accumulate的区别】：
- for_each对每一个元素做一个 *** 作，返回值为一个函数对象，通过该函数对象提取统计信息；
- accumulate对区间进行信息汇总，直接返回统计结果；

accumulate

/* 传入区间起点和终点，以及一个初始值，直接返回汇总后的值 */
template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init);
/* 传入区间起点和终点，以及初始值和一个 *** 作函数，直接返回汇总后的值 */
template <class InputIterator, class T, class BinaryOperation>
   T accumulate (InputIterator first, InputIterator last, T init,
                 BinaryOperation binary_op);
void test() {
    vector<int> vc {1, 3, 4, 5, 6};
    vector<int> vc2 {10, 30, 14, 15, 16};

    auto ret1 = accumulate(vc.begin(), vc.end(), 10);
    cout << "ret1: " << ret1 << endl;
    auto ret2 = accumulate(vc2.begin(), vc2.end(), 100, minus<int>());
    cout << "ret2: " << ret2 << endl;
}

for_each

/* 传入区间起点和终点，以及一个函数 */
template <class InputIterator, class Function>
   Function for_each (InputIterator first, InputIterator last, Function fn);
struct point {
    int x, y;
    point(int _x, int _y) : x(_x), y(_y) {}
};

class PointAvg : public unary_function<point, void>{
public:
    PointAvg() : xSum(0), ySum(0), numPoint(0) {}

    void operator()(const point& p) {
        ++numPoint;
        xSum += p.x;
        ySum += p.y;
    }

    point result() const {
        int x = xSum / numPoint;
        int y = ySum / numPoint;
        return point(x, y);
    }
private:
    int xSum;
    int ySum;
    size_t numPoint;
};

void test() {
    vector<point> vp;
    vp.emplace_back(1,2);
    vp.emplace_back(4,5);
    vp.emplace_back(1,3);
    vp.emplace_back(1,9);
    point avg = for_each(vp.begin(), vp.end(), PointAvg()).result();
    cout << avg.x << " " << avg.y << endl;

函数传递时，必须通过函数指针进行传递；
在STL中，函数指针是按值传递的；
由于STL中函数按值传递
	- 我们需要让函数对象尽可能地小，以至于不会有大的开销；
	- 函数对象必须是单态的，不得使用虚函数，在以传值的方式会被切割；
	- 函数对象的有点是可以带上状态信息；
***但在实际使用过程中，发现难免无法避免函数小巧，以及不适用到虚函数，该如何解决？？
	我们将所需的数据和虚函数从函数子类中分离，放到新类中，且在函数子类中包含一个指针，指向新类；

// 以下的返回值和参数都是按值传递
template<class InputIter, class Function>
Function for_each(InputIter first, InputIter last, Function f);

独立新类，让函数对象内部数据成员成为一个指针

需要注意的是如何处理拷贝构造，由于在STL中函数对象作为参数传递或返回总是被拷贝；

class Widge {
};

template<typename T>
class BPFC;

template<typename T>
class BPFCImpl : public unary_function<T, void> {
private:
    Widge* w;
    int x;
    virtual ~BPFCImpl();
    virtual void operator()(const T& val) const;
    friend class BPFC<T>;
};

/** 新类，将x、w数据成员抽出到新类中 */
template<typename T>
class BPFC: public unary_function<T, void> {
private:
    BPFCImpl<T>* pImpl;

public:
    void operator()(const T& val) const {
        pImpl->operator()(val);
    }
}

【判别式】：返回一个bool类型，一般用于排序，STL中要求判别式函数必须是纯函数；
	判别式类：为一个函数子类，operator()为一个判别式，其中对该函数必须声明为const，且为纯函数；
	STL中能接受判别式函数的就能够接受判别式类，接受判别式类的就能接受判别式函数；
【纯函数】：返回值仅依赖于其参数的函数，没有状态；

可配接的函数对象提供了（argument_type、first_argument_type、second_argument_type, result_type）必要的类型；
STL中提供4个标准函数配接器(not1, not2, bind1st, bind2nd)当我们自定函数时，且与配接器结合使用需要通过ptr_fun等
函数让我们自定义函数变成可配接；
若要让函数对象变成可配接函数，即通过基类继承即可（unary_function、binary_function）；

template<typename T>
class MeetsThreshild : public unary_function<Widget, bool> {
private:
	const T threshold;
public:
	bool operator()(const Widget&) const;
};

struct WidgetNameCmp : public binary_function<Widget, Widget, bool>{
	bool operator()(const Widget& lhs, const Widget& rhs) const;
};

struct WidgetNameCmp : public binary_function<Widget*, Widget*, bool>{
	bool operator()(const Widget* lhs, const Widget* rhs) const;
};

此类函数为了掩盖C++中一个内在语法不一致问题；
由于函数或函数对象在被调用的时候，总是使用非成员函数的语法形式，故在调用成员函数时编译不通过；
mem_fun带一个指向某成员函数的指针参数，并返回一个mem_fun_t的对象（函数子类）；
	- mem_fun_t拥有该成员函数的指针，提供了operator()函数；
mem_fun_ref（引用）：指针对对象容器的配接器；
另外还提供ptr_fun，该函数不会给程序带来性能损失，只会在阅读的时候会被考虑为何加上该函数进行修饰，若不注重阅读也可
将其加上；

class Widget {
public:
    Widget() {}
    void test() {
        cout << "test" << endl;
    }
    ~Widget() {}
};

void func(Widget *w) {
    cout << "out" << endl;
}

void test() {
    vector<Widget *> vc;
    vc.resize(2);

    for_each(vc.begin(), vc.end(), mem_fun(&Widget::test));
    for_each(vc.begin(), vc.end(), &func);
    //for_each(vc.begin(), vc.end(), &Widget::test);    // error
}

当我们要自定义排序准则时，需要创建一个函数子类，命名不能与less同名；
当然也不要对less版本进行特化；

struct MaxSpeedCmp ; public binary_function<Widget, Widget, bool> {
	bool operator()(const Widget& lhs, const Widget& rhs) const  {
		return lhs.maxSpeed() < rhs.maxSpeed();
	}
}

STL为我们提供各种算法，当内部有提供可以满足我们的需求是，我们应使用STL算法；
STL算法优点：
	- 效率，减少了繁琐的 *** 作，例如循环等；
	- 正确性，手写容易出现错误；
	- 可维护性， 代码简洁；
对于deque中数组，基于指针的遍历比基于迭代器的遍历要快，而只有库的内部实现才能使用基于指针的遍历；

void test() {
    deque<int> d;
    int arr[] = {1, 3, 4, 5, 6};
    int N = 5;
    /* 此类做法将插入后数据将会逆序，由于每次在begin插入 */
    for(size_t i=0; i<N; ++i) {
        d.insert(d.begin(), arr[i]);
    }
    /* 更正，但仍有问题 */
    auto it = d.begin();
    for(size_t i=0; i<N; ++i) {
        d.insert(it++, arr[i]);
    }
    /* 更正，为了保证it有效递增 */
    for(size_t i=0; i<N; ++i) {
        it = d.insert(it, arr[i]);
        i++;
    }
    
    /* 而使用STL，保证了不易出现错误，上述代码中不小心将会造成插入错误 */
    transform(arr, arr+N, inserter(d, d.begin()), plus<int>());
}

当我们的循环简单，使用STL算法来实现，要求混合使用绑定器和配接器或者要求一个单独的函数子类时，使用手写；

成员函数一般速度较快，由于成员函数与容器结合得更加紧密；
虽然其函数名称都一样，但内部所做的事情却大有区别；
例如：
	- set中成员函数以对数时间，而find算法确实以线性时间；
	- list中提供的成员函数无须任何对象拷贝，只是维护好指针；
使用成员函数的好处：
- 其成员函数对该容器具有针对性的 *** 作；
- 在时间效率上，能够获取对数时间的性能而不是线性；
- 对于关联容器可以使用等价性来确定两个值是否相同；
- 使用map等容器可以单独考虑键部分；

如果是已序区间，则通过binary_search、lower_bound、upper_bound、equal_range将会有对数的时间效率
若无序，则只能通过count、count_if、find、find_if来查找将获取线性时间效率；

我们将使用find和count；
【find】查找区间中的值，当查找第一个这样的值则返回；
【count】是通过区间中这样的值，需要从头遍历到尾；

【lower_bound】查找特定值时，不能用end来测试其返回值，应该检查返回对象是否等价于你要查找的值；if(i != vc.end() && *i == w)
【equal_range】：返回一对迭代器，第一个返回lower_bound，第二个返回upper_bound最后一个元素的下一个位置，如果返回两个迭代器相同，则为空；
p = equal_range(vc.begin(), vc.end()); if(p.first != p.second)

STL算法：
	对未排序的区间：
		- find：特定值是否存在，且其第一个值在哪；
		- cout：特定值有多少个；
		- count_if：特定值的前后；
	对已排序：
		- binary_search：特定值是否存在；
		- equal_range：特定值是否存在，且第一个值在哪；
		- lower_bound：第一个不超过特定值的对象在哪；
		- upper_bound：第一个在特定值之后的对象在哪；
		- equal_range：具有特定值的对象多少个，先确定区间，在使用distance；
		- equal_range：具有特定值的对象都在哪；
成员函数：
	对set或map：
		- count：特定值是否存在；
		- find：特定值是否存在且第一个在哪；
		- lower_bound：第一个不超过特定值的对象在哪；
		- upper_bound：第一个特定值后的对象在哪；
		- count：具有特定值的对象有多少；
		- equal_range：具有特定值的对象都在哪；
	对multiset或multimap：
		- find：特定值是否存在；
		- find或lower_bound：特定值是否存在，且第一个值在哪；
		- lower_bound：第一个不超过特定值的对象在哪；
		- upper_bound：第一个特定值后的对象在哪；
		- count：具有特定值的对象有多少；
		- equal_range：具有特定值的对象都在哪；

在STL中，将函数对象传递往往比传递实际的函数更加高效；
如果一个函数对象的operator()函数被声明为内联，则该函数体将可以直接被编译器使用；
【函数指针抑制内联机制】当函数作为参数传递时，一般会隐式将其转化为函数指针，而后产生一个间接的函数调用（通过指针），而编译器一般不会试图对通
过函数指针执行的函数调用做内联优化；
函数对象中，C++必须先实例化函数模板和类模板，在调用operator()函数，只是简单函数调用，且负担都在编译期间消化；

template<typename FPTyep>
struct Average: public binary_function<FPType, FPType, FPType> {
	FPType operator()(FPType v1, FPType v2) {
		return average(v1, v2);
	}
}

代码阅读次数远大于编写次数，故需要能够让阅读者看懂，易于理解；

SGI STL：http://www.sgi.com/tech/stl
STLport：http://www.stlport.org
Boost：http://www.boost.org