2021-10-24发表2022-11-23更新 cx C++1 小时读完 (大约6939个字)0次访问

《effective STL》书摘与感悟记录

[TOC]
本文记录一下《effective STL》书摘与感悟记录.
目的有三:

加强学习效果,只是瞄一遍很难确保自己掌握通过总结摘要考核自己的理解,加强印象.
方便事后的查阅,书不在手边时翻阅本文会快一些,更何况是用了自己的语言总结出来的.
方便以后有新的感触实际经验后对相关内容进行补充,实现学习的真正闭环.
至于为什么选择学习这本书,一是对STL感兴趣,二是由应用入口学习C++的一些特性更生动一些.

容器

I1.选择合适的容器

选容器要考虑的一些方面:

任意位置插入元素?Y:序列容器
元素预先排序?N:不要考虑哈希容器
标准C++容器?Y:不要考虑slist,rope等
迭代器选择:随机访问?双向访问?
删除插入元素时,避免移动元素?:Y避免随机访问容器
C兼容?Y:vector
查找速度优先?Y:哈希容器
引用计数是否介意?Y:避免使用string/rope
对删除插入操作是否需要事务语义(方便回滚等)?Y:list
减少迭代器/引用/指针无效次数?Y:基于节点list
swap会使迭代器/指针/引用无效,介意吗?Y:避免string
deque是唯一尾部插入迭代器失效但是指针/引用有效的容器

I2.不要试图编写独立于容器类型的代码

不要试图写出代码适用于N种容器的代码.
如果有需求更换容器,使用封装成类或者是typedef的形式.

I3.确保容器中的对象拷贝正确并高效

核心概念:是容器中存储了对象而不是提供容器给对象,换言之,容器的一切基于拷贝.不仅包括内置类型的按位拷贝,还包括对象的拷贝构造函数以及拷贝赋值函数等.
拷贝剥离问题(slicing),基类容器里插入派生类导致派生类性质丢失.
解决剥离,可以存入对象指针,甚至是智能指针.
容器看起来难用,也要跟更难用的数组比.

I4.调用empty而不是size检查为空与否

前提:不同平台的STL实现不同,因此需要编写共同支持的最优.
empty对所有的标准容器都是常数操作时间.size不一定,例如list的splice拼接与size的效率无法两立.

I5.区间成员函数优于与之对应的单元素成员函数

区间函数优于单元素函数的原因:

阅读性强,没有循环,省代码.
效率高,在三个方面.
- 1. 函数调用次数上,区间函数只调用1次.
- 1. 单元素函数可能导致每次循环移动容器元素,如果是list的话,可能导致频繁更新所有元素前后向指针.
- 1. 单元素函数可能触发多次扩容.

区间函数的分类

区间创建(注意istream_iterator与istreambuf_iterator).

区间插入(insert)

v1.assign(v2.begin()+v2.size()/2, v2.end);
//优于下面
v1.clear();
copy(v2.begin()+v2.size()/2, v2.end,back_inserter(v1));

区间删除(erase)
区间赋值(assign)

I6.当心C++编译器最烦人的分析机制

例子如下:

1
2
3

ifstream dataFile("int.dat");
list<int> data((istream_iterator<int> (dataFile),istream_iterator<int>()); //Not OK, data变量会被编译器解析成函数声明,而不是构造函数
list<int> data((istream_iterator<int> (dataFile)),istream_iterator<int>()); //OK only on standard STL platform,加()跳过编译的分析机制

更普适的写法:

ifstream dataFile("int.dat");
istream_iterator<int> dataBegin(dataFile);
istream_iterator<int> dataEnd();
list<int> data(dataBegin,dataEnd);

c++11可以使用{}进行初始化,也可以解决这个问题.

I7. 如果在容器中用new创建了指针,不要忘记在容器对象析构的时候delete指针

STL没有智能到管理new出来的内存.

使用delete操作类删除指针,如下.但是依旧可能会出现删除前的异常抛出导致内存泄漏.

struct DeleteOnject{
    template<typename T>
    void operator()(const T* ptr) const
    {
        delete ptr;
    }
}

void dosomething(){
    deque<SpecialString*> dssp;
    for_each(dssp.begin(),dssp.end(),DeleteObject());
}

彻底解决,使用std::shared_ptr(boost::shared_ptr)管理.

void dosomething(){
    typedef std::shared_ptr<Widget> SPW;
    vector<SPW> vwp;
    for(int i=0; i<N; ++i)
    {
        vwp.push_back(SPW(new Widget));
    }
}

I8. 切勿包含auto_ptr创建的容器对象

auto_ptr被越来越多的平台摒弃,非法.
auto_ptr会在复制时改变原值为NULL.
容器不使用auto_ptr的原因之一:例如vector的sort排序使用了快排,会改变某些元素为NULL.

I9. 慎重选择删除元素的方法

删除容器中所有特定值的对象
- vector,deque,string: erase-remove
  1
  c.erase(remove(c.beging(),c.end(),DeleteObj),c.end());
- list: remove
  1
  c.remove(DeleteObj);
- 标准关联容器: erase成员函数.

删除容器中满足特定判别条件的所有对象

vector,deque,string: erase-remove_if
list: remove_if

标准关联容器: 1.remove_copy_if和swap. 2. 循环遍历单元素删除.

//方法1
AssociateContainer<int> c;
AssociateContainer<int> goodvalues;
remove_copy_if(c.begin(),c.end(),inserter(goodvalues, goodvalues.end()), badvalue);
c.swap(goodvalues);
//方法2
for(AssociateContainer<int>::i = c.begin();
   i!=c.end();
   )
{
    if(badvalue(*i) c.erase(i++));//此处的巧妙是i传给erase是原值,同时会在删除对象导致i失效之前增加1指向下一个对象.
    else ++i;
}

要在循环内部做了除了删除之外的操作(例如打印日志)

标准序列容器: 循环遍历,并使用erase返回值更新迭代器.无法使用erase/remove直接写日记,因为删除元素后被删元素及其之后的所有迭代器都无效

ofstream logFile;
SeqContainer<int> c;
for(SeqContainer<int>::iterator i=c.begin();
   i!=c.end();
   )
{
    if(badvalue(*i)){
        logFile<<"Erasing"<<*i<<'\n';
        i=c.earse(i); //把erase的值返回给i,使i保持有效
    }
    else ++i;
}

非标准序列容器: 循环遍历,迭代器要做后缀递增

ofstream logFile;
AssociateContainer<int> c;
for(AssociateContainer<int>::iterator i=c.begin();
   i!=c.end();
   )
{
    if(badvalue(*i)){
        logFile<<"Erasing"<<*i<<'\n';
        c.earse(i++);
    }
    else ++i;
}

I10.了解分配子(allocator)的约定和限制

分配子是一个模板,模板参数T代表要为它分配内存的对象类型.
分配子提供类型定义pointer和reference,但是始终让pointer为T*,reference为T&.
分配子不要拥有随对象不同而有不同的状态(per-object state),也就是说不能拥有静态数据成员,否则能通过编译可能运行时破坏数据结构.
allocate成员函数的参数为对象的个数,而不像new一样给出字节数.同时该函数返回的T*指针但是T并没有构造出来(new返回的是void*,即未分配内存).

一定要提供一套被容器依赖的嵌套的rebing模板.

template<typename T>
class allocator{
    public:
        template <typename U>
        struct rebind{
            typedef allocator<U> other;
        };
        ...
}
//通过引用Allocator::rebind<ListNode>::other,List<T>就能从T对象的分配子得到ListNode对象的分配子.

I11.理解自定义分配子的合理用法

未完全搞明白…

I12.切勿对STL容器的线程安全有不切实际的依赖

对于STL的线程安全只有2个期待,不能依赖.

多个线程读是安全的.
多个线程对不同容器的写入操作是安全的.

手动同步控制,使用Lock类,对于异常发生也是健壮的.

template<typename Container>
class Lock{
    public:
        Lock(const Container& container):c(container){
            getMutexFor(c);
        }
        ~Lock(){
            releaseMuteFor(c);
        }
    private:
        const Container& c;
}

//实际应用,找到等于5的位置并置0
vector<int> v;
{
    Lock<vector<int>> lock(v);
    vector<int>::iterator first5(find(v.begin(),v.end(),5));
    if(first5 != v.end())
    {
        *first5=0;
    }
}

vector和string

I13.vector和string优先于动态分配的数组

vector/string的好处,内存生命周期的自动管理,算法的内置,C API的兼容等.
不使用string的特例,多线程环境下的使用引用计数的string.可以使用vector/预处理关闭引用计数/替换string实现.

I14.使用reserve避免不必要的重新分配

vector/string的realloc的过程:容量加倍->旧元素全部复制到新内存里->析构掉旧内存里的对象->释放旧内存.不想在这个过程中浪费资源,请使用reserve.
可以先reserve一个大些的内存后期去除多余的空间.

I15.注意string的多样性

string包含的信息:字符串的大小size,内存容量capacity,字符串的值value[],分配子的拷贝(可选),引用计数(可选).
string实现举例:

A
B支持多线程(other),动态分配2次内存
C一整块内存,X存储了可共享性信息,没有对单个对象的分配子支持
D小字符串优化,没有引用计数,新建时不会导致任何动态内存分配

I16.了解如何把vector/string传到C API

使用&v[0]而不是v.begin()传递指针,v.begin()返回的迭代器看似指针不是指针.

void doSomething(const int*pInts, size_t numInts);
//=>
if(!v.empty()){
    doSomething(&v[0],v.size());
}

void doSomething(const char* pString);
//=>
doSomething(s.c_str());//不用考虑string为空,string内部的空字符解释后会被理解为C里字符的结束标志.

string转换后无法修改/添加元素,因为指向的是不可修改的拷贝.
vector转换后理论上可以修改/添加元素但是注意不要导致size的变化,附加属性(sort后)的变化.

C API初始化vector(参见下面初始化string的例子).string/deque/list/set等容器都是通过vector完成的转换(区间复制).

size_t fillString(char* pArrary,size_t arraySize);
vector<char> vc(maxNumChars);
size_t charsWritten=fillString(&v[0],vc.size(0));
string s(vc.begin(),vc.end()+charsWritten);

I17.使用swap去除多余容量

通过拷贝构造创建临时变量(最小内存)交换现容器去除多余容量.
1
vector<Obj>(obj).swap(obj).
swap还可以用来清除容器,同时容量缩减至最小.
1
string().swap(s);

I18.避免使用vector<bool>

问题点:vector<bool>是个假的容器,表面上看是bool对象存储其实存储的是二进制位.
1
2
vector<bool> v;
bool *pb = &v[0]; //错误
vector<bool>的初衷是通过代理对象(proxy object)实现,但是失败了.
vector<bool>的替代品:

deque<bool>(对比vector,只有reserve与capacity没有)
bitset(非STL,不支持迭代器,编译时确定大小,不支持插入删除,含有flip等成员函数)

关联容器

I19.理解相等(equality)和等价(equivalence)的区别

equality可以理解为对应的是==运算符,find函数的比对方法.关联容器里默认无,自己可以i指定,处理不当有风险.
equivalence可以理解为对应的是<,><=,>=运算符,排序函数的比对方法.是关联容器默认的相同的概念.下面的x,y为equivalent.
1
2
3
!c.key_comp()(x,y) && !c.key_comp()(y,x);
//即
!(x<y) && !(y<x);
标准关联容器是基于equivalence来实现排序的,与此同时借用equivalence的方式实现了==的判断,即上面的代码.
如果希望区分equivalence与equality则需要指定equality判断函数或者是重载==(惯例选择重载),如下.
1
set2CF<string, CIStringCompare, equal_to<string> > s;//CIStringCompare忽略大小写进行排序
但是这会导致新的问题,例如stl与STL可以insert进入(不equal),但是无法排序(equivalent),导致混乱.
还有一点需要注意,成员函数与算法函数的区别.
例如成员函数的find可以调用equivalence方法(默认无equality方法),但算法函数find会调用算法里的equality方法导致两种函数结果不同.

I20.为包含指针的关联容器指定比较类型

指针对象无法遵照容器默认比较方法比较指针指向对象.因此有必要创造比较函数子类.

struct StringPtrLess:
public binary_function<const string*, const string*,bool>
{
    bool operator()(const string *ps1, const string *ps2) const{
        return *ps1 < *ps2;
    }
};
typedef set<string*,StringPtrLess> StringPtrSet;
StringPtrSet ssp;
...
//依次打印排序后
//方法1:显示循环
for(StringPtrSet::const_iterator i=ssp.begin();i!=ssp.end();++i){
    cout << **i << endl;
}
//方法2:for_each算法函数
void print(const string *ps){
    cout << *ps << endl;
}
for_each(ssp.begin(),ssp.end(),print());
//方法3:transform+ostream_iterator
struct Derefence{
    template<typename T>
    const T& operator()(const T *ptr) const{
        return *ptr;
    }
};
transform(ssp.begin(),ssp.end(),ostream_iterator<string>(cout, "\n"),Derefence());

不要传入函数进入比较函数,不支持的类型,编译不通过.
对于智能指针/迭代器也有必要类似地指定比较函数.

I21.总是让比较函数在等值情况下返回false

若对等值的情况返回true,则等值的对象会被放入容器中,破坏容器.即便是multiset,multimap也不会视等值对象为相同的元素,例如equal_range不会识别.
抽象起来:比较函数必须为它们所比较的对象定义一个严格的弱序化(strict weak ordering).

I22.切勿直接修改set或multiset中的键

set/multiset,大前提,不要修改key部分,否则影响排序性.若不关心移植性,STL允许的话可以修改元素.若重视移植性,不要修改任何元素,至少不能不经过const_cast就修改.
static_cast只不过创建了一个临时对象,虽然能通过编译,但依旧改不了const性质的对象.
map/multimap中的key为const类型,只能通过const_cast修改,但一般不要这么做(遵守规定).

安全的修改方式:

EmployeeSet::iterator i = se.find(ID); //第一步,找到修改元素
if(i!=se.end()){
    Employee e(*i);//第二步,拷贝元素
    e.setTitle("aa");//第三步,修改拷贝元素
    se.erase(i++);//第四步,删除元素,递增迭代器保持其有效性
    se.insert(i,e);//插入修改后元素
}

I23.考虑用排序的vector代替关联容器

关联容器,实现为平衡二叉树,综合能力强,查找/插入/删除后重组很平衡.
排序vector,优点在于连续内存省内存,减少内存页面错误机率,性能也更好.关键在于排序函数的创建/指定上.例如下面的排序函数.

typedef pair<string,int> Data;
class DataCompare{
    public:
    bool operator()(const Data& lhs, const Data& rhs) const{ //用于排序的比较函数
        return keyLess(lhs.first,rhs.right);				//keyLess意思为<
    }
    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);
    }
}

vector<Data> v;
...
sort<v.begin().v.end()>;
string s;
//三种查找方式
//binary_search
if(binary_search(v.beging(),v.end(),s,DataCompare())){}

//lower_bound
vector<Data>::iterator i=lower_bound(v.begin(),v.end(),s,DataCompare());
if(i!=v.end() && !DataCompare()(s.*i)){}

//equal_range
pair<vector<Data>::iterator, vector<Data>::iterator> range=equal_range(v.beging(),v.end(),s,DataCompare());
if(range.first!=range.second)

I24.当效率至关重要时,在map::operator[]与map::insert之间谨慎选择

insert在添加元素效率更高,[]会创建临时的对象与赋值操作.

1	m.insert(IntWidgetMap::value_type(1,1.5));

[]在更改元素上效率更高,因为insert需要构造value_type(pair)对象以及Widget对象.
可以编写区分添加/更改场景选择不同方法的接口.

这里的参数(KeyArgType/ValueArgType)只要能转换为映射表里的类型即可,如果使用MapType::key_type/MapType::mapped_type的话注意可能会产生构造表元素类的成本.

I25.熟悉非标准的散列函数

SGI的实现已经成为c++11的标准了,使用std::hash自定义hash函数.所以这篇文章就不记录摘要了吧.

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

迭代器

I26.iterator优于constant_iterator,reverse_iterator,const_reverse_iterator

四种迭代器之间的关系,没有箭头指向的表示无法隐式转换.

某些函数(insert/erase)的某些版本要求使用iterator.
iterator与const_iterator一般可以比较,例如 i==ci,如果编译不过可以尝试ci==i,或者static_casr<constant_iterator> i.混用还是有风险.

I27.使用distance和advance将容器的const_iterator转换为iterator

const_cast<const_iterator>(iterator)强制转换不会成功,因为const_iterator与iterator完全不同.
通过移动iterator到const_iterator位置实现转换.

typedef deque<int> IntDeque;
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
IntDeque d;
ConstIter ci;
Iter i(d.begin());
advance(i,distance<ConstIter>(i,ci));

I28.正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

reverse_iterator及其base()后的iterator位置关系如下图.

插入操作,由于是插入到插入位置的前一个位置,因此base()前后的迭代器结果不变.
删除操作,i位置要提前,但不要使用v.erase(--ri.base)的形式.某些平台vector/string的迭代器是内置指针,返回指针不允许被修改.

改为v.erase((++ri).base())

I29.对逐个字符的输入考虑使用istreambuf_iterator

istreambuf_iterator效率高,不会跳过空白等字符,替代istream_iterator.类似地ostreambuf_iterator.

1 2	ifstream inputFile("1.txt"); string fileData((istreambuf_iterator<char>(inputFile)),istreambuf_iterator<char>());

算法

I30.确保目标区间足够大

容器的自动扩容是伴随着push_back/push_front类似的添加操作才会运行.在执行与添加操作无关的函数时,要保证区间够大,或者是增大区间.

增大区间可以通过插入型迭代器实现,例如back_inserter,front_inserter,inserter,ostream_inserter.

vector<int> v;
vector<int> r;
r.reserve(r.size()+v.size());
transform(v.begin(),v.end(),r.end(),transformFunction);//错误,r没有可以内存.

transform(v.begin(),v.end(),back_inserter(r),transformFunction);//正确,back_inserter会增加空间.

I31.了解各种与排序有关的选择

vector,string,deque,array全排序:sort/stable_sort(原地).
vector,string,deque,array只对等价性最前面的n个元素排序:partial_sort.
vector,string,deque,array找到第n个位置上的元素,或者是找到等价性最前面的n个元素但又不用排序时(例如求中位数,排序占比):nth_element.
标准序列容器按照是否按照某个特定条件区分开:partition/stable_partition.
list,list::sort代替sort/sort_stable.
list,实现partitial_sort/nth_element方法:

list复制到随机访问容器中再排序.
创建list::iterator容器,对该容器排序后用迭代器访问list元素.
使用splice成员函数反复调整位置.

priority_queue虽然不是标准容器(虽然是标准涵盖的内容但不是容器),也可以实现排序.
算法性能排序:partition > stable_partition > nth_element > partial_sort > sort > stable_sort.

I32.如果确定要删除元素,在remove后调用erase

不要被remove的字面意思误导,remove无法删除元素,它只是把满足输入的元素移到末尾,把不满足的元素依次前移填充移除后的空洞.
满足输入的元素会被压缩成一个元素并附加在容器尾部,返回指向它的迭代器.
能对容器进行删除操作的是erase操作.
1
v.erase(remove(v.begin(),v.end(),99),v.end());
list特例,没有erase函数,其与remove合并为remove,并且调用remove成员函数比erase-remove算法函数更高效.
同样地适用于remove_if/unique函数

I33.对包含指针的容器时使用remove类算法时要特别小心

remove/remove_if/unique压缩原容器可能导致被删除指针没有被释放,导致内存泄漏.

正确做法1:删除指针并置其为空然后再用erase-remove删除空指针.

void delAndNullifyUncertified(Widget*& pWidget){
    if(!pWidget->isCertified()){
        delete pWidget;
        pWidget=0;
    }
}
for_each(v.begin(),v.end(),delAndNullifyUncertified);
v.erase(remove(v.begin(),v.end(),static_cast<Widget*>(0)),v.end());

正确做法2: 使用智能指针存储,直接erase-remove删除即可.

1	v.erase(remove_if(v.begin(),v.end(),not1(mem_fun(&Widget::isCertified)),v.end());

I34.了解哪些算法需要排序区间作为参数

搜索类:binary_search/lower_bound/upper_bound/equal_range:二分法查找,对数时间效率.
set操作类:ser_union/set_intersection/set_difference/set_dymmetric_difference,线性时间效率.
合并类:merge/inplace_merge,线性时间效率.
includes判断一个区间是否都在另一个区间内,线性时间效率.
这些算法如果输入区间不是已经排好序的话效率会很低.
同时注意定义排序的比较函数与删除时的比较函数一致,都是”等价”性判断.
unique/unique_copy比较函数为”相等”性判断.

I35.通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较

定义比较函数,使用mismatch比较,返回第一个不一致的2个迭代器.

int ciCharCompare(char c1, char c2){
    int lc1=tolower(static_cast<unsigned char>(c1));
    int lc2=tolower(static_cast<unsigned char>(c2));
    if(lc1>lc2) return -1;
    if(lc2<lc1) return 1;
    return 0;
}

int ciCtringCompareImpl(const string &s1, const string &s2);{
    typedef pair<string::const_iterator,string::const_iterator> PSCI;
    PSCI p=mismatch(s1.begin().s1.end(),not2(ptr_fun(ciCharCompare)));//not2的意义为mismatch与ciCharCompare的终止循环条件相反
    if(p.first==s1.end()){
        if(p.second==s2.end() return 0;)
        else return -1;
    }
    else return ciCharCompare(*p.first,*p.second);
}

int ciStringCompare(const string &s1, const string &s2)
{
    if(s1.size()<=s2.size()){
        return ciCtringCompareImpl(s1,s2); //mismatch要求第一个参数区间比第二个短
    }
    else return -ciCtringCompareImpl(s2,s1);
}

使用lexicographical_compare算法,泛化版的strcmp函数,可以与任意类型的区间一起工作.

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

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

把string换成char[],使用strcmp活strcmpi.

I36.理解copy_if的正确实现

STL标准里没有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;
    }
    return destBegin;
}

I37.使用accumulate或者for_each进行区间统计

accumulate头文件在<numeric>中
accumulate有2种形式:

2个迭代器+初始值:计算累计和
2个迭代器+数值函数+初始值:区间某种统计计算

string size_type stringLenSum(string:size_type sumSoFar, const string& s) //每种标准容器都有Container::size_type,==size_t.
{
    return sumSoFar + s.size();
}

set<string> ss;
...
string::size_type lenSum = 
    accumulate(ss.begin(),ss.end(),static_cast<string::size_type>(0), stringLenSum) //计算set中所有字符串的长度总和

注意accumulate的初始值参数必须输入正确的double/int等数值类型,否则会导致精度丢失.
复杂对象的统计工作时,例如求解所有点列的x,y坐标平均数.瑕疵是产生了numPoints,xsum,ysum的副作用.

struct Point{
    Point(double initX, double initY):(x(initX), y(initY)){}
    double x,y;
}

class PointAverage: public binary_function<Point, Point, Point>{
public: 
    PointAverage():xsum(0),ysum(0),numPoints(0){}
    const Point operator()(const Point& avgSoFar, const Point &p)
    {
        ++numPoints;
        xsum+=p.x;
        ysum+=p.y;
        return Point(xsum/numPoints,ysum/numPoints);
    }
private:
    size_t numPoints;
    double xsum;
    double ysum;
    
}

list<Point> lp;
...
Point avg = accumulate(lp.begin(),lp.end(),Point(0,0),PointAverage());

for_each可以实现类似的功能,但其返回的为函数对象,需要转换一下,并且不会产生副作用.

struct Point{
    Point(double initX, double initY):(x(initX), y(initY)){}
    double x,y;
}

class PointAverage: public urary_function<Point,void>{
public: 
    PointAverage():xsum(0),ysum(0),numPoints(0){}
    const Point operator()(const Point& avgSoFar, const Point &p)
    {
        ++numPoints;
        xsum+=p.x;
        ysum+=p.y;
        return Point(xsum/numPoints,ysum/numPoints);
    }
private:
    size_t numPoints;
    double xsum;
    double ysum;
    
}

list<Point> lp;
...
Point avg = for_each(lp.begin(),lp.end(),Point(0,0),PointAverage()).result();

函数子,函数子类,函数其其他

I38.遵循按值传递的原则来设计函数子类

STL可以使用引用的形式传递,但不要这么做,使用按值传递.
按值传递的问题:保证函数小(拷贝成本),单态(不得使用虚函数,否则会对传入的派生类参数产生剥离slicing problem).
解决上述问题的思路之一:Bridge Pattern(Pimpl Idion).

template<typename T>
class BPFCImpl{
private:
    Widget w;
    int x;
    
    virtual ~BPFCImpl();
    
    virtual void operator()(const T& val) const; //保持多态
    friend class BPFL<T>;		//BPFL可以访问数据
};

template<typename T>
class BPFC:public unary_function<T, void>{
private:
    BPFCImpl<T> *plmpl;	//唯一的成员数据为指针,小
public:
    void operator()(const T &val) const
    {
        plmpl->operator()(val); //非虚函数里转接调用
    }
};

存的指针可以考虑换成智能指针

I39.确保判别式是纯函数

纯函数,其返回值仅仅依赖于参数,内部不存在中间值能潜在地改变输出.
判别式类(predicate class)是一个函数子类,其operator()函数为一个判别式,返回true/false.
确保operator()为纯函数的第一步是声明其为const.后面还要继续考虑其他可能性.

1	bool operator()(const Obj&) const

I40.若一个类是函数子,则应是它可配接

STL里4个标准配接器(not1,not2,bind1st,bind2nd)是包装好的类型(argument_type,first_argument_type,second_argument_type,result_type).自定义的函数子必须满足其类型才能配接.
配接的2种方式.

ptr_fun

1	find_if(O.begin(),O.end(),not1(ptr_fun(isRight)));

让函数子继承自特定的函数模板.unary_function,binary_function.

class MeetsThreshold: public std::unary_function<Widget, Wideget, bool>{
    public operator()(const Widget& lhs,const Widget& rhs) const;
}

struct Compare: public std::unary_function<Widget, Wideget, bool>{
bool operator()(const Widget& lhs, const Widget& rhs) const;} //模板参数不为引用,实际参数为引用,不统一

struct Compare: public std::unary_function<const Widget*, bool>{
bool operator()(const Widget* lhs, const Widget* rhs) const;} //模板参数为参数,统一

I41.理解ptr_fun,mem_fun和mem_fun_ref的由来

三个函数对象配接器(function object adpater),分别对应函数子的调用方式为:

非成员函数:f(x),如果不确定是否需要加,那就加上基本不会影响性能.

1	for_each(v.begin(),v.end(),ptr_fun(test));

成员函数:x.f()

1	for_each(v.begin(),v.end(),mem_fun(&Widget::test));

成员函数指针p->f()

1	for_each(v.begin(),v.end(),mem_fun_ref(&Widget::test));

I42.确保less<T>与operator<具有相同的语义(the principle of least astonishment)

问题:如何对一个类同时实现多个不同的比较规则?

解法1

特化std::less<T>

template<>
struct std::less<Widget>: public std::binary_function<Widget, Widget, bool>{
    bool operator()(const Widget& lhs, const Widget& rhs) const
    {
        retunrn ...;
    }
}

不要这么做,修改less这种std函数违背the principle of least astonishment.(但我总感觉作者给我指出了一条可以特化std的方式,以防不时之需…)

2.自定义函数子

在程序中使用STL

I43.算法调用优先于手写循环

算法调用的好处:效率高,正确性高(例如迭代器的正确性保证),可维护性强.

quque<double>::iterator insertLocation = d.begin();
for(size_t i=0; i<num; ++i){
    insertLocation = d.insert(insertLocation,data[i]+41);	//保证插入的顺序与data原顺序一致
    ++insertLocation;		//不加此行,insertLocation在每次循环后失效    
}

//调用算法,绑定器方式如下
transform(data, data+num, inserter(d,d.begin()), bind2d(plus<double>(), 41));

如果绑定器对接器实现函数子功能太复杂,可以考虑使用自定义函数子.
如果循环里的工作很简单,并且并且使用绑定器对接器不好实现的情况下使用手写循环也可以接受.

I44.容器的成员函数优先于算法函数

原因1:效率更高,例如set.find()是对数时间复杂度,find()是线性时间复杂度.
原因2:结果不同,例如成员函数的比较是基于等价性,而算法函数是基于相等性原则.再例如,对于map,成员函数只比较key,算法函数可能比较key+value.因此成员函数可以保证容器成员及其操作的一致性.
原因3:list而言,成员函数的含义与某些算法函数不一致,例如remove函数,有些算法函数无法适用例如sort要求随机访问迭代器.

I45.正确区分count,find,binary_search,lower_bound,upper_bound和equal_range

选择如下图:

find比count在查找上更效率
lower_bound/upper_bound比equal_range更容易受制于相等性原则上.equal_range返回的两个迭代器之间的distance能做很多事.

1 2	vector<Widget>::iterator i = lower_bound(v.begin(), v.end()); if(i!=v.end() && *i==w){...} //注意此处的相等性判断

I46.考虑使用函数对象而不是函数作为STL算法的参数

原因1:效率高.函数对象的operator()会被编译器进行内联优化.函数即便声明为inline也不会进行内联优化,因为本质上它仍是函数指针,指针不会进行内联优化.

1	void sort(vector<int>::iterator first, vector<int>::iterator second, bool(*comp)(int, int));

原因2:容易正确通过编译,考虑到STL平台/编译器的组合.
原因3:有助于避免语言的微妙缺陷.例如潜在的同名同参的函数.

I47.避免write-only型代码

write-only是只管写与实现,不管阅读与维护的含义.

//一行代码实现删除v中所有小于x但最后一个小于x但大于y的保留
v.earse(
remove_if(find_if(v.rbeging(), v.rend(),
                  bind2nd(greater_equal<int>(),y)).base(),
         v.end(),
         bind2nd(less<int>(),x)),
v.end());

I48.总是#include正确的头文件

容器:<vector>,<map>(包括map,multi_map).
算法:<algorithm>,<numeric>.
特殊迭代器:<iterator>(istream_iterator,istreambuf_iterator).
标准的函数子:<functional>.

I49.学会分析与STL相关的编译器诊断信息.

通过文本替换逐步简化诊断信息得到问题症结.

I50.熟悉与STL相关的web站点

SGI STL:文档+非标准组件(hash_set,slist,rope,select1st,selcet2nd…).
STLport:对SGI移植性的提升,优秀的调试模式
Boost:STL相关的函数对象(例如支持指向引用的引用合法)

《effective STL》书摘与感悟记录

https://www.chuxin911.com/effective_STL_summary_20211024/

作者

发布于

2021-10-24

更新于

2022-11-23

许可协议

#C++Learning_Note Summary Programming Scott_Meyers

《effective STL》书摘与感悟记录

容器

I1.选择合适的容器

I2.不要试图编写独立于容器类型的代码

I3.确保容器中的对象拷贝正确并高效

I4.调用empty而不是size检查为空与否

I5.区间成员函数优于与之对应的单元素成员函数

I6.当心C++编译器最烦人的分析机制

I7. 如果在容器中用new创建了指针,不要忘记在容器对象析构的时候delete指针

I8. 切勿包含auto_ptr创建的容器对象

I9. 慎重选择删除元素的方法

I10.了解分配子(allocator)的约定和限制

I11.理解自定义分配子的合理用法

I12.切勿对STL容器的线程安全有不切实际的依赖

vector和string

I13.vector和string优先于动态分配的数组

I14.使用reserve避免不必要的重新分配

I15.注意string的多样性

I16.了解如何把vector/string传到C API

I17.使用swap去除多余容量

I18.避免使用vector<bool>

关联容器

I19.理解相等(equality)和等价(equivalence)的区别

I20.为包含指针的关联容器指定比较类型

I21.总是让比较函数在等值情况下返回false

I22.切勿直接修改set或multiset中的键

I23.考虑用排序的vector代替关联容器

I24.当效率至关重要时,在map::operator[]与map::insert之间谨慎选择

I25.熟悉非标准的散列函数

迭代器

I26.iterator优于constant_iterator,reverse_iterator,const_reverse_iterator

I27.使用distance和advance将容器的const_iterator转换为iterator

I28.正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

I29.对逐个字符的输入考虑使用istreambuf_iterator

算法

I30.确保目标区间足够大

I31.了解各种与排序有关的选择

I32.如果确定要删除元素,在remove后调用erase

I33.对包含指针的容器时使用remove类算法时要特别小心

I34.了解哪些算法需要排序区间作为参数

I35.通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较

I36.理解copy_if的正确实现

I37.使用accumulate或者for_each进行区间统计

函数子,函数子类,函数其其他

I38.遵循按值传递的原则来设计函数子类

I39.确保判别式是纯函数

I40.若一个类是函数子,则应是它可配接

I41.理解ptr_fun,mem_fun和mem_fun_ref的由来

I42.确保less<T>与operator<具有相同的语义(the principle of least astonishment)

在程序中使用STL

I43.算法调用优先于手写循环

I44.容器的成员函数优先于算法函数

I45.正确区分count,find,binary_search,lower_bound,upper_bound和equal_range

I46.考虑使用函数对象而不是函数作为STL算法的参数

I47.避免write-only型代码

I48.总是#include正确的头文件

I49.学会分析与STL相关的编译器诊断信息.

I50.熟悉与STL相关的web站点

作者

发布于

更新于

许可协议

目录

分类

最新文章

目录

标签

订阅更新