2019年4月

STL中的mapset默认时不支持存结构体的,如果要添加结构体的支持,必须手动重载<运算符。

原因:map和set底层都是通过红黑树实现的,红黑树搜索树的一种,插入数据时要比较大小,所以结构体必须重载小于号

示例:

#include <iostream>
#include <string>
#include <set>

using namespace std;

typedef struct stu_st {
    string name;
    int age;
}stu_t;

int main() {
    set<stu_t> stu_infos;

    stu_t a, b;
    a.name = "xiaoming";
    a.age = 20;

    b.name = "xiaohua";
    b.age = 21;

    stu_infos.insert(a);
    stu_infos.insert(b);

    cout << stu_infos.size() << endl;

    return 0;
}

以上代码在vs下编译报错:

问题很明确,没有重载<符号,添加上以下代码即可:

bool operator<(const stu_t& a, const stu_t& b) {
    return a.name < b.name;
}

一、申请方式

  • 栈是系统自动申请,自动释放。
  • 堆需要手动申请,手动释放。

二、增长方向

  • 栈是从高地址向地地址增长
  • 堆从地地址到高地址增长

三、存储位置

  • 栈的内存空间在用户空间的最顶端,3G以下
  • 堆位于全局静态区,在栈的下面

四、大小限制

  • 栈可分配的内存大小较小
  • 堆中可分配的内存较大

五、申请效率

  • 栈内存申请较快,不会产生碎片
  • 堆内存申请较慢,会产生碎片

  • 面向对象的原则是什么?
封装、继承和多态
  • C++的空类默认产生哪些类成员函数?
默认构造函数、析构函数、复制构造函数和赋值函数
  • 为什么拷贝构造函数只能传递引用
以传值方式调用函数时,会拷贝临时变量,此时又会调用拷贝构造函数来构造临时变量,从而出现无限循环。
  • 哪一种成员变量可以在所有该类的实例之间共享?
静态成员变量
  • C++中class和struct的区别
  • 如何在类中使用常量成员变量?
使用const修饰的成员变量,必须在初始化列表中初始化。
  • 把析构函数定义成virtual的意义在哪?
当析构函数被定义成virtual的以后,销毁父类对象时,会先执行子类的析构函数,销毁掉子类对象。
  • 为什么构造函数不能被定义成virtual的?
虚函数内部是通过虚函数表来实现的,在执行时能通过vptr指针指向正确的子类对象函数。而在创建对象时,必须要知道创建对象的准确类型,因此构造函数不能为虚。
  • 析构函数可以时内联函数吗?
可以

static关键字的作用:

  1. 修饰局部变量:使得该变量在函数运行完后不会被释放,一直存在于整个程序的运行周期。
  2. 限制函数或者变量的作用域:在某一模块内声明的static变量或者函数无法被其他模块使用,例如使用static修饰的全局变量其他模块不能使用,static修饰的函数其他模块也不能使用。
  3. 作为类成员函数或者变量:被static修饰过的成员变量或函数生存在整个程序周期中,所有的类共享同一个静态成员。使用前必须在类外部手动定义该变量,并且被static修饰过后无法访问类里面的this指针

一、基本排序算法

  1. 插入排序
  2. 选择排序
  3. 冒泡排序
  4. 梳排序

二、高级排序算法

  1. 快速排序
  2. 堆排序
  3. 计数排序
  4. 归并排序

三、各排序算法的比较

各排序算法总结

排序算法平均时间复杂度最好情况时间复杂度最坏情况时间复杂度空间复杂度是否稳定适用场景
插入排序O($n^2$)O(n),当序列已经有序时O($n^2$),序列逆序时。O(1)数组大部分有序
选择排序O($n^2$)O($n^2$)O($n^2$)O(1)数据量较小的情况
冒泡排序O($n^2$)O($n^2$)O($n^2$)O(1)数据量较小的情况
希尔排序O(n^(1.3~2)​)O(n^(1.3~2))O(n^(1.3~2))O(1)增量序列的选取会影响排序时间,希尔排序没有快速排序算法快,中等大小规模表现良好,对规模非常大的数据排序不是最优选择,但是比O($n^2$)复杂度的算法快。
快速排序O(nlogn)O(nlogn)哨兵选择为边界值时,O($n^2$)O(nlogn)不适合元素较小的数组排序
堆排序O(nlogn)O(nlogn)O(nlogn)O(n)需要大量的移动操作,且要额外的空间保存已排序数组
计数排序O(n)O(n)O(n)O(n*2)假设数组元素都在0-k的范围内,并且需要两个辅助数组,如果数据分布不均匀,出现一个特别大的数据会导致额外的空间增加。
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)合并时需要额外的内存空间
基数排序O (nlog(r)m),其中r为所采取的基数,而m为堆数O (nlog(r)m)O (nlog(r)m)O(r*m)需要额外的m个队列的辅助空间

在微博上看到了一个很有意思的题目:

最开始想了半天都没有想到解法,总觉得这是个不可能完成的。后面看评论才知道解法原来很简单:

把十个盒子的球分别编号1-10,然后把每个编号的球都取出它编号的个数,例如1号球取一个,2号球取两个,依次类推。最后把所有的球放到称上称,比预计的少了几克那么几号球就是次品了。

总结

其实题目挺有玄机的,很多人可能忽略了装满了球的盒子这个题眼,大部分原因解不出来是因为没看到这里。

如果知道有很多球可以使用,相信很多人都能很快想到解法。归根结底还是审题不仔细,导致错误结论下得太早。

一、线程的基本使用

正常情况下,一个进程只有一个一线程在运行。有了多线程之后,就可以使得程序在同一时间可以做多间不同的事情。

这样就可以利用起来很多被浪费掉的时间,例如执行阻塞任务,磁盘IO等等,这些等待的时间都可以被用来做其他的事情,这也就是多线程的用武之地。

1.1 线程标识

线程通过线程ID来标识,在linux环境中被定义为pthread_t类型。在调试中,我们可以把它当作一个整形变量打印,但是实际上在严谨的场合不能这么干,它并不等于整形。

判断两个线程id是否相等要使用linux提供的函数接口:

#include <pthread.h>
int pthread_equal(pthread_t t1, pthread_t t2);

对线程而言,可以通过pthread_self()函数来获得当前线程的ID,例如打印出一个函数中主线程的id:

#include <stdio.h>
#include <pthread.h>

int main() {
    pthread_t tid;

    tid = pthread_self();

    printf("main thread: %08x\n", tid);

    return 0;
}

编译运行:

main thread: 0x66744700
注意,多线程程序编译时要加-lpthread选项

1.2 创建一个函数

创建一个线程的函数原型:

#include <pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                  void *(*start_routine) (void *), void *arg);

各个参数的含义:

  • thread:用来接收新创建的线程ID,该参数不能省略,不能写成NULL
  • attr:设置线程的属性,一般为NULL
  • start_routine:线程启动的函数,是一个函数指针,线程启动后将调用这个函数
  • arg:自定义参数,会作为线程函数的启动参数传入

以下是一个简单的创建线程的示例,创建一个线程并打印出它当前的进程id和线程id:

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<pthread.h>
#include<string.h>

typedef unsigned int uint;

void f(const char *s) {
    pid_t pid = getpid();
    pthread_t tid = pthread_self();
    // 打印出当前的进程id和线程id
    printf("%s pid is %d, tid is 0x%x\n", s, pid, (uint)tid);
}

void *thread_start(void *arg) {
    f((char*)arg);
    return 0;
}

int main(){
    int err;
    pthread_t tid;
    // 创建线程
    err = pthread_create(&tid, 0, thread_start, (void*)"new thread:");
    if (err != 0) {
        fprintf(stderr, "pthread_create error: %s", strerror(err));
        return 0;
    }
    printf("main thread: pid is %d, child thread is 0x%x.\n", (int)getpid(), (uint)tid);
    // 等待线程执行完毕
    sleep(1);
    return 0;
}

运行结果:

main thread: pid is 18267, child thread is 0xe33ba700.
new thread: pid is 18267, tid is 0xe33ba700

根据两个线程打印出来的pid可以看到:多线程实际上还是处于同一个进程的。

二、线程终止

2.1 pthread_exit()

pthread_exit()的作用就是退出当前线程,并设置退出的返回值。定义为:

#include <pthread.h>
void pthread_exit(void *retval);

retval参数表示线程的退出状态。

线程也可以使用return来返回,但是在线程定义了清理函数的时候,如果使用return返回,清理函数将不会被执行。

2.2 pthread_join()

上面代码的主函数中,最后面有一个sleep(1)来等待子线程退出,这么做实际上是不合理的,因为线程和进程一样,执行的时机是不确定的,1S之后线程可能还没有执行完。

如果要在主线程等待子线程执行完毕的话,可以通过pthread_join()函数来完成,其定义为:

#include <pthread.h>
int pthread_join(pthread_t thread, void **retval);

参数含义:

  • thread:线程id
  • retval:线程的返回码

调用这个函数后,线程会一直阻塞,直到指定线程退出。如果调用时线程已经处于结束状态,那么函数会立即返回。

如果指定的线程被取消了,retval的值将会是PTHREAD_CANCELED。不关心线程返回值的话,可以直接把retval设为NULL。

注意,如果线程被分离了(执行了pthread_detach()),执行pthread_join()无效。

以下是一个调用pthread_exit()pthread_join()的示例:

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<pthread.h>
#include<string.h>

typedef unsigned int uint;

void *func1(void *arg) {
    pthread_t tid;
    tid = pthread_self();

    printf("this is func1(), tid = 0x%08x\n", tid);
    return (void *)111;
}

void *func2(void *arg) {
    pthread_t tid;
    tid = pthread_self();

    printf("this is func2(), tid = 0x%08x\n", tid);
    pthread_exit((void *)222);
}

// 创建一个线程,并打印出对应的信息
int pthread_create_ex(pthread_t *tid, void *(pf)(void*)) {
    int err;

    err = pthread_create(tid, 0, pf, NULL);
    if (err != 0) {
        fprintf(stderr, "pthread_create error: %s", strerror(err));
    } else {
        printf("main thread: child thread is 0x%x\n", tid);
    }

    return err;
}

// 回收一个线程,并打印相关信息
int pthread_join_ex(pthread_t tid) {
    int err, retval;

    err = pthread_join(tid, (void *)&retval);
    if (err != 0) {
        fprintf(stderr, "pthread_join error: %s", strerror(err));
    } else {
        printf("thread 0x%x has exit, code %d\n", tid, retval);
    }

    return err;
}

int main(){
    int err; 
    pthread_t tid1, tid2;

    err = pthread_create_ex(&tid1, func1);
    if (err != 0)
        return -1;

    err = pthread_create_ex(&tid2, func2);
    if (err != 0)
        return -1;

    err = pthread_join_ex(tid1); 
    if (err != 0)
        return -1;

    err = pthread_join_ex(tid2);
    if (err != 0)
        return -1;
    
    return 0;
}

这里的代码用两个函数作为不同的线程开始,分别通过returnpthread_exit来返回,运行结果:

可以看到,pthread_join()都能拿到返回值,那这两者是否有区别呢?下面将会继续探究。

2.2 pthread_cancel()

pthread_cancel()函数可以取消同一进程中的其他线程:

#include <pthread.h>
int pthread_cancel(pthread_t thread);

参数就是希望取消的线程id,这会使得被取消的线程返回PTHREAD_CANCELED

#include <stdio.h>
#include <pthread.h>

void *f1(void *arg) {
    int i = 0;
    while (i++ < 5) {
        printf("second %d\n", i);
        sleep(1);
    }
    pthread_exit((void *)99);
}

void *f2(void *arg) {
    pthread_t tid;

    tid = *(pthread_t *)arg;

    sleep(1);
    printf("pthread_cancel --> 0x%08x\n", tid);
    pthread_cancel(tid);
    pthread_exit((void *)0);
}

int main() {
    pthread_t tid1, tid2;
    pthread_t ret1, ret2;

    pthread_create(&tid1, NULL, f1, NULL);
    pthread_create(&tid2, NULL, f2, (void *)&tid1);

    pthread_join(tid1, (void *)&ret1);
    pthread_join(tid2, (void *)&ret2);

    printf("tid1: %08x, exit status: %d\n", tid1, ret1);
    printf("tid2: %08x, exit status: %d\n", tid2, ret2);
    printf("PTHREAD_CANCELED = %d\n", PTHREAD_CANCELED);

    return 0;
}

以上是一个简单的调用示例,产生两个线程,一个线程每隔一秒打印一次,另一个线程则在一秒后关闭该线程。

主线程中等待退出并打印返回码,结果如下所示:

被取消掉的线程91ef7700并没有返回其函数内定义的99,而是-1,也就是PTHREAD_CANCELED的值。

一、问题描述

在使用shared_ptr时,如果出现了循环引用(如链表节点的next指向),就会导致内存泄漏。

例如以下两个类,内部互相有一个指向对方的智能指针,在生存空间结束后就不会被释放掉:

#include <iostream>
#include <memory>
using namespace std;

class CTestB;

class CTestA {
public:
    shared_ptr<CTestB> b;
    CTestA() {
        cout << "CTestA()" << endl;
    }
    ~CTestA() {
        cout << "~CTestA()" << endl;
    }
};

class CTestB {
public:
    shared_ptr<CTestA> a;
    CTestB() {
        cout << "CTestB()" << endl;
    }
    ~CTestB() {
        cout << "~CTestB()" << endl;
    }
};

int main() {
    shared_ptr<CTestA> a(new CTestA);
    shared_ptr<CTestB> b(new CTestB);

    cout << "a.use_count = " << a.use_count() << endl;
    cout << "b.use_count = " << b.use_count() << endl;

    a->b = b;
    b->a = a;

    cout << "a.use_count = " << a.use_count() << endl;
    cout << "b.use_count = " << b.use_count() << endl;

    return 0;
}

编译后的运行程序的结果:

原因很简单,a->b = b导致b的引用计数增加,b->a = a导致a的引用计数增加,在程序运行完后,a、b自行析构引用计数都会减一,但是此时引用计数都是1,因此不会释放。

二、解决方法

shared_ptr循环引用要通过weak_ptr来解决,weak_ptr也是智能指针的一种,不过它是一种弱引用,不会增加智能指针的引用计数。

分别修改两个类为以下形式:

class CTestA {
public:
    weak_ptr<CTestB> b;
    // ...
}

class CTestB {
public:
    weak_ptr<CTestA> a;
    // ...
}

运行结果:

一、互斥量

互斥量的本身是一把锁,在访问共享资源时前对互斥量加锁,访问完成后释放。在对互斥量加锁后,其他线程如果想再次加锁,操作会被阻塞,直到锁被释放为止。

创建互斥量和销毁互斥量的函数定义:

#include <pthread.h>

int pthread_mutex_init(pthread_mutex_t *restrict mutex,
      const pthread_mutexattr_t *restrict attr);
int pthread_mutex_destroy(pthread_mutex_t *mutex);

也可以直接使用宏定义PTHREAD_MUTEX_INITIALIZER完成对锁的初始化:

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

对互斥量加锁和解锁:

#include <pthread.h>

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

其中,pthread_mutex_trylock()会尝试对互斥量加锁,如果此时互斥量没有被锁住,加锁成功。如果互斥量已经被其他线程锁住了,返回EBUSY。还有一个可以执行超时加锁的函数:

#include <pthread.h>
#include <time.h>

int pthread_mutex_timedlock(pthread_mutex_t *restrict mutex,
        const struct timespec *restrict abs_timeout);

对加锁设置超时时间,如果在指定时间内,加锁不成功(即锁还没有被释放或者释放了又被其他线程抢占了),加锁失败,直接返回,不阻塞线程了。

二、使用示例

分别创建50个线程,每个线程对全局变量n执行1000次自加操作:

#include <stdio.h>
#include <pthread.h>
#include "log.h"

static int n = 0;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

// 线程函数
void *f(void *args) {
    int idx = 0;
    // n自加1000次
    while (idx++ < 1000) {
        pthread_mutex_lock(&mutex);
        n++;
        pthread_mutex_unlock(&mutex);
    }
    return 0;
}

int main() {
    int i;
    pthread_t ts[50];
    // 创建50个线程
    for (i = 0; i < 50; i++) {
        pthread_create(&ts[i], 0, f, 0);
    }

    // 回收线程
    for (i = 0; i < 50; i++) {
        pthread_join(ts[i], 0);
    }

    pthread_mutex_destroy(&mutex);
    info("n = %d\n", n);

    return 0;
}

执行结果:

mutex.png

三、死锁

当多个线程之间,对多个锁产生不同的竞争关系时,就有可能发生死锁现象。

注意:死锁只会发生在一个线程试图锁住另一个线程以相反顺序锁住的互斥量

例如此时有A/B两个锁,t1t2两个线程分别执行以下抢占:

  1. t1对A加锁,t2对B加锁,两者都加锁成功
  2. t2再对A加锁,t1对B加锁,此刻t1会等待t2释放B锁,而t2又要等待t1先释放A锁,此时产生死锁。

一、读写锁

读写锁和互斥量相似,都是对共享空间执行加锁和解锁的过程。不过,读写锁比互斥量有更高的并行性。

读写锁有三种状态:读模式加锁、写模式加锁和不加锁。读写锁只允许同时有一个线程占有写模式的锁。

这就意味着读锁可以同时被多个线程拥有,读写锁特别适合读次数远大于写次数的场景。

1.1 创建并初始化一把锁

读写锁的数据类型为pthread_rwlock_t,使用以下方式初始化和销毁:

#include <pthread.h>

int pthread_rwlock_init(pthread_rwlock_t *restrict rwlock,
      const pthread_rwlockattr_t *restrict attr);
int pthread_rwlock_destroy(pthread_rwlock_t *rwlock);

1.2 加锁和解锁

#include <pthread.h>

// 加读锁
int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
// 加写锁
int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
// 解锁
int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);

pthread_rwlock_rdlock()可以同时对一把锁使用,不会阻塞线程。

1.3 带超时的读写锁

#include <pthread.h>
#include <time.h>

int pthread_rwlock_timedrdlock(pthread_rwlock_t *restrict rwlock,
      const struct timespec *restrict abs_timeou
int pthread_rwlock_timedwrlock(pthread_rwlock_t *restrict rwlock,
      const struct timespec *restrict abs_timeout);

二、示例

#include <stdio.h>
#include <pthread.h>
#include "log.h"

static int n = 0;

pthread_rwlock_t rwlock;

// 线程函数
void *f(void *args) {
    int idx = 0;
    while (idx++ < 1000) {
        pthread_rwlock_wrlock(&rwlock);
        n++;
        pthread_rwlock_unlock(&rwlock);
    }
    return 0;
}

int main() {
    int i;
    pthread_t ts[50];

    pthread_rwlock_init(&rwlock, NULL);

    for (i = 0; i < 50; i++) {
        pthread_create(&ts[i], 0, f, 0);
    }

    for (i = 0; i < 50; i++) {
        pthread_join(ts[i], 0);
    }

    pthread_rwlock_destroy(&rwlock);
    info("n = %d", n);

    return 0;
}

执行结果:

rwlock.png