Month: March 2016

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

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

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

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

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

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

原来的代码：快排（一）
[c language=”++”]
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);
}
[/c]
 

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

递归实现代码：
[c language=”++”]
/**
* 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;
}
};
[/c]
 

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，任务好紧它的时间片时，同一优先级的其他实时进程被轮流调度。

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

[c language=”++”]
/**
* 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;
}
};
[/c]

方法二：就地翻转

[c language=”++”]
/**
* 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 language=”++”]
//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成员需要在外部进行初始化。
[c language=”++”]

//#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;

}
[/c]