C++经验谈

C++ 的经验之谈

一、用异或来交换变量是错误的

翻转一个字符串，例如把“12345”变成“54321”。

// 版本一，用中间变量交换两个数
void reverse_by_swap(char* str, int n)
{
    char* begin = str;
    char* end = str + n - 1;

    while(begin < end)
    {
        char tmp = *begin;
        *begin = *end;
        *end = tmp;
        ++begin;
        --end;
    }
}

// 版本二，用异或运算交换两个数
void reverse_by_xor(char* str, int n)
{
    // WARNING: BAD code
    char* begin = str;
    char* end = str + n - 1;

    while(begin < end)
    {
        *begin ^= *end;
        *end ^= *begin;
        *begin ^= *end;
        ++begin;
        --end;
    }
}

C++ 对翻转字符有更简单的解法—调用 STL 里的 std::reverse() 函数。现在的编译器会把 std::reverse() 这种简单函数自动内联展开。

// 版本三，用 std::reverse 颠倒一个区间
void reverse_by_std(char* str, int n)
{
    std::reverse(str, str + n);
}

二、不要重载全局 ::operator new()

内存管理的基本要求

既不重复 delete，也不漏掉 delete。new/delete 要配对，不仅个数相等，还隐含了 new 和 delete 的调用本身要匹配 。

• 用系统默认的 malloc() 分配的内存要交给系统默认的 free() 去释放。
• 用系统默认的 new 表达式创建的对象要交给系统默认的 delete 表达式去析构并释放。
• 用系统默认的 new[] 表达式创建的对象要交给系统默认的 delete[] 表达式去析构并释放。
• 用系统默认的 operator new() 分配的内存要交给系统默认的 ::operator delete() 去释放。
• 用 placement new 创建的对象要用 placement delete 去析构（其实就是直接调用析构函数）。
• 从某个内存池 A 分配的内存要还给这个内存池。
• 如果定制 new/delete，要按《Effective C++ 中文版》第8章“定制 new 和 delete”来。

重载 ::operator new() 的理由

• 检测代码中的内存错误；
• 优化性能;
• 获得内存使用的统计数据。

::operator new() 的两种重载方式

1. 不改变其签名，无缝直接替换系统原有的版本

   #include <new>
   
   void* operator new(size_t size);
   void operator delete(void* p);

   用这种方式的重载，使用方不需要包含任何特殊的头文件，也就是不需要看见这两个函数声明。“性能优化”通常用这种方式。

2. 增加新的参数，调用时也提供这些额外的参数

   // 此函数返回的指针必须能被普通的 ::operator delete(void*) 释放
   void* operator new(size_t size, const char* file, int line);
   
   // 此函数只在构造函数抛出异常的情况下才会被调用
   void operator delete(void* p, const char* file, int line);
   
   // 使用方式
   Foo* p = new(__FILE, __LINE__) Foo; // 这样能跟踪是哪个文件哪一行代码分配的内存

   也可以用宏替换 new 来节省打字。使用方需要看到这两个函数声明，也就是要主动包含你提供的头文件。“检测内存错误”和“统计内存使用情况”通常会用这种方式重载。

现实的开发环境

编写稍具规模的 C++ 应用程序，会用到一些 library。可以分为如下几大类：

1. C 语言的标准库，也包括 Linux 编程环境提供的 glibc 系列函数。
2. 第三方的 C 语言库，例如 OpenSSL。
3. C++ 语言的标准库，主要是 STL。
4. 第三方的通用 C++ 库，例如 Boost.Regex，或者 XML 库。
5. 公司其他团队的人开发的内部基础 C++ 库，比如网络通信和日志等基础设施。
6. 本项目组的同事自己开发的针对本应用的基础库，比如某三维模型的仿射变换模块。

重载 ::operator new() 的困境

1、规则1：绝对不能在 library 里重载 ::operator new()
如果 library 要提供给别人使用，那么你无权重载全局 ::operator new(size_t)（注意这是前面提到的第一种重载方式），因为这非常具有侵略性，任何用到你的 library 的程序都被迫使用了你重载的 ::operator new()，而别人可能不愿意这么做。另外，如果有两个 library 都试图重载 ::operator new(size_t)，估计会发生 duplicated symbol link error。

2、第二种重载方式如何？
首先，void* operator new(size_t size, const char* file, int line); 这种方式得到的 void* 指针必须能同时被 void operator delete(void) 和 void operator delete(void p, const char* file, int line) 这两个函数释放。

其次，在 library 里重载 void* operator new(size_t size, const char* file, int line) 还涉及你的重载要不要暴露给 library 的使用者(其他 library 或主程序)。

1. 包含你的头文件的代码会不会用到你重载的 ::operator new()
2. 重载之后的 ::operator new() 分配的内存能不能在你的 library 之外被安全地释放。如果不行，那么是不是要暴露某个接口函数来让使用者安全地释放内存？或者返回 shared_ptr，利用其捕获析构动作的特性？

在主程序里重载 ::operator new() 的作用不大

C++ library 在代码组织上有两种形式：

1. 以头文件方式提供（如以 STL 和 Boost 为代表的模板库）；
2. 以头文件 + 而二进制库文件方式提供（大多数非模板库以此方式发布）。

对于纯以头文件方式实现的 library，可以在你的程序的每个 .cpp 文件的第一行包含重载 ::operator new() 的头文件，这样程序里用到的其他 C++ library 也会转而使用你的 ::operator new() 来分配内存。

对于以库文件方式实现的 library，这么做并不能让其受惠，因为 library 的源文件已经编译成了二进制代码，它不会调用你新重载的 ::operator new。

替换 malloc()

直接从 malloc 层面入手，通过 LD_PRELOAD 来加载一个 .so，其中有 malloc/free 的替代实现（drop-in replacement），这样同时能为 C 和 C++ 代码服务，而且避免 C++ 重载 ::operator new()。

对于检测内存错误，可以用 valgrind、dmalloc、efence 来达到相同的目的。

对于统计内存使用情况，替换 malloc 同样能够得到足够的信息，因为可以用 backtrace() 函数来获得调用栈，这比 new(FILE, __LINE) 的信息更丰富。

为单独的 class 重载 ::operator new() 有问题吗？
如果一个 class Node 需要重载 member ::operator new()，说明它用到了特殊的内存分配策略，常见情况是使用了内存池或对象池。具体地说，用 factory 来创建对象，比如 static Node* Node::createNode() 或者 static shared_ptr< Node > Node::createNode()。

有必要自行定制内存分配器吗？
如果写一个简单的只能分配固定大小的 allocator，确实很容易做到比系统的 malloc 更快，因为每次分配操作就是移动一下指针。

三、带符号整数的除法与余数

const char* convert(char buf[], int value)
{
    static char digits[19] = 
    {
        '9', '8', '7', '6', '5', '4', '3', '2', '1',
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 
    };
    static const char* zero = digits + 9;   // zero 指向 '0'

    // work for -2147483648 .. 2147483647
    int i = value;
    char* p = buf;
    do
    {
        // lsd - least significant digit
        int lsd = i % 10;   // lsd 可能小于 0
        i /= 10;            // 是向下取整还是向零取整？
        *p++ = zero[lsd];   // 下标可能为负
    }while(i != 0)

    if(value < 0)
    {
        *p++ = '-';
    }
    *p = '\0';
    std::reverse(buf, p);
    return p;   // p - buf 为整数长度
}

可以作为 itoa() 的参考实现。《C Traps and Pitfalls》讲到，C 语言中的整数除法（/）和取模（%）运算在操作数为负的时候，结果是 implementation-defined。也就是说，如果 m、d 都是整数，

int q = m / d;
int r = m % d;

C 语言只保证 m = q × d + r。如果 m、d 当中有负数，那么 q 和 r 的正负号是由实现决定的。比如（-13）/ 4 = （-3）或（-13）/ 4 = （-4）都是合法的。

四、在单元测试中 mock 系统调用

在某些情况下，单元测试是很有必要的，在测试 failure 场景的时候尤其重要。

• 在开发存储系统时，模拟 read()/write() 返回 EIO 错误（有可能是磁盘写满了，也有可能是磁盘出现了坏道读不出数据）
• 在开发网络库的时候，模拟 write() 返回 EPIPE 错误（对方意外断开连接）
• 在开发网络库的时候，模拟自连接（self-connection），网络库应该用 getsockname() 和 getpeername() 判断是否是自连接，然后断开之
• 在开发网络库的时候，模拟本地 ephemeral port 耗尽，connect() 返回 EAGAIN 临时错误
• 让 gethostbyname() 返回我们预设的值，防止单元测试给公司的 DNS Server 带来太大压力

4.1、系统函数的依赖注入

1、采用传统的面向对象的手法，借助运行期的迟绑定实现注入与替换。自己写一个 System interface，把程序里用到的 open、close、read、write、connect、bind、listen、accept、gethostname、getpeername、getsockname 等等函数统统用虚函数封装一层。在代码里不要直接调用 open()，而是调用 System::instance.open()。这样代码主动把控制权交给了 System interface。在写单元测试的时候，把这个 singleton instance 替换为 mock object，这样就能模拟各种 error code。

2、采用编译期或链接期的迟绑定。可以在写一个 system namespace 头文件，在其中声明 read() 和 write() 等普通函数，然后在 .cc 文件里转发给对应系统的系统函数 ::read() 和 ::write() 等。

// .h
namespace sockets
{
    int connect(int sockfd, const struct sockaddr_in& addr);
}

// .cc
int sockets::connect(int sockfd, const struct sockaddr_in& addr)
{
    return ::connect(sockfd, sockaddr_cast(&addr), sizeof addr);
}

有了这一层间接性，就可以在编写单元测试的时候链接我们的 stub 实现，以达到替换实现的目的

int sockets::connect(int sockfd, const struct sockaddr_in& addr)
{
    errno = EAGAIN;
    return -1;
}

一个 C++ 程序只能有一个 main() 入口，所以要先把程序做成 library，再用单元测试代码链接这个 library。假设有一个 mynetcat 程序，为了编写 C++ 单元测试，可以把它拆成两部分，即 library 和 main()，源文件分别是 mynetcat.cc 和 main.cc。
在编译普通程序的时候：

g++ main.cc mynetcat.cc SocketsOps.cc -o mynetcat

在编译单元测试时这么写：

g++ test.cc mynetcat.cc MockSocketsOps.cc -o test

namespace 的好处在于它不是封闭的，可以随时打开往里添加新的函数，而不用改动原来的头文件。这也是以 non-member non-friend 函数为接口的优点。

4.2、链接期垫片（link seam）

要仿冒 connect() 函数，可以在单元测试程序里实现一个自己的 connect() 函数，它遮盖了同名的系统函数。在链接的时候，linker 会优先采用我们自己定义的函数。（这对动态链接是城里的；如果是静态链接，会报 multiple definition 错误。好在绝大数情况下 libc 是动态链接的。）

typedef int (*connect_func_t)(int sockfd,
                              const struct sockaddr* addr,
                              socklen_t addrlen);

connect_func_t connect_func = dlsym(RTDL_NEXT, "connect");

bool mock_connect;
int mock_connect_errno;

// mock connect
extern "C" int connect(int sockfd,
                       const struct sockaddr* addr,
                       socklen_t addrlen)
{
    if(mock_connect)
    {
        errno = mock_connect_errno;
        return errno == 0 ? 0 : -1;
    }
    else
    {
        return connect_func(sockfd, addr, addrlen);
    }
}

程序真的要调用 connect()，为了防止出现无限递归的情况，用 dlsym(RTDL_NEXT, “connect”) 获得 connect() 系统函数的真实地址，然后通过函数指针 connect_func 来调用它。

Link seam 同样适用于第三方 C++ 库

class File : boost::noncopyable
{
    public:
        File(const char* filename);
        ~File();

        int readn(void* data, int len);
        int writen(const void* data, int len);
        size_t getSize() const;
    private:
};

这个 class 没有适用虚函数，无法通过 sub-classing 的方法来实现 mock object。如果需要为用到 File class 的程序编写单元测试，我们可以自己定义其成员函数的实现，这样可以注入任何我们想要的结果。

int File::readn(void* data, int len)
{
    return -1;
}

这种做法对动态库是可行的，但对于静态库则会报错。

五、慎用匿名 namespace

其只要目的是让该 namespace 中的成员（变量或函数）具有独一无二的全局名称，避免名字碰撞（name collisions）。

5.1、C 语言的 static 关键字的两种用法

1. 用于函数内部修饰变量，即函数内的静态变量。这种变量的生存期长于该函数，使得函数具有一定的状态。使用静态变量的函数一般是不可重入的，也不是线程安全的，比如 strtok()。
2. 用在文件级别（函数体之外），修饰变量或函数，表示该变量或函数只在本文件可见，其他文件看不到、也访问不到该变量或函数。专业的说法叫“具有 internal linkage”（简言之：不暴露给别的 translation unit）。

5.2、C++ 语言的 static 关键字的四种用法

3. 用于修饰 class 的数据成员，即所谓静态成员。这种数据成员的生存期大于 class 的对象（实体/instance）。静态数据成员是每个 class 有一份，普通数据成员是每个 instance 有一份吗，因此也分别叫做 class variable 和 instance variable。
4. 用于修饰 class 的成员函数，即所谓静态成员函数。这种成员函数只能访问 class viriable 和其他静态成员函数，不能访问 instance variable 或 instance method。

这几种用法可以组合，比如 C++ 的成员函数（无论 static 还是 instance）都可以有其局部的静态变量。对于 class template 和 function template，其中的 static 对象的真正个数跟 template instantiate（模板具现化）有关。

5.3、匿名 namespace 的不利之处

1. 匿名 namespace 中的函数是匿名的，那么在确实需要引用它的时候就比较麻烦。比如在调试的时候不便给其中的函数设断点，又比如 profiler 的输出结果也不容易判别到底是哪个文件中的 calculate() 函数需要优化。
2. 使用某些版本的 g++ 时，同一个文件每次编译出来的二进制文件会变化。比如说拿到一个会发生 core dump 的二进制可执行文件，无法确定它是由哪个 revision 的代码编译出来的。毕竟编译结果不可复现，具有一定的随机性。另外这也可能让某些 build tool 失灵，如果该工具用到了编译出来的二进制文件的 MD5 的话。

六、采用有利于版本管理的代码格式

6.1、对 diff 友好的代码格式

1. 多行注释也用 //，不用 /* … */
2. 局部变量与成员变量的定义
   一行代码只定义一个变量，同样的道理适用于 enum 成员的定义、数组的初始化列表等。
3. 函数声明中的参数
   如果函数的参数大于3个，那么在逗号后面换行，这样每个参数占一行，便于 diff。

   class TcpClient : boost::noncopyable
   {
       public:
           TcpClient(EventLoop* loop,
                     const InetAddress& serverAddr,
                     const string& name);
   }

4. 函数调用时的参数
   在函数调用的时候，如果参数大于3个，那么把实参分行写。

   Timestamp EpollPoller::poll(int timeoutMs, ChannelList* activeChannels)
   {
       int numEvents = ::epoll_wait(epollfd_,
                                    &*events_.begin(),
                                    static_cast<int>(events_.size()),
                                    timeoutMs);
       Timestamp now(Timestamp::now());
   }

5. class 初始化列表的写法
   class 初始化列表（initializer list）也遵循一行一个的原则。
6. 与 namespace 有关的缩进
   Google 的 C++ 编程规范明确指出，namespace 不增加缩进。方便 diff -p 把函数名显示在每个 diff chunk 的头上。diff 原本是为 C 语言设计的，C 语言没有 namespace 缩进一说，所以它默认会找到顶格写的函数作为一个 diff chunk 的名字。如果函数名前面有空格，它就不认得了。

   namespace muduo
   {
   
   // class 从第一列开始写，不缩进
   class Timestamp : public muduo::copyable
   {
       // ...
   };
   }

7. public 与 private
   C++ diff 无法看出把一个函数从 public 区移到 private 区。
8. 避免使用版本控制软件的 keyword substitution 功能
   这么做是为了避免 diff 噪声。

6.2、对 grep 友好的代码风格

1. 操作符重载
   operator overloading 应仅限于和 STL algorithm/container 配合时使用，比如 std::transform() 和 map< Key, Value >，其他情况都用具名函数为宜。
   又比如，Google Protocol Buffers 的回调是 Closure class，它的接口用的是 virtual function Run() 而不是 virtual operator()()。
2. static_cast 与 C-style cast
   为什么 C++ 要引入 static_cast 之类的转型操作符，原因之一就是像 (int*)pBuffer 这样的表达式基本上没办法用 grep 判断出它是个强制类型转换，写不出一个刚好只匹配类型转换的正则表达式。

七、再探 std::string

std::string 主要有三类实现方式

1. 无特殊处理（eager copy），采用类似 std::vector 的数据结构。

   // class invariants:
   // (1) [start, finish) is a valid range.
   // (2) Each iterator in [start, finish) points to a valid object of type value_type.
   // (3) *finish is a valid object of type value_type; in particular, it is value_type().
   // (4) [finish + 1, end_of_storage) is a valid range.
   // (5) Each iterator in [finish + 1, end_of_storage) points to uninitialized memory.
   
   // Note one important consequence: a string of length n must manage a block of memory
   // whose size is at least n + 1.
   
   class string
   {
       public:
           const_pointer data() const { return start; }
           iterator begin()           { return start; }
           iterator end()             { return finish; }
           size_type size() const     { return finish - start; }
           size_type capacity() const { return end_of_storage - start; }
   
       private:
           char* start;
           char* finish;
           char* end_of_storage;
   };

   对象的大小是3个指针，在 32-bit 中是12字节，在 64-bit 中是24字节。
   Eager copy string 的另一种实现方式是把后两个成员变量替换成整数，表示字符串的长度和容量。

   class string
   {
       public:
           const_pointer data() const { return start; }
           iterator begin()           { return start; }
           iterator end()             { return start + size_; }
           size_type size() const     { return size_; }
           size_type capacity() const { return capacity_; }
   
       private:
           char* start;
           size_t size_;
           size_t capacity_;
   };

2. Copy-on-Write（COW）。g++ 的 std::string 一直采用这种方式实现。
   string 对象里只放一个指针。

   class cow_string    // libstdc++-v3
   {
       struct Rep
       {
           size_t size;
           size_t capacity;
           size_t refcount;
           char*  data[1];     // variable length
       };
       char* start;
   };

3. 短字符串优化（SSO），利用 string 对象本身的空间来存储短字符串。Visual C++ 用的是这种实现方式。
   无论哪种实现方式都要保存三个数据库：1、字符串本身（char[]），2、字符串的长度（size），3、字符串的容量（capacity）。
   string 对象比前面两个都大，因为有本地缓冲区（local buffer）。

   class sso_string
   {
       char* start;
       size_t size;
       static const int kLocalSize = 15;
       union
       {
           char buffer[kLocalSize+1];
           size_t capacity;
       }data;
   }

八、用 STL algorithm 做算法题

C++ STL 的 algorithm 配合自定义的 functor（仿函数、函数对象）可以用来解决某些算法题。

8.1、用 next_permutation() 生成排列组合

生成 N 个不同元素的全排列

把元素从小到大放好（即字典序最小的排列），然后反复调用 next_permutation()。

int main()
{
    int elements[] = { 1, 2, 3, 4};
    const size_t  N = sizeof(elements)/sizeof(elements[0]);
    std::vector<int> vec(elements, elements + N);

    int count = 0;
    do
    {
        std::cout << ++count << ": ";
        std::copy(vec.begin(), vec.end(),
                  std::ostream_iterator<int>(std::cout, ", "));
        std::cout << std::endl;
    }while(next_permutation(vec.begin(), vec.end()));
}

生成从 N 个元素中取出 M 个的所有组合

int main()
{
    int values[] = { 1, 2, 3, 4, 5, 6, 7 };
    int elements[] = { 1, 1, 1, 0, 0, 0, 0 };
    const size_t N = sizeof(elements)/sizeof(elements[0]);
    assert(N == sizeof(values)/sizeof(values[0]));
    std::vector<int> selectors(elements, elements + N);

    int count = 0;
    do
    {
        std::cout << ++count << ": ";
        for(size_t i = 0; i < selectors.size(); ++i)
        {
            if(selectors[i])
            {
                std::cout << values[i] << "，";
            }
        }
        std::cout << std::endl;
    }while(prev_permutation(selectors.begin(), selectors.end()));
}

8.2、用 unique() 去除连续重复空白

std::unique() 的作用是去除相邻的重复元素。注意所有针对区间的 STL algorithm 都只能调换区间内元素的顺序，不能真正删除容器内的元素。

struct AreBothSpaces
{
    bool operator()(char x, char y) const
    {
        return x == ' ' && y == ' ';
    }
};

void removeContinuousSpaces(std::string& str)
{
    std::string::iterator last
        = std::unique(str.begin(), str.end(), AreBothSpaces());
    str.erase(last, str.end());
}

8.3、用 {make, push, pop}_heap() 实现多路归并

题目 用一台 4GiB 内存的机器对磁盘上的单个 100 GB 文件排序
标准思路是先分块排序，然后多路归并并输出文件。多路归并用 heap 排序实现，比方说要归并已经按从小到大的顺序排好序的32个文件，可以构造一个32元素的 min heap，每个元素是 std::pair< Recode, FILE* >。然后每次取出堆顶的元素，将其 Record 写入输出文件；如果 FILE* 还可读，就读入一条 Record，再向 heap 中添加 std::pair< Recode, FILE* >。这样当 heap 为空的时候，多路归并就完成了。这个过程中 heap 的大小通常会慢慢变小，因为有可能某个输入文件已经全部读完了。

typedef int Record;
typedef std::vector<Record> File;

struct Input
{
    Record value;
    const File* file;

    explicit Input(const File* f);
    bool next();

    bool operator<(const Input& rhs) const
    {
        // make_heap to build min-heap, for merging
        return value > rhs.value;
    }
};

File mergeN(const std::vector<File>& files)
{
    File output;
    std::vector<Input> inputs;

    for(size_t i = 0; i < files.size(); ++i)
    {
        Input input(&files[i]);
        if(input.next())
        {
            inputs.push_back(input);
        }
    }

    std::make_heap(inputs.beigin(), inputs.end());
    while(!inputs.empty())
    {
        std::pop_heap(inputs.begin(), inputs.end());
        output.push_back(inputs.back().value);

        if(inputs.back().next())
        {
            std::push_heap(inputs.begin(), inputs.end());
        }
        else
        {
            inputs.pop_back();
        }
    }

    return output;
}

8.4、用 partition() 实现重排数组，让奇数位于偶数前面

std::partition() 的作用是把符合条件的元素放到区间首部，不符合条件的元素放到区间后部。

bool isOdd(int x)
{
    return x % 2 != 0;      // x % 2 == 1 is WRONG
}

void moveOddsBeforeEvens()
{
    int oddeven[] = { 1, 2, 3, 4, 5, 6 };
    std::patition(oddeven, oddeven+6, &isOdd);
    std::copy(oddeven, oddeven+6, std::ostream_iterator<int>(sdt::cout, ', '));
    std::cout << std::endl;
}

如果要求保持原来的数字先后顺序不变，可以用 std::stable_partition()。

8.5、用 lower_bound() 查找 IP 地址所属的城市

struct IPrange
{
    uint32_t startIp;   // inclusive
    uint32_t endIp;     // inclusive
    int value;          // >= 0

    bool operator<(const IPrange& rhs) const
    {
        return startIp < rhs.startIp;
    }
};

// REQUIRE: ranges is sorted.
int findIpValue(const std::vector<IPrange>& ranges, uint32_t ip)
{
    int result = -1;

    if(!ranges.empty())
    {
        IPrange needle = { ip, 0, 0 };
        std::vector<IPrangea>::const_iterator it
                = std::lower_bound(ranges.begin(), ranges.end(), needle);
        if(it == ranges.end())
        {
            --it;
        }
        else if(it != ranges.begin() && it->startIp > ip)
        {
            --it;
        }

        if(it->startIp <= ip && it->endIp >= ip)
        {
            result = it->value;
        }
    }

    return result;
}

8.6、STL algorithm 算法分类

• 容易，手写一遍的难度跟 strlen() 和 strcpy() 差不多。这类算法基本上是遍历一遍输入区间，对每个元素做些判断或操作，一个 for 循环就可以解决问题。一半左右的 STL algorithm 属于此类，例如 for_each()、transform()、accmulate() 等等。
• 较难，要写出正确的实现要考虑清楚各种边界条件。例如 merge()、unique()、remove()、random_shuffle()、lower_bound()、partition() 等等。
• 难，例如 sort()、nth_element()、next_permutation()、inplace_merge() 等等。

参考文章:
Linux多线程服务端编程