C++之copy initialized

内容摘抄自
https://github.com/Mooophy/Cpp-Primer/tree/master/ch13
https://stackoverflow.com/questions/21010371/why-is-it-not-efficient-to-use-a-single-assignment-operator-handling-both-copy-a

13.52 Explain in detail what happens in the assignments of the HasPtr objects on page 541. In particular, describe step by step what happens to values of hphp2, and of the rhs parameter in the HasPtr assignment operator.

class HasPtr{
  public:
    HasPtr(HasPtr &&p) noexpect;
    HasPtr & operator=(HasPtr rhs);
}

rhs parameter is nonreference, which means the parameter is copy initialized. Depending on the type of the argument, copy initialization uses either the copy constructor or the move constructor.

lvalues are copied and rvalues are moved.

Thus, in hp = hp2;hp2 is an lvalue, copy constructor used to copy hp2. In hp = std::move(hp2);, move constructor moves hp2.

13.53 As a matter of low-level efficiency, the HasPtr assignment operator is not ideal. Explain why. Implement a copy-assignment and move-assignment operator for HasPtr and compare the operations executed in your new move-assignment operator versus the copy-and-swap version.

As the problem suggests, it’s “a matter of low-level efficiency”. When you use HasPtr& operator=(HasPtr rhs) and you write something like hp = std::move(hp2);ps member is copied twice (the pointer itself not the object to which it points): Once from hp2 to rhs as a result of calling move constructor, and once from rhs to *this as a result of calling swap. But when you use HasPtr& operator=(HasPtr&& rhs)ps is copied just once from rhs to *this.

C++之string &a和const string &b

在做题的时候发现了一个问题:

string &a=string();//error
const string &a=string();//true

在C++Primer第二章找到了答案,除了两个特例之外,引用的类型和对象的类型必须匹配。

string &属于左值引用,而string()属于右值,因此不匹配,出现报错。const string& a属于两个特例中的其中一个,因此const string& a不报错。

C++之尝试把类成员作为回调函数

问题提出:

在使用openGL的时候我想通过在类里面使用并且定义回调函数,经过对这个问题了解并且寻找解决办法,我才发现其实这绝非易事。

尝试解决:

一开始发现普通的成员函数由于隐藏着一个参数this,因此他无法作为回调函数。于是我将函数改成静态成员函数。但是这时候却发现静态成员函数只能访问静态成员变量,这就失去了我想把回调函数写在类里面的初衷,我希望这个函数可以访问成员变量而不仅仅是静态成员变量。

第二种方法是利用友元函数,但是友元函数同样需要传入对象才可以操作对象的成员,所以无意义。

这时候我发现了一种方法,bind函数,可以将函数和参数绑定在一起,这样就可以实现对成员函数使用bind把他和第一个参数this绑定在一起,进而把他作为回调函数。

auto b_reshape=std::bind(&Game::reshape,this,_1,_2);
auto b_display=std::bind(&Game::display,this);
auto b_gameOver=std::bind(&Game::gameOver,this);
auto b_keyOperation=std::bind(&Game::keyOperation,this);
auto b_welcomeScreen=std::bind(&Game::welcomeScreen,this);

编译。发现

错误,因为bind生成是std::function,而回调函数要求的是c风格function pointer,除非再进一步转化,否则二者是不同的。

解决:

最终我做了妥协,选择使用类外函数对成员函数进行再一步的包装,并且在类外使用回调函数。

C++ 之静态成员函数的限制

问题提出:

发现在类中使用OPENGL时候无法直接将成员函数作为回调函数,需要使用静态成员函数,于是决定探究一下静态成员函数。

一探究竟:

静态成员函数和非静态成员函数很大的不同在于静态成员函数无法直接访问非静态成员变量。原因在于类的静态成员(变量和方法)属于类本身,在类加载的时候就会分配内存,而类的非静态成员需要在定义对象的时候才会分配内存,因此当一个类的静态成员中去访问其非静态成员时候,类的非静态成员不存在的时候类的静态成员就已经存在了,访问一个内存中不存在的东西当然会出错。

在静态成员函数的实现中不能直接引用类中说明的非静态成员,可以引用类中说明的静态成员。如果静态成员函数中要引用非静态成员时,可通过对象来引用。

class M
{

public:
     M(int a) { A=a; B+=a;}
     static void f1(M m);
private:
     int A;
     static int B;
};

void M::f1(M m)
{
     cout<<“A=”<<m.A<<endl; //静态成员函数中通过对象来引用非静态成员
     cout<<“B=”<<B<<endl;
}

以上内容引用自:https://www.cnblogs.com/jianglei-tz/archive/2012/09/02/static-member-function.html

C++之类相互引用问题

题:

在Game类中使用PacMan的静态成员出现了

在A类中是可以使用B类的静态成员变量的,那这个错误来自哪里?

解决:

原来在PacMan.h中#include”Game.h”,在Game.h中#include”PacMan.h”,将PacMan.h中的include去掉即可。

一探究竟:类之间的相互引用

//A.h
class A
{
 B b;
}

//B.h
class B
{
 A a
}

第一个问题,类之间的相互引用是不能出现都定义对象的,因为这样会陷入a b a b a b这种无限循环的状态中,因此在两者相互引用中,至少有一方是使用指针或者说两者都使用指针。

//A.h
#include "B.h"
class A
{
  int i;
  B b;
}

//B.h
#include "A.h"
class B
{
  int i;
  A* a;
}

第二个问题,修改成这样后就出现了原问题,两边都Include了彼此,会产生错误。

解决方案是一边包含另一个类的头文档,另外一个采用前向声明class *,然后在他的实现文档里面包含头文件。

//A.h
#incldue "B.h"
class A
{
  int i;
  B b;
}

//B.h
class A;
class B
{
  int i;
  A* a;
}

//B.cpp
#include "A.h"

注意:class *;这种前向声明只适用与定义类指针或类应用,而不能定义类对象或者函数的变量名称,因此A是定义B的对象,所以需要在A里面include B。

以上内容引用自:http://www.cnblogs.com/zendu/p/4987971.html

C++之类内静态成员变量

类内的static成员变量可以作为类共享变量,在吃豆人游戏中我在角色类中使用static成员存储地图指针,这样就可以达到所有角色类都共享一张地图的目的,这次笔记是记录static变量的使用过程。

首先是static 成员的初始化,除非是const或constexpr,staic成员一般采用类内声明,类外初始化

class A
{
 public:
   static int a;
 private:
  static int b;
}
int A::a=10;
int A::b=10;
int main()
{
  cout<<A::a;
}

这里a和b都是static成员变量,不管是公有还是私有,都需要在类外初始化,但是私有的成员变量初始化后无法直接使用。

接下来就是static成员变量的继承问题了

class Base
{
  public:
    static int a;
}
class Son1:public Base
{
}
class Son2:public Base
{
  public:
   static int a;
}
int Base::a=10;
int Son2::a=10;

子类是可以继承的父类的静态成员变量的,但是初始化是使用父类的名称进行初始化(son1),而如果子类有父类的同名静态成员变量就会覆盖父类的静态成员变量(son2)。

Dijkstra’s 最短路径算法究竟能不能计算负权重

Cousera普林斯顿算法课提出,Dijkstra是不可以计算含负权值的路线的,但是经过自己跑了一遍发现某些路径上是可以,这里参考了知乎stackflow上的回答。

这里的问题主要在于如何实现Dijkstra,从algs4官方上的实现上这个版本的Dijkstra是可以计算负权值的,其原因在于如知乎所讲的该实现是优先队列优化+允许重入队,因此在出现负权值的时候该路径可以进行二次修改,如stackflow中的举例,在二次修改后d(c)=-200。

同时允许重入队也让Dijkstrea计算具有负权值的图时时间复杂度不好分析,算法的运行时间依赖于输入数据的分布。在非负权图的情况下,此算法与算法 2 行为完全相同,时间复杂度为O((V+E)lg V);而对于有负权边但无负权回路的图,算法的最坏运行时间是顶点数目的指数。因此在有负权值的计算并不采用这种算法。

字符串那些烦人事

1.sprintf,strcpy,strncpy

做作业的时候发现对这三个函数的理解有点混乱,整理一下三个复制字符串函数的区别

1.

sprintf(s1,”%s”,s2)————将s2字符串输入到s1,包括’\0’,同理如果没有遇到”\0″,会一直复制到下一个字符串,这一点类似于strcpy

2.

strcpy(s1,s2)——————-将s2复制到s1,包括’\0’。

这两种复制都存在一种问题就是如果s2字符串没有以’\0’结尾就会错误的一直往下复制

3.

strncpy(s1,s2,n)————–复制s2的前s个字符,

这里我发现存在一种可能会导致错误的用法,strncpy(s1,s2,strlen(s2)),strlen并没有将’\0’计算进去,因此这个复制不会复制’\0’,因此假设

s1=”abc”,s2=”12″,strncpy(s1,s2,strlen(s2))————s1=”12c”—-s1保留原来的字符

总结的来说strcpy会复制到\0,strncpy会忠心耿耿的复制完n个字符,空的补\0,sprintf多用在格式化输入。

2.char *,char []

char  * s1="abc";
char s2[4]="abc";
char *s3=malloc(sizeof(char)*4);

s1创建在常量区无法修改,s2创建在在栈区为一个字符数组,s3创建在堆区

3.操作文件时不要使用str

我们str系列的操作都是以\0作为结尾,然而当我们在操作文件传输信息时,这些信息有一些是含有\0的但这并意味着他的结束,特别是二进制文件。

CSAPP: 文件I/O,各大输出流的不同

(一) Unix I\O , RIO ,标准I\O

刚接触文件I/O的时候,原来一直习惯,也只会使用printf的我被几个输入函数绕得团团转,于是利用这篇文章整理一下这三大代表,从不同在哪,为什么需要这种不同分析,(每一个轮子的诞生总是因为他被需要

Unix I\O

write() 向描述符为fd的文件中写入最多n个字节到buf中,read则为读取,write和read做为Unix I\O,是在操作系统内核中实现的,实际上RIO和标准I\O也都是对他进行二次封装,因此他实际上是一个系统调用,上代码看效果‘

#include "csapp.h"
  int main(void)
 {
  char c;
  while(Read(STDIN_FILENO, &c, 1) != 0)    //STDIN_FILENO代表标准输入的描述符
  {
  write(STDOUT_FILENO, &c, 1);                 //STDOUT_FILENO代表标准输出的描述符
  }                   
  exit(0);
}

用strace工具跟踪查看他的运行效果

每一行代表一次系统调用,由于我们设定是1,因此每一次的系统调用都只写入和读取一次字符。

RIO

Unix I\O是底层的调用,可以通过他完成所有的读写任务,但也因为他在最底层,所以在任务上他并不能完成得很好,会遗留下一些漏洞,也正是为了解决这些漏洞这些需求,诞生了后面的I\O函数,每一个漏洞就对应着一个新的解决方法。

如果说Unix IO是底层的调用,标准I\O(也就是我们平时用的printf)就是属于比较高层的封装了,而RIO是在CSAPP中的包,我认为它处于一个中间位置,一方面我们可以看到他的源码其实是通过还是基于Unix I\O的实现,另一方向我们可以看到他的实现很好的解决了一些Unix I\O的漏洞,因此通过他可以把上下两层的东西都串在一起。

首先是Unix IO遗留下的第一个漏洞,不足值

在第一次看书的时候没有细看,所有一直不太理解为什么需要一个RIO的实现,直到我做了第一个服务器的连接练习回来看到这段话的时候才深有体会,不然我会一直觉得不足值似乎就是一个大多时候可以忽略的东西。

想象一下一个简单的网络应用,你是客户端,对面的妹子是服务端,然后你通过把你想说的话写在一个文件上,这个文件会传到妹子那里进行读取,你们之间的交流是通过读写文件。OK,开始,你想说“我想追你朋友”,于是你用write写入这句话write(file,”我想追你朋友”,6),你要写入6个字,然后系统调用,由于某种原因出错,他只写进了4个字然后就停止了,于是系统回来告诉你我只写了4个字而且我发过去了,你…..(¥#@¥%

因此rio_write的出现就是为了避免这种悲剧的发送,他会让系统一直写直到6个字都写进去为止,上源码

   ssize_t rio_writen(int fd, void *usrbuf, size_t n)
{
    size_t nleft = n;
    ssize_t nwritten;
    char *bufp = usrbuf;

    while (nleft > 0)
  {
       if ((nwritten = write(fd, bufp, nleft)) <= 0)
 {
       if (errno == EINTR) /* Interrupted by sig handler return */
           nwritten = 0; /* and call write() again */
       else
           return -1; /* errno set by write() */
  }
   nleft -= nwritten;
   bufp += nwritten;
}
   return n;
}

rio_writen记录了要读数量n,每次write后都会获取已读数量并以此计算剩余未读数量,在while循环里面,rio_write会一直等待到剩余未读数量为0为止,因此我们不会出现只写了一半的数量然后就退出的情况。如果中途write返回小于等于0,则判断是否被打断,如果是被打断,则设置重新写一次,否则则是读取到EOF,说明已经读到了尽头,这种情况下不足值是允许的,因此退出。

rio_writen很好的解读了第一个漏洞,不足值的问题,这也是为什么书上会推荐我们在进行网络编程的时候使用这个接口去代替write。接下来是第二个漏洞,这个漏洞存在于以上的两种方法。

我们继续使用strace工具去跟踪rio_writen的运行,如图:

可以看到每一次读写都是一次系统调用(write调用),这和write的调用是一样的,系统调用的时候需要从用户态切换到系统态,因此这种做法会导致系统频繁的从用户态切换到系统态从而产生效率问题。

为解决这个问题,RIO的rio_read还有另外一个缓存版本,原理就是每次读先把尽量多的内容读取到缓存区,然后再根据用户的需要读取数量,比如我想要读取4个字符,实际上这个函数会读取40个字符到缓存区再返回前4个字符,这个方法的好处在于往后我再去读的时候就可以不需要进行系统调用,可以直接从缓存区读取以达到节省效率。上代码。

#define RIO_BUFSIZE 8192
    typedef struct {
     int rio_fd; /* Descriptor for this internal buf */
    int rio_cnt; /* Unread bytes in internal buf */
    char *rio_bufptr; /* Next unread byte in internal buf */
    char rio_buf[RIO_BUFSIZE]; /* Internal buffer */
  } rio_t;

   void rio_readinitb(rio_t *rp, int fd)
{
   rp->rio_fd = fd;
   rp->rio_cnt = 0;
   rp->rio_bufptr = rp->rio_buf;
}

        static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)
{
        int cnt;

       while (rp->rio_cnt <= 0) 
      { /* Refill if buf is empty */
          rp->rio_cnt = read(rp->rio_fd, rp->rio_buf,
          sizeof(rp->rio_buf));
         if (rp->rio_cnt < 0) 
        {
        if (errno != EINTR) /* Interrupted by sig handler return */
            return -1;
        }
         else if (rp->rio_cnt == 0) /* EOF */
            return 0;
         else
           rp->rio_bufptr = rp->rio_buf; /* Reset buffer ptr */ 
     }

/* Copy min(n, rp->rio_cnt) bytes from internal buf to user buf */
       cnt = n;
       if (rp->rio_cnt < n) 
           cnt = rp->rio_cnt;
       memcpy(usrbuf, rp->rio_bufptr, cnt);
       rp->rio_bufptr += cnt;
       rp->rio_cnt -= cnt;
      return cnt;
}
ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n)
{
   size_t nleft = n;
   ssize_t nread;
   char *bufp = usrbuf;

  while (nleft > 0) 
{
 if ((nread = rio_read(rp, bufp, nleft)) < 0)
    return -1; /* errno set by read() */
 else if (nread == 0)
    break; /* EOF */
 nleft -= nread;
 bufp += nread;
}
return (n - nleft); /* Return >= 0 */
}

使用RIO缓存版本之前要先使用rio_readinitb(rio_t *rp, int fd),我们可以看到这个函数实际上是把fd文件描述符和一个rp指针建立联系,rp结构体里面存储着文件描述符和缓存区。static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)是内部使用的读函数,ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n)是外部使用的读函数,为什么会有两个读函数,看实现就发现内部的读函数是用来代替无缓存版本(就是上面那个rio版本)的read,他不再是直接从描述符直接读取,而是判断缓存区是否为空,空则将数据读取进缓存区,否则直接从缓存区读取。而外部使用的函数和无缓存版本的是一样,他使用内部读取函数读取字符,并且保证读取字符数量是用户设定的数量。

两个版本的区别

无缓存版本
有缓存版本

标准I\O

最后的标准I\O也就是通常我们使用的fprintf,fputs,fgets系列,他使用的实际类似的这种缓存机制,因此有时候我们会发现printf(“hello”)没有输出,关键就是在于aaa只被缓存,而没有被传入到标准输出,你会发现printf(“hello\n”)就可以了,因为遇到了换行符”\n”这段字符就从缓存被传入到了标准输出。

在日常的使用中我们通常都可以直接使用标准I\O,因为他足以保证高效率,但在多线程或者网络编程的场景中,标准I\O却不被推荐,原因也是因为缓存机制。这里有一点要注意到,当你使用标准I\O打开一个文件进行同时读写,读写操作都是有缓存的,而且还是用一块缓存!想象一下我们先写满缓存,然后没有进行fflush(清空缓存区)再进行读操作,是什么东西会被读回来。这种情况下会很容易造成缓存区的混乱。因此书上推荐我们使用RIO I\O,一开始我疑惑RIO不是也是缓存机制吗,后来才想到RIO只有读缓存。

再想象一下多个线程使用标准输出,使用同一块缓存区,如果没有及时清空,同样很容易就会造成缓存区的混乱输出一些莫名的东西出来。

标准I\O在日常中普遍被使用,但是充分了解这些机制有助于我们看清有时候一些莫名其妙的输入。

参考:

1.代码片段均摘抄自CSAPP

2.知乎大佬们的回答

CSAPP:垃圾回收

(一)Mark&Sweep Garbage Collectors

一个Mark&Sweep Gabage Collector包含mark阶段和sweep阶段,首先是mark阶段

void mark(ptr p) 
{
//判断p指针是否指向一块有效的block区域,若是,该block区域head的指针
if ((b = isPtr(p)) == NULL)
return;
//判断该Header是否已经被标记
if (blockMarked(b))
return;
//若无标记,进行标记,并且把该block的每一个字节进行递归mark
markBlock(b);
len = length(b);
for (i=0; i < len; i++)
mark(b[i]);
return;
}

过程:

如图第一次传入的p指针是root point,即一个在堆区外指向堆区内的指针(就是我们通常定义的指针),这个指针指向堆区内的block1,我们通过这个指针进入到堆区内mark该block,由于block1可能指向其他的block,因此我们进行搜索1,2,3,4区域,若该区域是一个指针则进入指向区域,于是我们在区域2搜索到了block2,同理递归搜索到block3..以此类推直到搜索不到。像block4,block5一个root point连接的block就不会被mark,因此他们就是garbage.

mark操作:

如图的mark操作实际上是在Head的第二位置1,Head是存储的是该block的size,由于block的地址是对齐8,因此每一个block长度至少为8,那么size的低三位则永远为0,因此可供我们使用。一般第一位存储的是该block是否被分配。

然后是sweep阶段

void sweep(ptr b, ptr end) 
{
//b为堆区开头的block,end为堆区的结尾
while (b < end)
 {
//该block是否被标记,若是则解除标记
if (blockMarked(b))
unmarkBlock(b);
//该block是否被分配,若被分配且在没有被标记,说明为garbage,回收
else if (blockAllocated(b))
free(b);
//下一个block
b = nextBlock(b);
}
return;
}

过程:

如图从b开始搜索block1的head,判断是否被标记,是否为garbage,然后nextBlock跳到block2,继续搜索直到end


两个阶段后回收完成。

(二)Conservative Mark&Sweep for C Programs

看似没问题的流程却在c语言的实现中存在着两个问题,问题主要出现在mark阶段:

1.isPtr(p)在mark阶段判断传入的指针p是否指向一块有效的block,但是我们如何确保p是一个指针而只是一个大一点的数,像0x11000,可能只是一个普通的数也有可能是指针,但是isPtr无法区分。(在java中,指针不是由用户管理的,因此他清楚的知道自己有哪一些指针)

2.如何确保p指向的位置是block的Payload区域以及如果p指向的是payload的中间我们如何获取该block的头部

我们可以看到一个指针指向一块block,他使用的只是其中的Payload区域,其他区域并不是用户在使用,他们是为了内存管理而生的。我们可以想象如果p指向的是payload中间的某一个地方,我们如何去获取他的头部,这是一个难题,因为我们不可能知道p偏离头部偏离了多少,无法获取头部我们也无法进行标记。

Solution:

如图,我们可以通过给每一个block建立平衡二叉树来解决这问题,每个block都增加left和right指针,left指向地址比自己小的block,right指向地址比自己大的block,Head存储着size,传入p在二叉树上进行搜索:

当addr<=p<=addr+size则标记该块。

参考:

1.[CSAPP笔记][第九章虚拟存储器][吐血1500行]

2.CSAPP