顾名思义，单例模式就是只提供一个类的实例。
简单来说的需要思考到的要点有：
- 全局只存在一个实例，不能拷贝和赋值
- 有实例时直接返回该实例，没有实例时创建实例
- 创建实例考虑线程安全
双重锁校验
两次锁的出现其实都是为了确保线程安全，
只有确保实例为空时，我们才需要加锁创立新的实例，
加完第一次锁之后，可能其它线程已经创建实例，此时需要再次进行判断，判断为空后就可以创建实例。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Singleton {
private:
static volatile Singleton* instance;
static std::mutex mtx;
Singleton() {}
public:
Singleton(Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
static Singleton* getInstance() {
if (instance == nullptr) {
std::lock_guard<std::mutex> lock(mtx);
if (instance == nullptr) {
instance = new Singleton();
}
}
return const_cast<Singleton*>(instance);
}
};
volatile Singleton* Singleton::instance = nullptr;
std::mutex Singleton::mtx;
静态局部变量
由于static只会在同一个地方分配内存，并且即使在局部函数中创建它的作用域也是在全局，利用这种特性，同样可以实现单例。
并且巧妙的利用了c++11中的一个特性：magic static
变量初始化时进入声明，并发线程会阻塞等待初始化结束。
因此
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Singleton {
private:
Singleton() {};
public:
~Singleton() {};
Singleton(Singleton&) = delete;
Singleton& operator=(const Singleton&) = delete;
static Singleton& get_instance() {
static Singleton instance;
return instance;
}
};
int main() {
Singleton& instance_1 = Singleton::get_instance();
Singleton& instance_2 = Singleton::get_instance();
return 0;
}
注意使用时也需要采用&的方式。
快速排序code:
1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r){
if(l>=r) return;
int i=l-1, j=r+1; x = q[l+r >> 1];
while(i<j) {
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if(i<j) swap(q[i], q[j]);
}
quick(q, l, j);
quick(q, j+1, r);
}
面试题8：旋转数组的最小数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Min(int numbers[], int length){
assert(numbers == NULL || length <= 0);
int i = 0, j= length - 1;
int index = i;
while(numbers[i] >= numbers[j]){
if(j == i+1){
index = j;
break;
}
index = i + j >> 1;
// 数据大量重复，无法移动指针
if(numbers[i] == numbers[j] && numbers[j] == numbers[index]){
return minorder(numbers, i, j);
}
if(numbers[index] >= numbers[i]){
i = index;
}else if(numbers[index] <= numbers[j]){
j = index;
}
}
return numbers[index];
}
参考资料：
1.剑指offer
