c++ notes

vector扩容缩容问题

两倍缩容，申请新空间，copy元素，释放老空间。

shrink_to_fit() 释放多出来的空间

扩容申请新空间后，所有原迭代器都会失效

    cout << test.capacity() << endl; // 0
    test.push_back(1);
    cout << test.capacity() << endl; // 1
    test.push_back(1);
    cout << test.capacity() << endl; // 2
    test.push_back(1);
    cout << test.capacity() << endl; // 4
    test.resize(8);
    cout << test.capacity() << endl; // 8
    test.resize(1025);
    cout << test.capacity() << endl; // 1025
    test.resize(1026);
    cout << test.capacity() << endl; // 2050
    test.resize(1);
    cout << test.capacity() << endl; //2050
    test.shrink_to_fit();
    cout << test.capacity() << endl; //1

template 的实现放在头文件中

https://blog.csdn.net/imred/article/details/80261632

skiplist

https://my.oschina.net/ljc94/blog/807388

柔性数组

typedef struct pen
{
    int len;
    char data[];//柔性数组
}pen;

// sizeof(pen) == 4

C99使用不完整类型实现柔性数组成员，在C99 中，结构中的最后一个元素允许是未知大小的数组，这就叫做柔性数组(flexible array)成员(也叫伸缩性数组成员)，但结构中的柔性数组成员前面必须至少一个其他成员。柔性数组成员允许结构中包含一个大小可变的数组。柔性数组成员只作为一个符号地址存在，而且必须是结构体的最后一个成员，sizeof 返回的这种结构大小不包括柔性数组的内存

unique_lock和lock_guard的区别

unique_lock和lock_guard最大的不同是unique_lock不需要始终拥有关联的mutex，而lock_guard始终拥有mutex。这意味着unique_lock需要利用owns_lock()判断是否拥有mutex。另外，如果要结合使用条件变量，应该使用unique_lock。

varint

用每个字节得第1位作为最高有效位。0表示当前字节为最后一个字节。 leveldb和protobu等都用到了

Encode : | 0xF0,移位

Decode : & 0x7F,移位

char* EncodeVarint64(char* dst, uint64_t v) {
  static const int B = 128;
  uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
  while (v >= B) {
    *(ptr++) = v | B;
    v >>= 7;
  }
  *(ptr++) = static_cast<uint8_t>(v);
  return reinterpret_cast<char*>(ptr);
}

void PutVarint64(std::string* dst, uint64_t v) {
  char buf[10];
  char* ptr = EncodeVarint64(buf, v);
  dst->append(buf, ptr - buf);
}

const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) {
  uint64_t result = 0;
  for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) {
    uint64_t byte = *(reinterpret_cast<const uint8_t*>(p));
    p++;
    if (byte & 128) {
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return nullptr;
}


bool GetVarint64(Slice* input, uint64_t* value) {
  const char* p = input->data();
  const char* limit = p + input->size();
  const char* q = GetVarint64Ptr(p, limit, value);
  if (q == nullptr) {
    return false;
  } else {
    *input = Slice(q, limit - q);
    return true;
  }
}

读写锁如何避免写锁饥饿

std::mutex mutex_;
std::shared_ptr<data> G_data(new data());

void read(){
	std::shared_ptr<data> Temp;
	{
		std::lock_guard<std::mutex> guard(mutex_);
		Temp = G_data;
	}
	Temp->read_something();
}

void write(){
    std::lock_guard<std::mutex> guard(mutex_);
    if(!G_data.unique()){
        G_data.reset(new data(*G_data));
    }
    G_data->write_something();
}

读线程访问时，写线程可以去更新保护数据的副本，但写线程需要等待所有读线程完成读取后，才可以删除老对象

Wall Clock and Monotonic Clock

Wall clock(time)就是我们一般意义上的时间，就像墙上钟所指示的时间。

Monotonic clock(time)字面意思是单调时间，实际上它指的是从某个点开始后（比如系统启动以后）流逝的时间，jiffies一定是单调递增的！

序列化和反序列化

把对象转化为可传输的字节序列过程称为序列化

把字节序列还原为对象的过程称为反序列化

address sanitizer

https://www.jianshu.com/p/3a2df9b7c353

https://github.com/google/sanitizers/wiki/AddressSanitizer

gcc编译时加上 -fsanitize=address 选项

自顶向下VS自底向上

• 自顶向下：从抽象到具体
• 自底向上：从具体到抽象

个人理解：以造房子为例。自顶向下：现设想好房子大概长什么样，画好轮廓，再搭好柱子，最后再搭地基。自底向上：还没想好盖成啥样，但搭好地基准没错，一边搭一边想。

自顶向下设计，自底向上实现

lower_bound和upper_bound

孩子总是记不住这两个的区别

lower_bound:下界，大于等于 [
upper_bound:上界，大于 (

if you have multiple elements in the range [first, last) whose value equals the value val you are searching for, then the range [l, u) where

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)
is precisely the range of elements equal to val within the range [first, last). So l and u are the "lower bound" and "upper bound" for the equal range. It makes sense if you're accustomed to thinking in terms of half-open intervals.

程序局部性原理

为什么快排比堆排和归并快？为什么插入比选择和冒泡快？

程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域，具体来说，局部性通常有两种形式：时间局部性和空间局部性。

时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。

空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

右值引用 折叠引用

左值和右值

右值引用。c++11标准提供右值引用。

A a1 = GetA();   // a1是左值
A&& a2 = GetA(); // a2是右值引用

a1是左值，在构造时使用了GetA() 产生的临时对象，之后GetA()产生的临时对象会销毁。

a2是右值引用，其指向的就是GetA()所产生的对象，这个对象的声明周期是和a2的声明周期是一致的。即少了临时对象，从而省去了临时对象的构造和析构。

纯右值引用折叠后才是右值引用，只要有一个左值引用，就是左值引用。

A& & 变成 A&
A& && 变成 A&
A&& & 变成 A&
A&& && 变成 A&&

move

移动构造函数。

类不会生成移动构造函数，在传入右值引用时，如果未定义则匹配左值引用，即复制构造函数

std::move 将一个左值强制转化为右值引用，继而可以通过右值引用使用该值，以用于移动语义。

移动构造函数和移动赋值函数定义方法如下

Thread(Thread &&t);
Thread &operator=(Thread &&t);

forward 完美转发

不管是T&&、左值引用、右值引用，std::forward都会按照原来的类型完美转发

remove_reference

线程池

ThreadPool.cc中，start函数确定了初始启动线程数量（固定，不会自动扩容缩容）

双端队列queue_用于存储task，notEmpty_条件变量用来通知线程池执行task，notFull_通知线程池可以继续添加任务。

std::bind

在bind中，如果要传递一个引用需要使用std::ref，常量引用为std::cref

using

构造函数的 using 声明
在 C++11 中，派生类能够重用其直接基类定义的构造函数。

class Derived : Base {
public:
    using Base::Base;
    /* ... */
};

如上 using 声明，对于基类的每个构造函数，编译器都生成一个与之对应（形参列表完全相同）的派生类构造函数。生成如下类型构造函数：

Derived(parms) : Base(args) { }

decltype

decltype 关键字用于检查实体的声明类型或表达式的类型及值分类。语法：

decltype ( expression )

decltype 使用

// 尾置返回允许我们在参数列表之后声明返回类型
template <typename It>
auto fcn(It beg, It end) -> decltype(*beg)
{
    // 处理序列
    return *beg;    // 返回序列中一个元素的引用
}
// 为了使用模板参数成员，必须用 typename
template <typename It>
auto fcn2(It beg, It end) -> typename remove_reference<decltype(*beg)>::type
{
    // 处理序列
    return *beg;    // 返回序列中一个元素的拷贝
}

initializer_list 列表初始化

用花括号初始化器列表初始化一个对象，其中对应构造函数接受一个 std::initializer_list 参数.

initializer_list 使用

#include <iostream>
#include <vector>
#include <initializer_list>
 
template <class T>
struct S {
    std::vector<T> v;
    S(std::initializer_list<T> l) : v(l) {
         std::cout << "constructed with a " << l.size() << "-element list\n";
    }
    void append(std::initializer_list<T> l) {
        v.insert(v.end(), l.begin(), l.end());
    }
    std::pair<const T*, std::size_t> c_arr() const {
        return {&v[0], v.size()};  // 在 return 语句中复制列表初始化
                                   // 这不使用 std::initializer_list
    }
};
 
template <typename T>
void templated_fn(T) {}
 
int main()
{
    S<int> s = {1, 2, 3, 4, 5}; // 复制初始化
    s.append({6, 7, 8});      // 函数调用中的列表初始化
 
    std::cout << "The vector size is now " << s.c_arr().second << " ints:\n";
 
    for (auto n : s.v)
        std::cout << n << ' ';
    std::cout << '\n';
 
    std::cout << "Range-for over brace-init-list: \n";
 
    for (int x : {-1, -2, -3}) // auto 的规则令此带范围 for 工作
        std::cout << x << ' ';
    std::cout << '\n';
 
    auto al = {10, 11, 12};   // auto 的特殊规则
 
    std::cout << "The list bound to auto has size() = " << al.size() << '\n';
 
//    templated_fn({1, 2, 3}); // 编译错误！“ {1, 2, 3} ”不是表达式，
                             // 它无类型，故 T 无法推导
    templated_fn<std::initializer_list<int>>({1, 2, 3}); // OK
    templated_fn<std::vector<int>>({1, 2, 3});           // 也 OK
}

如何定义一个只能在堆上（栈上）生成对象的类？

只能在堆上

方法：将析构函数设置为私有

原因：C++ 是静态绑定语言，编译器管理栈上对象的生命周期，编译器在为类对象分配栈空间时，会先检查类的析构函数的访问性。若析构函数不可访问，则不能在栈上创建对象。

只能在栈上

方法：将 new 和 delete 重载为私有

原因：在堆上生成对象，使用 new 关键词操作，其过程分为两阶段：第一阶段，使用 new 在堆上寻找可用内存，分配给对象；第二阶段，调用构造函数生成对象。将 new 操作设置为私有，那么第一阶段就无法完成，就不能够在堆上生成对象。

智能指针

#include <memory>

shared_ptr

多个智能指针可以共享同一个对象，对象的最末一个拥有着有责任销毁对象，并清理与该对象相关的所有资源。

支持定制型删除器（custom deleter），可防范 Cross-DLL 问题（对象在动态链接库（DLL）中被 new 创建，却在另一个 DLL 内被 delete 销毁）、自动解除互斥锁

weak_ptr

weak_ptr 允许你共享但不拥有某对象，一旦最末一个拥有该对象的智能指针失去了所有权，任何 weak_ptr 都会自动成空（empty）。因此，在 default 和 copy 构造函数之外，weak_ptr 只提供 “接受一个 shared_ptr” 的构造函数。

可打破环状引用（cycles of references，两个其实已经没有被使用的对象彼此互指，使之看似还在 “被使用” 的状态）的问题

unique_ptr

unique_ptr 是 C++11 才开始提供的类型，是一种在异常时可以帮助避免资源泄漏的智能指针。采用独占式拥有，意味着可以确保一个对象和其相应的资源同一时间只被一个 pointer 拥有。一旦拥有着被销毁或编程 empty，或开始拥有另一个对象，先前拥有的那个对象就会被销毁，其任何相应资源亦会被释放。

unique_ptr 用于取代 auto_ptr

强制类型转换运算符

static_cast
dynamic_cast
const_cast
reinterpret_cast

运行时类型信息 (RTTI)

dynamic_cast

用于多态类型的转换

typeid

typeid 运算符允许在运行时确定对象的类型

type_id 返回一个 type_info 对象的引用

如果想通过基类的指针获得派生类的数据类型，基类必须带有虚函数
只能获取对象的实际类型

type_info

type_info 类描述编译器在程序中生成的类型信息。 此类的对象可以有效存储指向类型的名称的指针。 type_info 类还可存储适合比较两个类型是否相等或比较其排列顺序的编码值。 类型的编码规则和排列顺序是未指定的，并且可能因程序而异。

头文件：typeinfo

typeid、type_info 使用

#include <iostream>
using namespace std;

class Flyable                       // 能飞的
{
public:
    virtual void takeoff() = 0;     // 起飞
    virtual void land() = 0;        // 降落
};
class Bird : public Flyable         // 鸟
{
public:
    void foraging() {...}           // 觅食
    virtual void takeoff() {...}
    virtual void land() {...}
    virtual ~Bird(){}
};
class Plane : public Flyable        // 飞机
{
public:
    void carry() {...}              // 运输
    virtual void takeoff() {...}
    virtual void land() {...}
};

class type_info
{
public:
    const char* name() const;
    bool operator == (const type_info & rhs) const;
    bool operator != (const type_info & rhs) const;
    int before(const type_info & rhs) const;
    virtual ~type_info();
private:
    ...
};

void doSomething(Flyable *obj)                 // 做些事情
{
    obj->takeoff();
    
    // 输出传入对象类型（"class Bird" or "class Plane"）
    cout << typeid(*obj).name() << endl;        

    if(typeid(*obj) == typeid(Bird))            // 判断对象类型
    {
        Bird *bird = dynamic_cast<Bird *>(obj); // 对象转化
        bird->foraging();
    }

    obj->land();
}

int main(){
	Bird *b = new Bird();
	doSomething(b);
	delete b;
	b = nullptr;
	return 0;
}

lambda表达式

捕获

any

boost::any （c++17中被引入标准库）

相比于void*增加了对类型的判断，更安全

any可以存储任意的类型，并能通过any_cast将any类型转化成原本的类型

实现：存储一个placeholder指针（智能指针？），利用template、多态、typeid等来存储不同类型的变量。any_cast是any的友元函数，可以进行指针转换，失败返回nullptr。也可以进行值转换，失败抛出bad_any_cast异常

std::async

shared_ptr 和 weak_ptr的问题

shared_ptr的循环引用可能导致对象无法销毁，导致内存问题。weak_ptr不会增加引用计数，可以解决这个问题。

下面的代码，A和B的对象都不会释放。不会看到析构函数的输出

class B;
class A
{
public:
    ~A() { cout << "~A" << endl; }
    shared_ptr<B> mp;
};

class B
{
public:
    ~B() { cout << "~B" << endl; }
    shared_ptr<A> mp;
};

int main()
{
    auto pb = std::make_shared<B>();
    auto pa = std::make_shared<A>();
    pa->mp = pb;
    pb->mp = pa;
    return 0;
}

用valgrind可以检测出内存泄漏

ubuntu@VM-0-10-ubuntu:~/github/notebook $ valgrind ./demo
==24914== Memcheck, a memory error detector
==24914== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==24914== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==24914== Command: ./demo
==24914== 
==24914== HEAP SUMMARY:
==24914==     in use at exit: 64 bytes in 2 blocks
==24914==   total heap usage: 3 allocs, 1 frees, 72,768 bytes allocated
==24914== 
==24914== LEAK SUMMARY:
==24914==    definitely lost: 32 bytes in 1 blocks
==24914==    indirectly lost: 32 bytes in 1 blocks
==24914==      possibly lost: 0 bytes in 0 blocks
==24914==    still reachable: 0 bytes in 0 blocks
==24914==         suppressed: 0 bytes in 0 blocks
==24914== Rerun with --leak-check=full to see details of leaked memory
==24914== 
==24914== For counts of detected and suppressed errors, rerun with: -v
==24914== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

改用weak_ptr之后不存在这个问题

placement new

new delete 分为两步：申请空间&调用构造/ 调用析构&释放空间

operator new :只申请空间
operaotr delete: 只释放空间

placement new : operator new 的一个重载版本，new(ptr) T在给定的地址空间new对象，进行构造。对象析构的时候显示调用析构函数

可变参模板

https://zhuanlan.zhihu.com/p/149405532

namespace detail
{
template <typename T, typename... Args>
inline void __construct(T* p, const Args&... args)
{
    std::cout << sizeof...(args) << std::endl;
}
} // namespace detail

template <typename T, typename... Args>
inline void construct(T* p, const Args&... args)
{
    detail::__construct(p, args...);
}

gflags调整姿势

才发现之前gflags一直用的不对，有资源泄漏问题

int main(int argc, char** argv)
{
    testing::InitGoogleTest(&argc, argv);
    google::ParseCommandLineFlags(&argc, &argv, true);
    google::ShutDownCommandLineFlags();
    return RUN_ALL_TESTS();
}

调用ParseCommandLineFlags后需调用ShutDownCommandLineFlags释放内存。

template sfinae初探

判断一个类是否有to_string成员函数，有的话调用

template <typename T>
struct has_to_string
{
    template <typename C>
    static char test(decltype(&C::to_string));
    template <typename C>
    static int32_t test(...);
    const static bool value = sizeof(test<T>(0)) == sizeof(char);
};


template <typename T>
typename std::enable_if<has_to_string<T>::value, std::string>::type
GetString(const T& value)
{
    return value.to_string();
}

template <typename T>
typename std::enable_if<!has_to_string<T>::value, std::string>::type
GetString(const T& value)
{
    return std::to_string(value);
}

// 另一种写法
template <typename T>
std::string
GetString(const T& value, typename std::enable_if<has_to_string<T>::value, void*>::type = nullptr)
{
    return value.to_string();
}

template <typename T>
std::string
GetString(const T& value, typename std::enable_if<!has_to_string<T>::value, void*>::type = nullptr)
{
    return std::to_string(value);
}

std::forward

函数的参数有多个，每个参数的引用类型都可能不同，如何处理呢？必然不能重载所有可能性，所以需要用到完美转发，std::forward来传递

https://blog.csdn.net/Stranger_CJHan/article/details/69830916

元数据

元数据是用来描述数据的数据（Data that describes other data）

compare

c++ - 参数相等时std::sort compare函数必须返回false