C++ values 和rvalues

C++左值和右值是一个不容易理解的概念,而且经常由于使用不正确而出现错误。
这里看到一个定义:
An lvalue (locator value) represents an object that occupies some identifiable location in memory (i.e. has an address).
rvalues are defined by exclusion, by saying that every expression is either an lvalue or an rvalue. Therefore, from the above definition of lvalue, an rvalue is an expression that does not represent an object occupying some identifiable location in memory.
 
左值变量与右值变量之间的转换
除了数组、不完整类型和函数,所有左值变量都能转换为右值。反之,则不行。但解引用操作符*是一个意外,能将右值变为左值,如*(p+1) = 10, p+1是右值,但*(p+1)是左值。 同时,&操作符也能将左值变为右值。

Sort List

问题描述:

Sort a linked list in O(n log n) time using constant space complexity.

解决代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *first = head, *second = head->next, *mid= NULL;
        while(second->next != NULL && second->next->next != NULL){       // find the mid position
            first = first->next;
            second = second->next->next;
        }
        mid = first->next;
        first->next = NULL;
        ListNode *left = sortList(head);
        ListNode *right = sortList(mid);
        return MergeSort(left, right);
    }
    ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }
};

有人采取自底向上的策略,给出了非递归解法,时间O(nlgn) 空间O(1):

/**
 * Merge sort use bottom-up policy,
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head || !(head->next)) return head;
        //get the linked list's length
        ListNode* cur = head;
        int length = 0;
        while(cur){
            length++;
            cur = cur->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode *left, *right, *tail;
        for(int step = 1; step < length; step <<= 1){
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;
                right = split(left, step);
                cur = split(right,step);
                tail = merge(left, right, tail);
            }
        }
        return dummy.next;
    }
private:
    /**
     * Divide the linked list into two lists,
     * while the first list contains first n ndoes
     * return the second list's head
     */
    ListNode* split(ListNode *head, int n){
        //if(!head) return NULL;
        for(int i = 1; head && i < n; i++) head = head->next;
        if(!head) return NULL;
        ListNode *second = head->next;
        head->next = NULL;
        return second;
    }
    /**
      * merge the two sorted linked list l1 and l2,
      * then append the merged sorted linked list to the node head
      * return the tail of the merged sorted linked list
     */
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode *cur = head;
        while(l1 && l2){
            if(l1->val > l2->val){
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
            else{
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
        }
        cur->next = (l1 ? l1 : l2);
        while(cur->next) cur = cur->next;
        return cur;
    }
};

https://leetcode.com/discuss/28594/bottom-recurring-with-space-complextity-time-complextity

单链表反转

题目:反转一个单链表

/**
 * 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) {
        ListNode *reverseHead = NULL;
        ListNode *node = head;
        ListNode *pre= NULL;
        while(node != NULL)
        {
            ListNode *next = node->next;
            if(next == NULL)
                reverseHead = node;
            node->next = pre;
            pre = node;
            node = next;
        }
        return reverseHead;
/** another version
        if(!pHead)
            return pHead;
        
        ListNode* curr = pHead;
        ListNode* prev = NULL;
        ListNode* next;
        while(curr->next){
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        curr->next = prev;
        return curr;
*/
    }
};

逆序输出单链表

void PrintReverseLink(ListNode *head)
{
    if(head->next != NULL){
       PrintReverseLink(head->next);
       printf("%d ",head->next->val);
    }
}

 

ListNode *reverse(ListNode *p, ListNode* &head)
{
   if(p == NULL || p->next == NULL)
   {
      head = p;
      return p;
    }
    else
    {
      ListNode *data = reverse(p->next, head);
      data->next = p;
      return data;
    }
}

 

谈谈持久链接——用暴走漫画理解HTTP

持久连接
    什么是持久连接?顾名思义,就是”持久”的连接。之前说到过,为了完成一个HTTP事务,服务器和客户端之间要建立一条TCP连接来传输报文,这个事务结束以后一般都会直接把它关闭,这是正常的模式。可是这样会造成网络使用效率的降低,为什么呢?有这么几点原因

  1. 每次建立连接的时候都要经过三次握手等必须的程序,如果我们拥有一条可以一直使用的连接的话,也就意味着我们只需要进行一次连接的建立,这就省去了每次建立连接的时间。
  2. 上一篇心得中提到过了,使用过的连接会比新建立的连接速度会快一些,这是由于TCP连接慢启动的特性,每次建立新的连接,当然不如已经被调教的很好的连接速度快咯。
  3.  每个连接对于服务器和客户端来说都是负担,能少开尽量少开,当然是在不影响功能和体验的前提下。

现在很多方案都会采用持久连接+新连接结合的方式,这种方式尽可能的减少了新建连接的浪费,同时当现有连接没有办法满足需求的时候,可以建立新连接满足需求,比较灵活。现有的持久连接类型有两种:HTTP/1.0+的keep-alive和HTTP/1.1的persistent.

  • keep-alive

   先来看来keep-alive,先上图:
     这个是百度首页的一个HTTP事务,可以看到有个首部connection:keep-alive,这个就是第一种持久连接了。下面来看下这个持久连接是怎么建立的:

这个就是请求的过程了:客户端先发出请求,以connection:keep-alive的形式传向服务器,如果服务器接受的请求的话响应中就会带有connection:keep- alive.
当使用了connection:keep-alive时,可以使用keep-alive首部传递一些关于持久连接的参数:timeout表示持续时间,max表示希望还在这条持久连接上传输多少个HTTP服务,但是这些都不是承诺值,也就是说随时都可以反悔
    接下来说说keep-alive持久连接需要注意的一些地方:

  1. 如果要是用持久连接,那么就一定要有正确的content-length这个描述主体长度的首部,因为持久连接会连续的传输HTTP事务,而判断连续的HTTP事 务之间的分界点就是靠content-length告诉的主体的长度了,如果错误或没有告诉主体的长度的话,那么就没办法知道这个事务在哪里结束了。
  2. 代理和网管必须再转发之前删除connection:keep-alive这个首部,这个涉及到哑代理问题,后面会说到。
  3. 因为持久连接可以随时关闭,所以一定要做好遇到当请求发出去响应还没回送回来的时候持久连接就断开的情况的准备,也就是有些时候可能要从新发送请求。

哑代理和聪明的代理

    这里先说明下哑代理和聪明的代理的区别:哑代理只是单纯的转发请求,并不能进行解析处理、维持持久连接等其他工作,而聪明的代理可以解析接收到的报文同时可以维持持久连接。
如上图,当客户端与服务器之间存在不解析直接转发的代理时,connection:keep-alive这个首部是直接转发给服务器的,服务器接收了这个请求之后,就会向客户端发送带有connection:keep-alive的响应,同样盲代理不会解析响应,直接将全部响应转发回客户端。因为客户端收到了这个首部,就认为建立持久连接已经成功了,但是中间的”笨代理“,并不知道这些事情,笨代理只有一种行为模式:在转发请求和回送服务器响应请求之后就认为这次事务结束了,等待连接断开,而这时由于connection:keep-alive首部已经发送到服务器和客户端,双方都认为持久连接已经建立完成,这样就变成了两边认为持久连接OK而中间的哑代理等待连接断开的情况,这种情况下如果客户端再一次在这条连接上发送请求,请求就会在亚代理处停止,因为哑代理已经在等待连接关闭。这种状态会导致浏览器一直处于挂起状态,直到客户端或服务器之中一个连接超时,关闭连接为止,一段美好的牵手就这么没了(哑代理就是把内容原封不动的转发到代理)。
为了避免这种情况,现代的代理是不会转发connection:keep-alive这个首部的。
为了防止这个问题,网景提出了一个方案,采用插入Proxy-connection的方式,上图:

来看看这个方案如何解决问题:

  1. 首先客户端发送Proxy-connection首部请求,这是一个非标准请求,也就是说即使服务器接收到这个首部也不知道他是干什么的,在服务器眼中它只知道客户端申请持久连接的首部为connection:keep-alive
  2. 哑代理的模式:报文来到了代理的位置,哑代理的话会直接转发请求不解析处理,则Proxy-connection这个首部直接被发给服务器,由于服务器不识别,所以直接忽略到这个首部,这样服务器在返回响应的时候便不会带有connection:keep-alive首部,当响应到达客户端的时候,客户端发现响应中没有connection:keep-alive首部,就认为服务器拒绝了持久连接的请求,也就是说客户端判断服务器是否接受持久连接请求仍是靠响应是否存在connection首部来进行的。
  3. 聪明的代理的模式:聪明的代理会对请求进行解析,发现有 Proxy-connection这个首部的时候,便会把这个首部替换成connection:keep-alive,由于服务器只能识别connection首部,当它发现有这个首部的时候,就知道客户端进行了持久连接请求,就在响应中添加connection首部,回送给客户端。当客户端收到带有connection首部的响应时,便认为持久连接建立成功,而正好中间的聪明的路由也可以维持持久连接,这样整条连接就处于客户端OK代理OK服务器OK的状态,可以继续使用该持久连接进行报文发送。

    从上面所说的,我觉得这个方案其实就是相当于对中间代理的类型进行了一次判断。
 但是这个方案只能解决中间只有一个代理的情况,如果聪明的任意一边还存在一个哑代理,那么仍会出现最开始的哑代理问题

  • persistent

    HTTP/1.1的持久连接默认是开启的,只有首部中包含connection:close,才会事务结束之后关闭连接。当然服务器和客户端仍可以随时关闭持久连接。
当发送了connection:close首部之后客户端就没有办法在那条连接上发送更多的请求了。当然根据持久连接的特性,一定要传输正确的content-length。
还有根据HTTP/1.1的特性,是不应该和HTTP/1.0客户端建立持久连接的。最后,一定要做好重发的准备。
 管道化连接
    HTTP/1.1允许在持久连接上使用管道,这样就不用等待前一个请求的响应,直接在管道上发送第二个请求,在高延迟下,提高性能。
管道化连接的限制:

  • 不是持久连接就不能使用管道。
  • 必须按照同样的发送顺序回送响应,因为报文没有标签,很可能就顺序就乱咯。
  • 因为可以随时关闭持久连接,所以要随时做好重发准备
  • 不应该使用管道化发送重复发送会有副作用的请求(如post,重复提交)。

就到这里了,画着好累。。。