2016年3月 – 我的经验分享

placement new

pi = new (ptr) int; //placement new

括号里的参数ptr是一个指针，它指向一个内存缓冲器，placement new将在这个缓冲器上分配一个对象。Placement new的返回值是这个被构造对象的地址(比如括号中的传递参数)。placement new主要适用于：在对时间要求非常高的应用程序中，因为这些程序分配的时间是确定的；长时间运行而不被打断的程序；以及执行一个垃圾收集器 (garbage collector)。

简单来说，placement new是创建对象（即调用对象的构造函数），但是不分配内存，使用了现有的内存。

delete与delete[]的区别

1.如果对象是无析构函数，或者类型是基本的数据类型，new出来的一个数组，使用delete p和delete[]p没有区别。

2.如果new出来的对象具有析构哈书，使用delete p只会调用p[0]的析构函数，而其余的均不会调用，可能会造成内存泄漏。

快排（二）—-寻找第k小的数

之前的快排采用了一个指针和for循环，这次使用的是双指针，相对比较正规，不过这次是使用快排来实现寻找第k小的数，去掉quickSort里面的判断，可以实现快排。

原来的代码：快排（一）

int partition(vector<int>&arr, int l, int r)
{
	int pivot = arr[l];
	int i = l + 1;
	int j = r;

	while (i <= j)
	{
		while (i <= j&&arr[i] <= pivot)
			i++;
		while (i <= j&&arr[j] >= pivot)
			j--;
		if (i <= j)
			swap(arr[i], arr[j]);
	}
	swap(arr[j], arr[l]);
	return j;
}

void quickSort(vector<int>&arr, int l, int r,int idx,int&target)
{
	if (l > r) return;
	int k = partition(arr, l, r);
	if (k == idx)
	{
		target = arr[k];
		return;
	}
	else if (k < idx)
		quickSort(arr, k + 1, r, idx, target);
	else
		quickSort(arr, l, k - 1, idx, target);
}

206. Reverse Linked List（使用递归的方法，新建一个指针，总共使用两个指针）

非递归方法参考：206. Reverse Linked List（只需新建两个指针，借用传入的head指针，共使用三个指针）

递归实现代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL) return head;
        
        ListNode* tmp=reverseList(head->next);//把head->next后面的链表翻转
        head->next->next=head;//翻转后的链表，head->next是尾节点，把head连接到尾部
        head->next=NULL;//因为head是尾部，所以指向NULL
        return tmp;
    }
};

Linux内核（深入理解linux内核+linux内核设计与实现）笔记

1.内核中使用双向循环链表来组织进程描述符（task_struct），进程描述符即我们操作系统中学习的进程控制块PCB，进程描述符里面包含进程的基本信息（thread_info），所接收的信号（signal_struct），进程号，父进程指针等。

2.由于在某些情况下，内核必须能从进程的PID到处对应的进程描述符指针，如kill系统调用从P1进程向P2发送信号，需要从P2的进程描述符中取出记录挂起信号的数据结构指针。所以引入了4个散列表，分别是PIDTYPE_PID（进程的PID），PIDTYPE_TGID（线程组领头进程），PIDTYPE_PGID（进程组领头进程的PID），PIDTYPE_SID（会话领头进程的PID），使用双向链表来解决冲突。

3.进程调度：采用CFS：完全公平调度算法。该算法有两个特点：（1）设有最小时间颗粒，即最低的CPU占用时间（如1ms），避免频繁的切换进程造成上下文切换的浪费；（2）按照nice的相对值来分配时间，而不是绝对值，如nice值为20和0的两个进程分配的时间为5ms和15ms，而nice值为1和0的两个进程分配的时间仍为5ms和15ms。

4.信号在内核中是如何发送传递的？

向某个进程a发送信号，会在a的进程描述符中信号相关变量设置，相关的有共享挂起信号队列，有私有挂起信号队列，向某个进程组发送的信号，会挂在共享挂起信号队列中，向单独一个进行发送的信号，会挂在私有挂起信号队列中。相应的进程在从内核态转到用户态时，会先处理可以处理的信号（没有阻塞的信号），然后再回到用户态。

5.init进程的pid号为1，内核中有pid为0的swapper进程，它只有在CPU不能执行其他进程时才执行。

6.Linux下如何进行进程调度？

对于普通进程，采用CFS(完全公平调度)算法，CFS使用红黑树组织可运行进程队列。

对于实时进程，有两种调度方法，分别是SCHED_FIFO和SCHED_RR，FIFO是简单的先入先出调度算法，不适用时间片。而SCHED_RR则是带有时间片的SCHED_FIFO，任务好紧它的时间片时，同一优先级的其他实时进程被轮流调度。

206. Reverse Linked List（只需新建两个指针，借用传入的head指针，共使用三个指针）

方法一：相当于头插法，不断地把后面的节点插入到头部的next位置，思路是先反转头结点后面的节点，最后再把头结点添加到末尾。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        
        ListNode* first=head->next;//第一个翻转的节点
        ListNode* tmp;//过度节点
        
        while(first->next)
        {
            tmp=first->next;
            first->next=tmp->next;
            tmp->next=head->next;
            head->next=tmp;
        }
        
        //这个时候first为现在最后的节点，head->next为元链表最后的节点
        tmp=head->next;
        head->next=NULL;
        first->next=head;
        return tmp;
    }
};

方法二：就地翻转

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //就地反转
        if(head==NULL || head->next==NULL) return head;
        
        ListNode* pre=NULL;
        ListNode* next=NULL;
        
        while(head)
        {
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        
        return pre;
    }
};

C++的观察者模式

观察者模式主要使用到了函数指针，类似的结构在linux内核中比较常见。

//C++实现观察者模式

#include<vector>
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;

template <class Handler>
class event //模板类，这就决定了这个委托可以委托任何类型了函数指针，只要你有，我就能委托  
{
public:
	event()
	{//构造函数
	}
	vector<Handler>& GetEvent()
	{//获取Event列表
		return m_HandlerList;
	}
	virtual void add(const Handler v)
	{//虚函数，添加时间到vector中
		m_HandlerList.push_back(v);
	}
	virtual void remove(const Handler v)
	{//删除vector
		vector<Handler>::iterator it = m_HandlerList.begin();
		for (; it != m_HandlerList.end(); it++)
		{
			if ((*it) == v)
			{//如果相等，则删除
				m_HandlerList.erase(it);
				break;
			}
		}
	}
private:
	vector<Handler> m_HandlerList;//时间列表
};

//参数列表为空，EventHandler是函数地址
typedef void   (*EventHandler)(void);
class MyClass
{
public:
	MyClass(){}
	void Notify()
	{
		size_t nCount = AllEvent.GetEvent().size();
		for (size_t i = 0; i < nCount; i++)
		{
			EventHandler notifyEvent = AllEvent.GetEvent()[i];
			(*notifyEvent)();

			//另外的两种写法
			//(*(AllEvent.GetEvent().at(i)))();
			//(*(AllEvent.GetEvent()[i]))();
		}
	}
public:
	event <EventHandler> AllEvent;
};


void MyEventHandler1()
{
	printf("This is a event!\n");
}
void MyEventHandler2()
{
	printf("This is another event!\n");
}

int main(void)
{

	MyClass Obj;
	Obj.AllEvent.add(MyEventHandler1);
	Obj.AllEvent.add(MyEventHandler2);
	Obj.Notify();
	Obj.AllEvent.remove(MyEventHandler1);
	Obj.Notify();
	printf("Over!\n");
	system("pause");
	return 0;


}

C++中的单例模式

注意C++的单例模式，其static成员需要在外部进行初始化。


//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<bitset>
using namespace std;

class Singleton
{

public:
	static Singleton* GetInstance()
	{
		if (instance == NULL)
			instance = new Singleton();

		return instance;
	}

private:
	Singleton(){};
	static Singleton* instance;
};
//C++单例模式需要先创建instance
//Singleton* Singleton::instance = new Singleton();
Singleton* Singleton::instance = 0;
int main(void)
{
	Singleton*s1 = Singleton::GetInstance();
	Singleton*s2 = Singleton::GetInstance();

	if (s1 == s2)
		cout << "it's same!" << endl;
	return 0;


}

月份：2016年3月

密码保护：20160325面经Y