Effective STL中文版

20140311-effective-stl-notes.txt

Effective STL中文版
跳转至： 导航、 搜索
目录

    1 容器
    2 关联容器
    3 迭代器
    4 算法
    5 函数对象
    6 在程序中使用STL
    7 附录A 地域性（locale）和忽略大小写的字符串比较

容器

    string vs vector<char>
    插入删除的事务语义：list
    不要试图编写独立于容器的算法
    善用typedef节省代码量
    Copy In, Copy Out（对象的副本）
    使用empty()而不是size()==0，后者可能需要线性时间
    尽量使用区间（Range，[begin, end)左闭右开）的概念（哪怕是只有一个元素）
        assign
        insert
        erase 
    避免声明匿名的istream_iterator对象：istream_iterator<int>(file)会被当作一个参数声明，而不是临时对象构造
    不要从string继承
        string没有virtual dtor（What？？？） 
    把模板从类移动到它的成员函数上（自动模板参数推导？）
    使用boost::shared_ptr（与STL容器配合）
    不要包含auto_ptr对象！（C++标准规定它不应该通过编译！）
        sort中会创建一个临时对象，而这将导致被复制的容器内对象被销毁 
    对连续内存容器（vector, string, deque），删除所有特定value的元素：erase-remove
        对于list，可直接remove
        对关联容器，使用erase
        remove_if：自定义过滤逻辑
            对关联容器，使用remove_copy_of，先收集需要的元素到临时容器，然后与原容器swap
            自己写一个：if(badValue(*it))c.erase(it++); else ++it; 
        it=c.erase(it); //对序列容器，删除的同时指向下一个有效的元素 
    allocator
        pointer和reference类型，STL实现允许假定就是T*和T&
        p47 STL实现可以假定同一类型的allocator是等价的，这实际上意味着可移植的allocator对象不可以有状态
        注意list<T>容器，它需要的是包含T的ListNode的内存，而不是allocator返回的T*
            ListNode的类型：Allocator::rebind<ListNode>::other 相当于重新映射了一下 
    关于线程安全，你最多只能期望：
        多个线程读是安全的
        多个线程对不同的容器写是安全的
        =〉可使用自己的AutoLock模板类。。。 
    reserve
    如何把vector/string传给C API
        vector：&*v.begin() 或 &v[0]
        s.c_str() 只读
        vector再到string 
    swap
        “Shrink to fit”：string(s).swap(s) 
    vector<bool>：它（1）不是一个STL容器；（2）它不存储bool
        备选方案：deque<bool> bitset（标准C++库） 

关联容器

    理解相等（equality, equals operator==）和等价（equivalent，operator<）
        A与B等价意味着A、B之间不存在偏序关系 
    为包含T*的容器指定比较类型
        typedef set<string*, StringPtrLess> StringPtrSet; //StringPtrLess可进一步泛化为一个functor模板 
    总是让比较函数在等值情况下返回false
        a>b的实现是b<a（STL总是使用operator<）,a==b意味着没有<关系，所以是false 
    切勿直接修改set/multiset中的key
        map/multimap的key是const的，set/multiset不是
        const_cast<T&>(*it).setXxx(...)
            更好的做法：detach --> 修改 --> attach 
    使用有序vector+binary_search代替关联容器
    map::operator[]在键k不在map中的情况不如直接map::insert效率高
        但‘更新’时operator[]更好
        自定义一个insertOrUpdate（这让我想到了SQL语句的INSERT/UPDATE） 
    散列容器：SGI vs Dinkumware 

迭代器

    iterator优先于const_iterator、reverse_iterator及const_reverse_iterator ？
    使用distanc和advance将const_iterator转换为iterator ？
        不能通过const_cast直接转
        Iter it(c.begin()); advance(it, distance<ConstIter>(it, cit)); //注意，iterator可安全转换为const_iterator 
    * reverse_iterator.base()的问题
        v.erase((++ri).base()); 
    对于逐个字符的输入考虑用istreambuf_iterator
        istream_iterator的默认operator>>默认会跳过空白字符，需要ifstream.unsetf(ios::skipws);
            但由于它执行了格式化输入，不够快 

算法

    front_inserter（无法用于vector）
    partial_sort：只排序前N个
        nth_element（不稳定，基于swap？）
        stable_sort 
    partition：返回begin()到谓词匹配的结果结束位置
    remove：移动了区间内的元素，并没有真正删除之（需之后再调用erase）
        list.remove：直接删除
        当存储的是原始指针时，避免使用remove（及remove_if、unique），而是partition更合适 
    了解哪些算法要求排序的区间
        binary_search lower_bound upper_bound
        equal_range
        set_union set_intersection set_difference set_symmetric_difference
        merge inplace_merge
        includes 
    mismatch、lexicographical_compare
    没有copy_if
    accumulate
        位于<numeric>中，其他3个：inner_product adjacent_difference partial_sum 

函数对象

    假设函数对象是按值传递的（+ Pimpl习俗）
    应是一个“纯函数”（不仅仅加const修饰）
    可配接：not1(ptr_fun(predicate_))
        ptr_fun提供了not1需要的类型信息：argument_type first_argument_type second_argument_type result_type
            class MyCompare : public std::binary_function<T, T, bool>{ bool operator()(const T&, const T&) const; }; 
    ptr_fun、mem_fun和mem_fun_ref
        for_each(c.begin(), c.end(), mem_fun(&C::f)); //这里c里元素是对象指针，如果是对象则用mem_fun_ref（有点不大好记！）
        需要传入函数时，总是用ptr_fun包装一下：没有性能损失 
    operator<是less的默认实现，确保两者行为一致 

在程序中使用STL

    学会使用STL算法以避免手写的循环，如bind2nd
        局部类不能作为模板参数（但C++ 11现在不是有lambda了吗） 
    成员函数优先于同名算法
        set的find
        list的remove、remove_if、unique、sort、merge、reverse 
    正确区分count、find、binary_search、lower_bound、upper_bound和equal_range
        区别count与find
        count与find使用相等性，其他的使用等价性
        equal_range = [lower_bound, upper_bound) 
    函数对象比普通函数指针更高效，原因是前者可以内联优化，后者不能（？！）
    避免Write-Only（深度组合的函数调用） 

附录A 地域性（locale）和忽略大小写的字符串比较

    std::locale::classic()
    std::locale L("de");
        ct = std::use_facet<std::ctype<char> >(L);
        ct.toupper(c1)
            toupper是virtual的，应该缓存其转换结果？（有点像Font/TypeFace Cache的处理逻辑） 
    collate平面