0. Google C++编程规范
英文版：http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml
中文版：http://zh-google-styleguide.readthedocs.org/en/latest/google-cpp-styleguide/contents/
1. C++函数的林林总总
2. Effective C++学习笔记
(1) 习惯c++，const特性
(2) 构造、析构、赋值、copy and swap
(3) RAII资源管理
(4) 传值or传引用、禁止返回局部对象指针、实现swap
(5) 少转型、异常安全、inline、编译依赖(pimpl手法)
(6) 继承本质、接口继承、实现继承
3. Effective STL学习笔记
(1) 容器：分类、区间操作优于单元素循环操作、容器不是线程安全
(2) vector优于数组、string优于char*、vector的reverse函数、swap空容器技巧
(3) 关联容器：不要使用[]操作，c++11标准hash容器std::unordered_map
(4) 迭代器: 提供越界检查、连续型容器使用 distance在 迭代器切换 idx下标
(5) 算法：多用标准库算法、各种排序相关算法、各种二分查找相关算法
(6) 函数对象：推荐陈硕大大： std::function std::bind替代虚函数
(7) 多使用STL，容器函数优于算法库函数，list的sort函数
4. C++ std::string 代码实现
陈硕大大 std::string实现
gcc std::string 详解
class Mystring {
public:
Mystring() : data_(new char[]) {
*data = '\0';
}
Mystring(const char* str) : data_(new char[strlen(str) + ]) {
strcpy(data_, str);
}
Mystring(const Mystring& str) : data_(new char[str.size() + ]) {
strcpy(data_, str.c_str());
}
~Mystring() {
delete[] data_;
}
// 重载赋值，采用copy and swap手法，旧式写法
Mystring& operator=(const Mystring& str) {
Mystring tmp(str);
swap(tmp);
return *this;
}
// 重载赋值，采用copy and swap手法，新式写法
Mystring& operator=(Mystring& str) {
swap(str);
return *this;
}
int size() const {
return (int)strlen(data_);
}
const char* c_str() const {
return data_;
}
void swap(Mystring& str) {
std::swap(data_, str.data_);
}
private:
char* data_;
};
5. C++ 智能指针 代码实现
c++智能指针的实现
智能指针类与普通指针一样，但它借由自动化内存管理保证了安全性，避免了诸如悬挂指针、内存泄露和分配失败等问题。
智能指针有好几种实现方式，STL和Boost库里都有实现，比如使用句柄类和引用计数方式。
我们现在使用引用计数定义智能指针，智能指针类将一个计数器与类指向的对象相关联。使用计数跟踪该类有多少个对象共享同一指针。
使用计数为0时，删除对象。使用计数有时也称为引用计数（reference count）。
使用一个计数变量，并将其置一，每新增一个对象的引用，该变量会加一，移除一个引用则减一，
即当对象作为另一对象的副本而创建时，复制构造函数复制指针并增加与之相应的使用计数的值。
当对一个对象进行赋值时（=操作符），覆写=操作符，这样才能将一个旧的智能指针覆值给另一指针，旧的引用计数减一，新的智能指针的引用计数则加一。
#include <memory>
#include <stdlib.h> template<typename T>
class SmartPointer {
public:
SmartPointer<T>(T* ptr) {
ref = ptr;
ref_count = (unsigned*)malloc(sizeof(unsigned));
*ref_count = ;
} SmartPointer<T>(SmartPointer<T>& sptr) {
ref = sptr.ref;
ref_count = sptr.ref_count;
++(*ref_count);
} SmartPointer<T>& operator=(SmartPointer<T>& sptr) {
if (this == &sptr) {
return *this;
} --(*ref_count);
if (*ref_count == ) {
clear();
} ref = sptr.ref;
ref_count = sptr.ref_count;
++(*ref_count);
return *this;
} ~SmartPointer<T>() {
--(*ref_count);
if (*ref_count == ) {
clear();
}
} T* GetValue() {
return ref;
} private:
void clear() {
delete ref;
free(ref_count);
ref = NULL;
ref_count = NULL;
} private:
T* ref;
unsigned* ref_count;
}; int main() {
int* ip1 = new int();
*ip1 = ;
int* ip2 = new int();
*ip2 = ; SmartPointer<int> sp1(ip1);
SmartPointer<int> sp2(ip2);
SmartPointer<int> spa = sp1;
sp2 = spa;
return ;
}
6. POD、迭代器萃取、模板偏特化
POD维基百科
POD(Plain Old Data)：标量类型 或 传统的C struct 类型，POD类型必然 拥有 默认的ctor、dtor、copy、assign
POD类类型就是指 class、struct、union，且不具有用户定义的构造函数、析构函数、拷贝算子、赋值算子；不具有继承关系，因此没有基类；不具有虚函数，所以就没有虚表；非静态数据成员没有私有或保护属性的、没有引用类型的、没有非POD类类型的（即嵌套类都必须是POD）、没有指针到成员类型的（因为这个类型内含了this指针）。
我们可以对 POD 型别采取最有效率的复制手法，而对 non-POD 型别采取最保险安全的作法
首先 利用迭代器萃取手法 萃取出迭代器 的 value type，然后判断该型别是否为 POD 型别
typedef typename __type_traits<T>::is_POD_type is_POD;
迭代器所指对象的型别，称为该迭代器的 value type
“模板参数推导机制” 只能针对于 函数参数类型，不能推导 函数的返回值类型
不是所有的迭代器都是 class type，原声指针就不是!!!
STL(泛型思维)绝对必须接受原生指针作为一种迭代器，这个时候就需要针对特殊情况(原生指针)做特化处理，即模板偏特化
模板偏特化：在泛化设计中提供一个特化版本(将泛化版本中的某些template参数赋予特殊的指定)
迭代器traits手法本质上就是 模板偏特化，实质代码如下：
template <class T>
struct iterator_traits {
typedef typename T::value_type value_type;
}
现在不管是class type 还是 原生指针int* , 我们都可以通过traits萃取出 迭代器的 value_type
7. C++ 单例模式 代码实现
c++ singleton神文
我的singleton博文
8. C++ 实现不被继承的类
我的博文
注：可以直接使用C++11的final关键字
9. c++ 虚函数 多态
多态两必要条件：(1) virtual函数 (2) 基类指针(引用)指向派生类对象
多态知识点：
(1) 任何含有 virtual函数的类及其派生类 均在类实例对象的首地址 安插一个指向虚函数表的指针(虚表指针，vptr)
为什么在 类对象的首地址(即this指针处) 存放 虚表指针呢？
Base* pBase = new Derived; // Base对象首地址、Derived对象首地址、this指针、虚表指针 均相同，非常方便的定位 虚表指针
(2) Derived类 会继承 Base类 的虚表，当Derived类 重定义了 Base类的某个函数，这时 Derived对应的虚函数表
Base::foo() ==> Derived::foo() // Derived::foo() 覆盖从基类 继承而来的 虚函数 Base::foo()
c++ this指针、虚函数
// c++中 所有non-static成员变量 和 virtual成员函数 都必须通过 this指针访问
class test {
public:
test(int value) : val(value) { } void foo1() { // 正确：non-virtual函数地址编译期确定，传入this指针，this指针为空，但是这个函数没有 访问 this空指针
fprintf(stdout, "hello world\n");
} void foo2() { // 错误：non-virtual函数地址编译期确定，传入this指针，this指针为空，但是这个函数 访问了 this空指针(因为 this->val)
fprintf(stdout, "%d\n", val);
} virtual void foo3() { // 错误：所有 virtual函数都需要通过 虚函数表确定，虚函数表需要 this指针来确定，因此 访问了 this空指针
fprintf(stdout, "hello world\n");
} static void foo4() { // 正确：所有static函数都没有this指针，所以不能访问 non-static成员变量
fprintf(stdout, "hello world\n");
}
private:
int val;
}; test* pTest = NULL; // this指针为空
pTest->foo1();
pTest->foo2();
pTest->foo3();
pTest->foo4();
c/c++类型转换
class Base {};
class Derived {};
Base* pBase = new Derived;
Base* pBase = new Derived[];
/*
1. 信息 = 比特位 + 解释方式，类型转换只是改变了 解释方式，数据未变
2. 数组和结构体(struct、class)访问成员变量和成员函数 都是 首地址 + offset偏移
type[i] ==> type(首地址) + i * sizeof(type) 3. new Derived返回指向Derived类型的指针
4. pBase = pDerived 指针的类型转换
5. 一般情况下，sizeof(Base) 不等于 sizeof(Derived) 6. 为什么第一句正确呢？
因为 这一句 只分配了一个对象，并且 vptr位于对象首地址，因此 Base的首地址 == Derived的首地址 == this指针，故正确找到 vptr 7. 为什么第二句一般情况下错误呢？
通常情况下，sizeof(Base) 不等于 sizeof(Derived), 因此 pBase[i] 不等于 pDerived[i]，由于类型转换改变了解释方式，导致找不到Derived的正确this指针位置，
因此vptr、析构函数就完全不正确了 注：当 sizeof(Base) == sizeof(Derived) 时，可以正确运行，但这是一个未定义行为，所以禁止这样的写法
*/
10. STL空间配置器
#ifndef _JJALLOC_
#define _JJALLOC_ #include <new> // for placement new
#include <cstddef> // for ptrdiff_t, size_t
#include <cstdlib> // for exit()
#include <climits> // for UINT_MAX
#include <iostream> // for cerr namespace JJ
{
template<class T>
inline T* _allocate(ptrdiff_t size, T*) {
std::set_new_handler();
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
if (tmp == ) {
std::cerr << "out of memory" << std::endl;
exit();
}
return tmp;
} template<class T>
inline void _deallocate(T* buffer) {
::operator delete(buffer);
} template<class T1, class T2>
inline void _construct(T1* p, const T2& value) {
new(p) T1(value);
}
template<class T>
inline void _destroy(T* ptr) {
ptr->~T();
} // std::allocator的标准接口
template<class T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type; template<class U>
struct rebind {
typedef allocator<U> other;
}; pointer allocate(size_type n, const void* hint = ) {
return _allocate((difference_type)n, (pointer));
} void deallocate(pointer p, size_type n) {
_deallocate(p);
} void construct(pointer p, const T& value) {
_construct(p, value);
} void destroy(pointer p) {
_destroy(p);
} pointer address(reference x) {
return (pointer)&x;
} const_pointer const_address(const_reference x) {
return (const_pointer)&x;
} size_type max_size() const {
return size_type(UINT_MAX/sizeof(T));
}
};
} #endif // _JJALLOC_
使用配置器：
std::vector<int, JJ::allocator<int>> vec
一般而言，我们习惯的c++内存配置操作和释放操作：
class Foo {...};
Foo* pf = new Foo; // 配置内存，然后构造对象
delete pf; // 析构对象，然后释放内存
new关键字包含两阶段操作：
(1) 调用 ::operator new 配置内存
(2) 调用 Foo::Foo()构造对象内容
delete关键字包含两阶段操作：
(1) 调用 Foo::~Foo() 将对象析构
(2) 调用 ::operator delete 释放内存
10.1 vector数据结构
template<class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator;
protected:
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
};
std::vector<int> vec;
sizeof(vec) = ; // 32位
11. 陈硕大大的C++博文学习 每篇都是经典:D
https://cloud.github.com/downloads/chenshuo/documents/CppPractice.pdf
11.1 C++ RAII封装Mutex
Linux C++ 多线程编程
MutexLock 封装临界区（Critical secion），这是一个简单的资源类，用 RAII 手法 [CCS:13]封装互斥器的创建与销毁。
临界区在 Windows 上是 CRITICAL_SECTION，是可重入的；在 Linux 下是 pthread_mutex_t，默认是不可重入的。MutexLock 一般是别的 class 的数据成员。
MutexLockGuard 封装临界区的进入和退出，即加锁和解锁。MutexLockGuard 一般是个栈上对象，它的作用域刚好等于临界区域。
#include <pthread.h> #define DISALLOW_COPY_AND_ASSIGN(TypeName) \
TypeName(const TypeName&) \
TypeName& operator=(const TypeName&) class MutexLock {
public:
MutexLock() {
pthread_mutex_init(&mutex_, NULL);
} ~MutexLock() {
pthread_mutex_destroy(&mutex_);
} void lock() {
pthread_mutex_lock(&mutex_);
} void unlock() {
pthread_mutex_unlock(&mutex_);
} pthread_mutex_t* getPthreadMutex() {
return &mutex_;
} private:
pthread_mutex_t mutex_;
DISALLOW_COPY_AND_ASSIGN(MutexLock);
}; class MutexLockGuard {
public:
explicit MutexLockGuard(MutexLock& mutex) : mutex_(mutex) {
mutex_.lock();
} ~MutexLockGuard() {
mutex_.unlock();
}
private:
MutexLock& mutex_;
DISALLOW_COPY_AND_ASSIGN(MutexLockGuard);
}; #define MutexLockGuard(x) static_assert(false, "missing mutex guard var name")
11.2 std::map学习
std::map学习
rb_tree 的迭代器的每次递增或递减不能保证是常数时间，最坏情况下可能是对数时间（即与树的深度成正比）
rb_tree_node* rb_tree_increment(rb_tree_node* node) {
if (node == NULL) {
return NULL;
}
if (node->right != NULL) {
node = node->right;
while (node->left != NULL) { // 右子树最左下节点
node = node->left;
}
} else {
rb_tree_node* parent = node->parent;
while (node == parent->right) { // 一直上溯
node = parent;
parent = node->parent;
}
if (node->right != parent) {
node = parent;
}
}
return node;
}
那么用 begin()/end() 迭代遍历一棵树还是不是 O(N)？
换言之，迭代器的递增或递减是否是分摊后的（amortized）常数时间？
利用数学归纳法可以获知：
对于深度为 n 的满二叉树，有 2^n - 1 个元素，从 begin() 到 end() 需要走 f(n) 步。那么 f(n) = 2*f(n-1) + n。
然后，用递推关系求出 f(n) = sum(i * 2 ^ (n-i)) = 2^(n+1) - n - 2（这个等式可以用归纳法证明）。
即对于深度为 n 的满二叉树，从头到尾遍历的步数小于 2^(n+1) - 2，而元素个数是 2^n - 1，二者一除，得到平均每个元素需要 2 步。
因此可以说 rb_tree 的迭代器的递增递减是分摊后的常数时间。
似乎还有更简单的证明方法，在从头到尾遍历的过程中，每条边（edge）最多来回各走一遍，一棵树有 N 个节点，那么有 N-1 条边，最多走 2*(N-1)+1 步，也就是说平均每个节点需要 2 步
