源之居
0%

发表于 更新于 分类于

启程

配环境

vscode+remote-ssh+云服务器centos8开发

本想写2023年的新版lab，但是看了看要用g++20编译，试了试更新g++太难，放弃了，期间还删掉了g++，还好服务器有备份可以回滚。

推荐使用 https://kangyupl.gitee.io/cs144.github.io/ 网站镜像备份，g++8编译就可以。

代码也是采用 https://gitee.com/kangyupl/sponge git clone 下来后直接切换分支就可以写。

编译 make
测试 make check_lab0

lab0

中规中矩，热身实验。耗时1.5h左右。

实现 get_url函数,注意端口号部分写 http 代表服务类型就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//! Construct by resolving a hostname and servicename. 函数重载采用这个函数
    Address(const std::string &hostname, const std::string &service);


void get_URL(const string &host, const string &path) {
    // Your code here.

    TCPSocket mysock;
    mysock.connect(Address(host,"http")); 

    mysock.write("GET "+path+" HTTP/1.1\r\n");
    mysock.write("Host: "+host+"\r\n\r\n");

    mysock.shutdown(SHUT_WR);

    while(!mysock.eof()){// eof代表读取完毕 且发送端也停止发送
        auto rec_message=mysock.read();
        cout<<rec_message;
    }

    mysock.closed();

    return;

}

内存中的通讯，采取了list的写法。注意下eof() 函数，头文件注意定义变量，别定义少了。

就是一个可以读取和写入的有序字节流，先写入的先被读取到。实现这个类的一些方法。

1
2
3
4
5
6
7
8
9
10
private:
  // Your code here -- add private members as necessary.

  bool _error{};  //!< Flag indicating that the stream suffered an error.
  std::list<char> stream_content;
  const size_t capacity= 0;
  size_t stream_size=0;// 最后一个写入的字节的序号，其实没用，当初写多了就一直保留了
  bool flag_finish=0;
  size_t read_size=0;// 已经读取的长度
  size_t writen_size=0;// 已经写的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
ByteStream::ByteStream(const size_t mycapacity) : stream_content{}, capacity(mycapacity), stream_size(0) {}

size_t ByteStream::write(const string &data) {
    if(flag_finish || _error) return 0;
 
    size_t temp_size = writen_size;
    for (auto& temp : data) {
        if ((writen_size-read_size ) >= capacity)
            break;// list中的数据量满了 就退出
        stream_size++;
        writen_size++;
        stream_content.emplace_back(temp);
    }
    return (writen_size - temp_size);// 返回实际写入的数据长度
}

//! \param[in] len bytes will be copied from the output side of the buffer
string ByteStream::peek_output(const size_t len) const {
    if(_error) return nullptr;
    size_t temp_len = 0;
    string ans(len, '0');

    for (auto temp_char : stream_content) {
        if (temp_len == len)
            break;
        temp_len++;
        ans[temp_len - 1] = temp_char;// 因为实际内容的长度可能不够 所以还需要一个 temp_len
    }
    return ans.substr(0, temp_len);
}

//! \param[in] len bytes will be removed from the output side of the buffer
void ByteStream::pop_output(const size_t len) {
    if(_error) return ;
    size_t cur_size=buffer_size();
    for (size_t i = 0; i < len; i++) {
        if (cur_size<= 0)
            break;// 防止数据量并没有len那么多 
        cur_size--;
        stream_content.pop_front();
        read_size++;
    }

    return;
}

void ByteStream::end_input() {
    flag_finish = 1;
    return;
}

bool ByteStream::input_ended() const { return flag_finish; }

size_t ByteStream::buffer_size() const { return writen_size-read_size; }

bool ByteStream::buffer_empty() const { return writen_size-read_size==0 ; }

bool ByteStream::eof() const {
    return buffer_empty() && flag_finish;  // 数据读取完毕 并且 输入端停止输入
}

size_t ByteStream::bytes_written() const {
    return writen_size;
}

size_t ByteStream::bytes_read() const { return read_size; }

size_t ByteStream::remaining_capacity() const { return capacity - (writen_size-read_size); }

lab1

实现一个类，把无序可能重复到达的数据组合成有序的并且写入到_output中，_output就是lab0实现的Bytestream。耗时3.5h左右。

写之前可以先make测试一下，看看测试程序的样例，不然理解可能会有些偏差，我盯着样例看了一会才明白具体细节。

注意点如下

  1. 到达数据会重叠
  2. 当到达数据全部被接受到（根据传入参数eof判断），且全部有序后，且全部写入output后，需要更新output的结束信号状态。
  3. output的容量可能比StreamReassembler的小，不过这个lab中不用考虑这些…不知道为什么，考虑的话，当output的可用容量小于要写入的字节时候，你还要自己做个判断，并且定义一个新的变量。
  4. 按照道理，流重组器的数据写入顺序字节流后，流重组器的数据就可以删除了，不过这个lab没要求，我也懒得写，也不知道后面lab需不需要考虑。

网上一个参考说明如下，不过这个lab其实并不用考虑

LAB0的顺序字节流和LAB1的流重组器各有各的容量限制。流重组器把字节流写满后，只有当字节流腾出空后才能继续写，相当于字节流满时流重组器出口被“堵住”了。同样当流重组器容量满了后自身也无法被写入新数据，此时到来的新碎片只能被丢弃掉。

选取合适数据结构很重要，写之前模拟半天，一个idea是两个链表，太复杂pass了，一个idea是双端队列+无序set，一个idea是string+无序set。

需要删除流重组器的数据的话用deque更好一些，不过我写的时候没考虑，直接用了string。 到时候看看再重构吧。

写完lab1 做lab2的时候我才知道

lab1的担心是对的，确实需要删除已经写入有序字节流的元素，把lab2代码拉下来后重新测试发现lab1出错了，lab2新增了对lab1的测试，也就是测试有没有删掉已经写入顺序字节流的元素，所以fix bug采用了deque数据结构。

以下是最新代码

1
2
3
4
5
6
7
8
9
10
11
12
private:
  // Your code here -- add private members as necessary.

  ByteStream _output;  //!< The reassembled in-order byte stream
  size_t _capacity;    //!< The maximum number of bytes
  std::deque<char> all_content_str;
  std::unordered_set<int> hash_str_unorderset={};
  size_t size_char_inorder=0; // 所有有序的数量，包括已经写入被pop出去的
  size_t size_char_all=0; //  // 所有数据的数量，包括已经写入被pop出去的
  size_t size_char_writen=0;// 写入到有序字节流中的数量
  size_t start_index=0;// deque中第一个字符的在字节流中的下标,其实和size_char_writen一样
  bool eof_flag=false;

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
StreamReassembler::StreamReassembler(const size_t capacity)
    : _output(capacity), 
    _capacity(capacity), 
    all_content_str(capacity, '0') 
    {}

//! \details This function accepts a substring (aka a segment) of bytes,
//! possibly out-of-order, from the logical stream, and assembles any newly
//! contiguous substrings and writes them into the output stream in order.
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    size_t data_length = data.size();
    
    size_t up_length = min(data_length , _capacity+start_index-index); // 实际可以写入的长度
    
    for (size_t i = 0; i < up_length; i++) {
        if (hash_str_unorderset.find(i+index) == hash_str_unorderset.end()) {
            hash_str_unorderset.emplace(i+index);
            all_content_str.at(index-start_index+i) = data[i];
            size_char_all++;
        }
    }// 将收到的data写入缓冲区，同时更新hash表（hash表是判断对应序号的data是否被写入）

    
    for (size_t i = size_char_inorder-start_index; i < _capacity; i++) {
        if (hash_str_unorderset.find(i+start_index) == hash_str_unorderset.end())
            break;// hash中找不到，也就是该位置对应的data未被写入

        size_char_inorder++;
    } // 寻找连续序列（也就是重组好的序列），直到出现断层
   

    size_t size_writable=min(_output.remaining_capacity(),size_char_inorder-size_char_writen);
    // 防止output内的缓冲长度不够，所以取最小值，同时还要定义一个size_char_written记录已经写入的数据

    string temp(size_writable,'0');
    for(size_t i=0;i<size_writable;i++) temp[i]=all_content_str.at(i);

    _output.write(temp);

    for(size_t i=0;i<size_writable;i++){
        all_content_str.pop_front();
        all_content_str.emplace_back('0'); // pop后还要在deque尾部添加，保持容量不变。
    };

    size_char_writen+=size_writable; // 更新写入的长度
    start_index=size_char_writen;

    if(eof) eof_flag=true;

    if(eof_flag && this->empty()){
        _output.end_input();
    }// 接受到全部data后且全部写入到output后，output就可以更新结束信号


    return;
}

size_t StreamReassembler::unassembled_bytes() const {  return size_char_all - size_char_inorder; }

bool StreamReassembler::empty() const { return size_char_all == size_char_inorder && size_char_inorder==size_char_writen; }
// 不仅全部要有序，所有的还必须被写入output ,可以直接写出 size_char_all==size_char_written

lab2 花费比较多，8h左右。

tcp receiver

part1

对我挺折磨的，主要是看不懂文档在说啥…，真正理解还是自己测试的时候，看测试代码才知道究竟让干啥，一些细节究竟是什么。

注释比较全面了，不过我的逻辑可能不太好理解，有问题可以给我提issue。

cout是debug时候看的，留着可能下个lab还要用，悲，测试样例不全就是这样的，不能相信之前自己写的lab。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    uint64_t t_num = UINT32_MAX;
    t_num++;

    n = n % (t_num);  // 先回退到第一个循环。
    n += isn.raw_value();

    n = n % (t_num);

    return WrappingInt32(static_cast<uint32_t>(n));
}

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    // n的绝对序列和checkpoint的差的绝对值一定小于(2^32)-1；
    cout << " n  isn  check  " << n << " " << isn << "  " << checkpoint << endl;
    WrappingInt32 check_in_wrap32 = wrap(checkpoint, isn);
    cout << " check in warp32 " << check_in_wrap32 << " " << endl;
    uint64_t ans = 0;
    uint64_t gap_1 = 0;  // 记录n的绝对序列比checkpoint大的情况，当然我们并不知道究竟是大还是小，比较取得最合适的
    uint64_t gap_2 = 0;  // 记录n的绝对序列比checkpoint小的情况
    uint64_t n_raw_value = n.raw_value();
    uint64_t check_in_wrap32_raw_value = check_in_wrap32.raw_value();

    // gap均为正
    // 假设n的绝对序列比check大的情况，比check大的时候，有可能没有多一个循环，有可能多了一个循环
    // 比如 checkpoint的相对序列为 3，n的相对序列可能为1（此时n的绝对序列比 check大了 2^32-2） 也可能为 10，但每种情况
    // n的绝对序列都要比checkpoint大
    if (n_raw_value < check_in_wrap32_raw_value) {
        gap_1 =
            1 + n_raw_value + (uint64_t)UINT32_MAX -
            check_in_wrap32_raw_value;  // 这里要加个一，因为跳入一个新的循环，要加1，想不通自己设个小点的数字，自己算一下

    } else
        gap_1 = n_raw_value - check_in_wrap32_raw_value;

    if (n_raw_value > check_in_wrap32_raw_value) {
        gap_2 = 1 + (uint64_t)UINT32_MAX + check_in_wrap32_raw_value - n_raw_value;  // 这里要加个一
    } else
        gap_2 = check_in_wrap32_raw_value - n_raw_value;  //  假设n的绝对序列比check小的情况

    if (gap_1 < gap_2) {
        ans = checkpoint + gap_1;
    }  // 第一种情况更接近checkpoint
    else if (checkpoint >= gap_2)
        ans = checkpoint - gap_2;  // 第二种情况更接近checkpoint
    else
        ans = checkpoint + gap_1;  // 虽然第二种情况更接近checkpoint，也就是n的绝对序列比checkpoint小，但是此时
                                   // checkpoint<gap_2,相减会溢出(而 两者差距不可能那么大)，因此其实是第一种情况

    // 上面三个if else 判断条件的 等号 要不要加 也要自己琢磨思考一下，不然会出错。
    return ans;
}

part2

认真看文档，先理解让干啥再写，我漏看了后面的详细介绍，懵逼了半天，不知道从何下手，然后又看文档才发现后面有详细的介绍。

逻辑不难，本质上就是维护一个滑动窗口，然后确认什么时候接收数据，什么时候不接受。需要注意的是，这里的窗口大小被有序字节流和重组器的共同限制，这下知道我怎么发现lab0的bug了吧。需要注意的细节有点多，慢慢对着测试代码改吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private:
    //! Our data structure for re-assembling bytes.
    StreamReassembler _reassembler;

    //! The maximum number of bytes we'll store.
    size_t _capacity;
    size_t seg_length = 0;  //// 当前TCPSegment的length
    bool seg_syn_flag = false;
    bool seg_fin_flag = false;
    uint64_t checkpoint{0};  // 检查号
    uint32_t offset_syn = 0;  // 如果当前段是syn的话，因为需要转换stream index 所以需要＋1，syn是0 但是在stream
                              // index中不占位置，syn的下一位才是0
                              
    WrappingInt32 syn_num{0};  // 整个字节流的初始序列号 也就是isn
    WrappingInt32 seq_num{0};  // 当前TCPSegment的序列号

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
bool TCPReceiver::segment_received(const TCPSegment &seg) {
    if (seg.header().syn) {
        if (seg_syn_flag)
            return false;  // second SYN is rejected
        offset_syn = 1;
        seg_syn_flag = true;
        syn_num = seg.header().seqno;
        checkpoint = static_cast<uint64_t>(0);  // 遇到syn的时候，设置初始序列号 和检查位,此时检查位应该为 0，因为此刻还没有开始转换，因此就选择0
    }

    if (!seg_syn_flag)
        return false;  // 没有开始的话就直接丢弃

    if (seg.header().fin && seg_fin_flag)
        return false;  // second FIN is rejected
    if (seg.header().fin)
        seg_fin_flag = true;

   
    WrappingInt32 temp_seq_num{seg.header().seqno};
    uint64_t temp_cur_index = unwrap(temp_seq_num + offset_syn, syn_num, checkpoint);  // 该segment的绝对序列号
    cout<< " 收到的数据段的绝对序列号 "<<temp_cur_index<<endl;

   
    //_reassembler.ack_n()+1 期望收到的下一个数据的绝对序列号
    if (_reassembler.ack_n() + 1 + _reassembler.empty_length() <= temp_cur_index){
        return false;  // 当前段的序列超过窗口范围 丢弃
        cout<<" 当前段的序列超过窗口范围 丢弃 "<<endl;
    }

    seg_length = seg.length_in_sequence_space()-seg.header().syn-seg.header().fin;

    
   

    if(seg_length==0){
        if(wrap(temp_cur_index, syn_num)-wrap(_reassembler.ack_n() + 1, syn_num) <0){
                return false;
            }// 重复空报文
    }
    else if (wrap(temp_cur_index, syn_num) + static_cast<uint32_t>(seg_length-1+seg.header().fin)
            -wrap(_reassembler.ack_n() + 1, syn_num) <0){
        
        cout<<" 判断接受到的 重叠且这个数据段没有新的信息 直接丢弃 "<<endl;
        return false;  // 判断接受到的 重叠且这个数据段没有新的信息 直接丢弃，fin报文也算数据 因此也要计算

    }

    seq_num = seg.header().seqno;
    uint64_t cur_index = unwrap(seq_num + offset_syn, syn_num, checkpoint);  
        // 绝对序列号,syn不占流里面的下标位置 因此有syn的时候 算的是syn之后一位的位置。

    checkpoint = cur_index + seg_length - 1;  // 最近确认的绝对序列号

    cout<<" 进入重组 "<<cur_index<<endl;
    _reassembler.push_substring(seg.payload().copy(), cur_index - 1, seg_fin_flag);

   
    offset_syn = 0;
    return true;
}

optional<WrappingInt32> TCPReceiver::ackno() const {
    if (seg_syn_flag == false)
        return nullopt;
    uint64_t n = _reassembler.ack_n() + 1;  // 期望收到的绝对序列号，ack_n返回的是stream_index
    cout<<" 期望收到的绝对序列号n "<<n<<endl;
    return wrap(n, syn_num);
}

size_t TCPReceiver::window_size() const { return _reassembler.empty_length(); }

在lab1中的流重组器中加了两个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    //   可以被写入的数据长度,也就是有序字节流中还剩下的空间 和 重组器中剩下的空间减去已经有序但还未进入重组器的长度  的较小值。
    uint64_t empty_length() const;
    
    // 返回下一个期望收到的字符的stream index
    uint64_t ack_n() const;

    uint64_t StreamReassembler::ack_n() const {
    if (eof_flag)
        return size_char_inorder + 1;// ＋1是因为fin也被看做一个字节 但是不会被写进去
    return size_char_inorder;  // 返回下一个期望收到的字符的stream index
}

    uint64_t StreamReassembler::empty_length() const {
    return min(_output.remaining_capacity()-(size_char_inorder-size_char_writen), _capacity - (size_char_inorder - size_char_writen));
}

中期总结

lab0实现了内存中的顺序读取结构，也就是bytestream。

lab1在此基础上实现了重组器，把不按照顺序到达的数据重新组装起来，流重组器控制传入数据读取多少，需要读取哪些数据，下一个需要读取的数据序号（ack的序号）。

lab2在两者基础上维护了一个滑动窗口，根据窗口大小，还有数据的序号关系，各种特殊情况怎么处理，选择是否接受数据，把数据传入流重组器（数据接收并不一定被全部接收，可能被流重组器部分接收，不过这不需要管，只要有数据需要被接收就传入流重组器，receiver不需要考虑接收多少，这是流重组器需要处理的）。

lab3

实现tcp sender

根据远方接收者的窗口内可接收新数据的长度 以及 我们可以发送的数据长度 发送tcp segment给receiver。
我们要发送的数据都在bytestream里面，也就是有序字节流中。

当然也要实现最开始发送syn空报文，结束发送fin报文的功能。

重传机制：设置重传计时器和超时时间，收到新的报文ack就重新启动重传计时器和超时时间，超时就需要重传最小的未被确认的报文。

未被确认的报文都需要进行缓存，确认后再pop出去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private:
  //! our initial sequence number, the number for our SYN.
  WrappingInt32 _isn;

  //! outbound queue of segments that the TCPSender wants sent，这个队列我们并不能控制 
  std::queue<TCPSegment> _segments_out{};
 
  // 等待被确认的，因为可能需要重传 所以需要缓存下，
  std::queue<TCPSegment> _segments_wait{};

  //! retransmission timer for the connection  rto的初始值
  unsigned int _initial_retransmission_timeout;

  //! outgoing stream of bytes that have not yet been sent
  ByteStream _stream;

  //! the (absolute) sequence number for the next byte to be sent
  uint64_t _next_seqno{0};

  bool syn_sent=false;// 是否发送最开始的syn
  bool fin_sent=false;// 是否发送结束的fin
  size_t remote_window_size=1;// 远方接收者的窗口，限制了我们发送数据的大小

  size_t cur_all_time=0;// 当前已经过去的时间
  size_t next_retran_time=0;// 下次需要重传的时间，也就是说 调用tick时候 假如当前时间超过了next_retran_time 就代表超时
  bool tcp_timer_running=false; // 计时器是否正在运行
  size_t cur_rto=0;// 当前的rto
  size_t continuous_retran_num=0;// 连续重传的数量
  uint64_t cur_bytes_length_in_flight=0;// 未被确认的序列号长度 syn和fin也算一个长度'

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
TCPSender::TCPSender(const size_t capacity, const uint16_t retx_timeout, const std::optional<WrappingInt32> fixed_isn)
    : _isn(fixed_isn.value_or(WrappingInt32{random_device()()}))
    , _initial_retransmission_timeout{retx_timeout}
    , _stream(capacity)
    , syn_sent{false} {}

uint64_t TCPSender::bytes_in_flight() const { return cur_bytes_length_in_flight; }

void TCPSender::fill_window() {

    if(fin_sent) return; 

    if (syn_sent == false) {
        TCPSegment syn_seg;
        syn_seg.header().syn = true;
        syn_seg.header().seqno = _isn;
        _next_seqno=1;  // 因为最开始的syn报文长度为1，所以＋1就ok了
        _segments_out.push(syn_seg);
        _segments_wait.push(syn_seg);
        syn_sent = true;

        if (tcp_timer_running==false) {
            tcp_timer_running = true;
            cur_rto = _initial_retransmission_timeout;
            next_retran_time = cur_all_time + cur_rto;
            continuous_retran_num = 0;
        }

        cur_bytes_length_in_flight = static_cast<uint64_t>(syn_seg.length_in_sequence_space());

        return;
    }

    size_t cur_send_size = min(_stream.buffer_size(), (remote_window_size - static_cast<size_t>(cur_bytes_length_in_flight)));

    size_t temp_i = 1450;  // 用temp_i 主要是为了使用min函数 不然类型不匹配
    size_t seg_num = cur_send_size / temp_i;
    size_t end_length=cur_send_size-seg_num*temp_i;
    if (cur_send_size > 0)
        seg_num++;// 当前能够发送的报文数量
    
   
    // 发送fin报文
    if(cur_bytes_length_in_flight<remote_window_size && _stream.eof()){// 结束输入 并且要保证接收窗口有位置接受fin报文
        fin_sent = true;

        TCPSegment fin_seg;
        fin_seg.header().fin = true;
        fin_seg.header().seqno = wrap(_next_seqno, _isn);
        _next_seqno += static_cast<uint64_t>(fin_seg.length_in_sequence_space());
        _segments_out.push(fin_seg);
        _segments_wait.push(fin_seg);

        if (tcp_timer_running==false) {
            tcp_timer_running = true;
            cur_rto = _initial_retransmission_timeout;
            next_retran_time = cur_all_time + cur_rto;
            continuous_retran_num = 0;
        }
     
        cur_bytes_length_in_flight += static_cast<uint64_t>(fin_seg.length_in_sequence_space());
    
        return;
    }


    for (size_t i = 0; i < seg_num; i++) {

        if (tcp_timer_running == false) {
            tcp_timer_running = true;
            cur_rto = _initial_retransmission_timeout;
            next_retran_time = cur_all_time + cur_rto;
            continuous_retran_num = 0;
        }

        string temp_seg_content;

        if(i==seg_num-1) temp_seg_content = _stream.peek_output(end_length);
        else temp_seg_content = _stream.peek_output(temp_i);
        

        _stream.pop_output(min(temp_i, cur_send_size));  // 用temp_i 主要是为了使用min函数 不然类型不匹配
        TCPSegment cur_seg;

        cur_seg.payload() = Buffer(std::move(temp_seg_content));  // 发送的segment的内容
        cur_seg.header().seqno = wrap(_next_seqno, _isn);         // 绝对序列号转换为相对序列号

        if (i == seg_num - 1 && _stream.eof())
            cur_seg.header().fin = true;  // 判断是否结束 fin标志位设置，只有最后输出的时候可能是fin报文

        _next_seqno += static_cast<uint64_t>(cur_seg.length_in_sequence_space());  // 绝对序列号增加

        _segments_out.push(cur_seg);
        _segments_wait.push(cur_seg);

        cur_bytes_length_in_flight += static_cast<uint64_t>(cur_seg.length_in_sequence_space());

    }

    return;
}

//! \param ackno The remote receiver's ackno (acknowledgment number)
//! \param window_size The remote receiver's advertised window size
//! \returns `false` if the ackno appears invalid (acknowledges something the TCPSender hasn't sent yet)
bool TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) {
    if (ackno - next_seqno() > 0) {
        return false;  // 确认的是还没有发送的数据，说明出错了
    }

    size_t old_rece_free_length = remote_window_size - static_cast<size_t>(cur_bytes_length_in_flight);
    // 我们认为的远方接收者的 可以接收我们发送的新数据的剩余空间（旧的数据远方接收者收到但未给我们确认的话，这是重传机制需要搞定的事情，这里不需要管）

    while (!_segments_wait.empty()) {
        
        if (_segments_wait.front().header().seqno - ackno < 0) {  // 按照道理这里还应该加上数据长度，但tcp的segment不可能被分开（可能吗，我现在感觉不可能），所以不加也没问题吧

            cur_rto = _initial_retransmission_timeout;
            continuous_retran_num = 0;
            tcp_timer_running = true;
            next_retran_time = cur_all_time + cur_rto;
            // 不为空就重启定时器，设置好重传时间 rto 重传次数

            cur_bytes_length_in_flight -= static_cast<uint64_t>(_segments_wait.front().length_in_sequence_space());

            _segments_wait.pop();
        } else {
            break;
        }
        
    }  // 移除已经被确认的 segment

    if (_segments_wait.empty())  tcp_timer_running = false;  // 全部确认 计时器关闭

    remote_window_size = static_cast<size_t>(window_size);  // 更新窗口

    size_t cur_rece_free_length=remote_window_size-static_cast<size_t>(cur_bytes_length_in_flight);

    if (cur_rece_free_length>old_rece_free_length && _stream.buffer_size() > 0) {
        fill_window();
    }  // rece有空间可以接收 且 有数据可以发送 就继续发送

    return true;
}

//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void TCPSender::tick(const size_t ms_since_last_tick) {
    cur_all_time += ms_since_last_tick;

    mytcp_timer();

    return;
}

void TCPSender::mytcp_timer() {
    if (tcp_timer_running == false)
        return;  // 实际上tick和计时器是两个东西 tick是用来获取时间的 计时器是计时器
                 // 不过计时器基于tick，因此写在tick里面也ok。

    if (cur_all_time >= next_retran_time && !_segments_wait.empty()) {
        _segments_out.push(_segments_wait.front());
        continuous_retran_num++;
        cur_rto *= 2;
        next_retran_time = cur_all_time + cur_rto;
    }

    return;
}

unsigned int TCPSender::consecutive_retransmissions() const { return continuous_retran_num; }

void TCPSender::send_empty_segment() {
    TCPSegment cur_seg;
    cur_seg.header().seqno = wrap(_next_seqno, _isn);  // 绝对序列号转换为相对序列号
    _segments_out.push(cur_seg);

    return;
}

bool& TCPSender::sender_syn_sent  () {
    return syn_sent;
}

lab4

tcp connection

把前面的4个lab内容结合起来，实现一个完整的tcp自动机。

需要处理的细节很多很多很多…….

主要就四个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
    void connect(); // 初始连接 发送syn报文

    size_t write(const std::string &data); // 把需要被发送的数据写入有序字节流等待被发送 同时让sender类发送这些数据（假如根据窗口大小判断 能发送的话）

    void tick(const size_t ms_since_last_tick);// 这个函数由操作系统调用，获取过去的时间，超时就进行重传操作，重传次数太多会发送rst报文结束连接。

    void segment_received(const TCPSegment &seg); // 接收到了新的报文 就调用receiver更新信息，同时调用sender发送ack报文和数据。同时也要处理一些异常情况


using namespace std;

size_t TCPConnection::remaining_outbound_capacity() const { 
    return _sender.stream_in().remaining_capacity();
 }

size_t TCPConnection::bytes_in_flight() const { 
    return _sender.bytes_in_flight();
 }

size_t TCPConnection::unassembled_bytes() const { 
    return _receiver.unassembled_bytes();
 }

size_t TCPConnection::time_since_last_segment_received() const { 
    return cur_time_since_last_segment_received;
 }

void TCPConnection::segment_received(const TCPSegment &seg) { 
    if(!_sender.sender_syn_sent() && !seg.header().syn && !recv_start) return; // 如果我们没发送syn 对面发送的这个数据也不是syn 并且也没有启动（没这个标记的话 对面发送syn 之后的数据就没法接收了） 那就拒绝接收数据
    recv_start=true;// 开始启动
    if(rst_receved) return;

    if(seg.header().rst){
        _receiver.stream_out().set_error();
        _sender.stream_in().set_error();
        _linger_after_streams_finish=false;
        rst_receved=true;
        active_tcp=false;
    }

    cur_time_since_last_segment_received=0;// 重设间隔时间

    _receiver.segment_received(seg);
    _sender.ack_received(seg.header().ackno, seg.header().win); // 数据传输给接收类，发送类发送对应数据

    if (_receiver.stream_out().input_ended() && !_sender.stream_in().eof()) {
        // 如果入站流在TCPConnection到达其出站流的EOF之前结束，则需要将此变量设置为false
        _linger_after_streams_finish = false;
        // 被动关闭 对面fin之后 我们发送ack 然后接收类就处理数据发送完毕后 会发送fin给对方 后半部分的逻辑和主动关闭差不多
    }

    
    if (_sender.segments_out().empty()) {// 没有数据可以发送时候 收到了数据包 可能是三次握手的syn 四次挥手的fin 和 ack，这时候发送类不会不会产生包来发送
        //需要产生一个空段进行ack
        if (_receiver.stream_out().input_ended() && !seg.header().fin) {
            // 已经关闭了 被动或者主动关闭 这时候收到不是fin的包就不产生空包回应
    
        }
        /*else if(seg.length_in_sequence_space() == 0 && 
        _sender.next_seqno_absolute() > _sender.bytes_in_flight() 
        && !_sender.stream_in().eof()){
            // 连接已经建立时候 需要回复空包
            _sender.send_empty_segment(); // 发送空包进行ack
        }*/
        else if (seg.length_in_sequence_space() == 0 ) {
            //  连接未建立时候就不发送空包回复
            // 不直接return是因为 可能是有其他数据需要发送
           // cout<<" 没有建立连接的时候就不发送空包回复 "<<endl;
        } else {
           // cout<<" 发送空包 "<<endl;
            _sender.send_empty_segment(); // 发送空包进行ack
        }
    }
    

    send_segments();

 }

bool TCPConnection::active() const { 
    
    if(_sender.stream_in().eof() && _sender.bytes_in_flight() == 0 && _receiver.stream_out().input_ended() && (cur_time_since_last_segment_received >= _cfg.rt_timeout * 10 || _linger_after_streams_finish==false)) 
    return false; // 数据全部接收处理 发送 被确认 结束 且 time_wait时间结束(或者是被动关闭 不需要time_wait)

   
    if (rst_receved || !active_tcp) return false;
    

    return true;
 }

size_t TCPConnection::write(const string &data) {
    size_t writen_num=_sender.stream_in().write(data);
    _sender.fill_window();
    send_segments();
    return writen_num;
}

//! \param[in] ms_since_last_tick number of milliseconds since the last call to this method
void TCPConnection::tick(const size_t ms_since_last_tick) { 
    _sender.tick(ms_since_last_tick);
    cur_time_since_last_segment_received+=ms_since_last_tick;
    //cout<<" 间隔时间 "<<cur_time_since_last_segment_received<<" "<<endl;
    send_segments();// 时间流逝后 发送类可能会有新的数据需要发送 因此需要send_segments()

    if (_time_wait && cur_time_since_last_segment_received >= _cfg.rt_timeout * 10) {
        // 关闭连接
        //cout<<" 关闭连接 "<<endl;
        _time_wait = false;
        recv_start=false;
        active_tcp=false;
    }

    if (_sender.consecutive_retransmissions() > _cfg.MAX_RETX_ATTEMPTS) {
        // 重传次数太多 就进入rst状态
        _sender.stream_in().set_error();
        _receiver.stream_out().set_error();
        _linger_after_streams_finish = false;
        while (!_sender.segments_out().empty()) {
            // pop出数据
            _sender.segments_out().pop();
        }
        _sender.send_empty_segment();
        TCPSegment& seg = _sender.segments_out().front();
        seg.header().rst = true;
        active_tcp=false;
        rst_receved=false;
        send_segments();
    }
    

    return;
 }

void TCPConnection::end_input_stream() {
    _sender.stream_in().end_input(); //结束输出流，因此先关闭有序字节的写端
    _sender.fill_window();// 然后输出剩余的所有 未被发送的 数据
    send_segments();
    return;
}

void TCPConnection::connect() {
    if(!_sender.sender_syn_sent()){
        _sender.fill_window();
        TCPSegment& syn_seg = _sender.segments_out().front();
        syn_seg.header().win = min(_receiver.window_size(), static_cast<size_t>(UINT16_MAX));// uint16_t win = 0;  window size ,防止传递窗口过大
        _segments_out.push(syn_seg);
        _sender.segments_out().pop();
    }
    return;
}

void TCPConnection::send_segments() {
    if (!active_tcp || rst_receved) return;
    while (!_sender.segments_out().empty()) {
        TCPSegment& seg = _sender.segments_out().front();
        if (_receiver.ackno().has_value()) {
            seg.header().ack = true;
            seg.header().ackno = _receiver.ackno().value();
            //cout<< " 发送报文 设置ack "<<seg.header().ackno<<endl;
        }// 设置ack
        seg.header().win = min(_receiver.window_size(),static_cast<size_t>(UINT16_MAX));
        _segments_out.push(seg);
        _sender.segments_out().pop();
        //if(seg.header().fin) cout<<" 发送了fin 报文 "<<endl;
    }

    if (_sender.stream_in().eof() && _sender.bytes_in_flight() == 0 && _receiver.stream_out().input_ended()) {
        if (_linger_after_streams_finish) {// 接收类接收完毕 发送类发送完毕且发送的包也全部被确认 那就主动关闭
            _time_wait = true;
           // cout<<" 进入time_wait "<<endl;
        }
    }

    return;
}

TCPConnection::~TCPConnection() {
    try {
        if (active()) {
            //cerr << "Warning: Unclean shutdown of TCPConnection\n";
            _sender.stream_in().set_error();
            _receiver.stream_out().set_error();
            rst_receved=true;
            active_tcp=false;
            _linger_after_streams_finish = false;
            while (!_sender.segments_out().empty()) {
                // pop all segments
                _sender.segments_out().pop();
            }
            _sender.send_empty_segment();
            TCPSegment& seg = _sender.segments_out().front();
            seg.header().rst = true;
            send_segments();
            // Your code here: need to send a RST segment to the peer
        }
    } catch (const exception &e) {
        //std::cerr << "Exception destructing TCP FSM: " << e.what() << std::endl;
    }
}




优化

用官方提供的sponge/libsponge/util/buffer.cc中的 BufferList类来作为ByteStream的容器，使得原来基于内存拷贝的存储方法变为基于内存所有权转移。

用c++的 std::move assign 右值引用等新特性对 ByteStream进行改造。

发表于 分类于

忙

今天周一，课表上也只有两次一共4小节课程，按道理来说今天并没有多么忙，只是，生活不讲道理。

七点多起来之后，迷迷糊糊上完热统早八，十点多回到宿舍，写完三道算法题后已经将近十二点，吃完饭回来简单整理了一下思路，回复了一些必要的消息+看了看今日to do后又到了计算物理的签到时间。索性翘掉了课程，网上扫码签到一气呵成，然后午睡。

入睡很快，只是做的梦显得我压力很大的样子，梦中大概是又多了一些dll，整个人有些烦闷，睡觉过程中能感觉到自己有几个翻身的大动作。
醒来后查看消息，确实，又多了个ddl。

原子物理刚好出分，平均分略高，虽不如热统期中分数那么高，但也还可以，毕竟考试时候看见题目的我过于懵逼，一时间不知道自己是在学原子物理还是在学数学分析，怎么那么多定理证明题啊。

忙，会有结果的。

发表于 更新于 分类于

在学习初期就对与头文件和链接有些迷茫，今天简单谈谈这些事情。

从源代码到可执行文件

使用g++/gcc 工作流程如下
流程图.png

预处理：宏的展开，头文件展开，条件编译，去除注释等操作。

编译和汇编就不再叙述

链接：将目标代码中用到的所有相关的代码链接在一起，比如各种库函数和自己定义的各种函数。

预处理和链接

初学的时候，我迷惑的点在于，既然预处理已经展开头文件，那么链接又在链接什么？直到自己完成了lept_json这个完整的项目之后，才对这个问题有了更加清晰的认识。

首先了解一下gcc/g++ 的用法
image56afcdcda47539c8.md.png

image9eade6b095c77371.md.png

-o 也可以用来指定生成的文件的名称，否则会为默认文件名。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
---test.cpp---
#include<stdio.h>
#include<iostream>
#include "head_file1.h"
int main()
{   
    int t1=1;
    fun(t1);
    std::cout<<"this is test"<<std::endl;
    return 0;
}

---head_file1.h---
#include<stdio.h>
#include<iostream>

void fun(int t1);

---head_file1.cpp---
#include<stdio.h>
#include<iostream>

void fun(int t1){
    std::cout<<t1<<std::endl;
    return;
}

g++生成可执行文件的命令如下

1
2
3
g++ -c test.cpp -o test.o
g++ -c head_file1.cpp -o head_file1.o
g++ test.o head_file1.o -o test

或者直接

1
g++ test.cpp head_file1.cpp -o test // 文件的先后顺序不影响正确性

在实际开发过程中，良好的习惯是将函数的声明和定义分开，声明写在 xxx.h，定义写在 xxx.cpp。例子中 fun() 的定义和声明就是分开的

预处理就是将头文件展开，也就是将head_file1.h 中的 fun函数声明 在 test.cpp 中展开。

预处理过后 test.cpp中有了fun函数的声明，在接下来的编译过程中，它是符合规范的，即便现在编译器并不知道fun函数的定义。

链接过程中，链接器看到fun函数的声明，会去找fun函数的定义，那么怎么找到fun函数的定义呢？

我们将fun函数定义在了 head_file1.cpp中，因此就需要将 head_file1.cpp的目标代码(head_file1.o) 和test.cpp的目标代码(test.o) 链接起来生成 可执行文件

在第一种方法中

1
2
3
g++ -c test.cpp -o test.o // 生成目标代码 test.o  该文件中含有fun函数的声明但并没有定义
g++ -c head_file1.cpp -o head_file1.o // 生成目标代码 head_file.o
g++ test.o head_file1.o -o test // 两个文件链接在一起，此时就有了fun函数的具体实现
1
g++ test.cpp head_file1.cpp -o test // 两个文件一起处理，作用和第一种方法是一致的

一些问题

1

也许有人会想着先处理头文件对应的head_file1.cpp 然后处理 test.cpp

1
g++ head_file1.cpp  -o test

这样是错误的，因为head_file1.cpp 中并没有main()函数，因此链接会出现错误，所以我们只能生成目标代码，也就是使用 -c 这个命令，停留在链接之前，然后和test.o 一起链接处理，test.o中是有main()函数的哦。

2

linux中文件的后缀其实并没用，我们只是习惯 .o .s .cpp 这些；

head_file1.cpp 并不一定要和 head_file1.h 的名字一样，只是这样更加规范一些，g++是不会在乎这些名字的，因为 .h文件 是在预处理阶段展开的， 对应的 .cpp 文件是在链接阶段和test.o 链接在一起的，链接器并不是根据名字找到头文件对应的.cpp后缀的源代码的(当然，链接时候已经变成了 .o 后缀的目标代码)。

3

三个文件都引用了标准库，但并没有重复定义的问题，为什么？

第一，我们可以使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//条件编译
     #define        //  宏定义 
     #undef         //  取消宏 
     #include       //  文本包含 
     #ifdef         //  如果宏被定义就进行编译 
     #if defined    //  与ifdefine的区别在于可以可以组成复杂的判别条件
     #ifndef        //  如果宏未被定义就进行编译 
     #if !defined   //  与if !define的区别在于可以可以组成复杂的判别条件
     #endif         //  结束编译块的控制 
     #if   defined        //  表达式非零就对代码进行编译 
     #else          //  作为其他预处理的剩余选项进行编译 
     #elif          //  这是一种#else和#if的组合选项 
     #elif defined    //  与ifdefine的区别在于可以可以组成复杂的判别条件
	 #elif !defined    //  与ifdefine的区别在于可以可以组成复杂的判别条件
//编译指令
     #line          //  改变当前的行数和文件名称 
     #error         //  输出一个错误信息 
     #pragma        //  为编译程序提供非常规的控制流信息，可跟once，message等许多参数。

标准库中都含有条件编译指令
这些指令来避免重复定义(也能避免重复声明，但是重复声明只是会增加代码体积而已)，但是请注意条件编译指令是在预处理阶段进行的，也就是说

这里针对的都是在一个.cpp文件中避免头文件重复引入。如果一个工程有多个”.cpp”文件，由于编译器对每个.cpp文件是分开处理的，只在最后进行链接。在这种情况下，如果有多个.c文件都直接或间接引入了某个头文件，这时无法避开的。

我们的 head_file1.h 和 test.cpp 都引用库函数，但是在预处理阶段就已经处理掉了，只会引用一次。但是这两个文件(test.cpp head_file1.cpp)都有标准库啊，链接时候怎么没出错呢？

这就是定义和声明分开的好处，我们引用的头文件是标准库各种函数的声明，而不是定义，而重复声明并没关系(当然为了节省代码体积，减少内存开销，最好能不用头文件就不用，不要一股脑把可能用到的库函数头文件全部写上)，在链接的时候，库函数对应的 .o 文件会和我们的目标代码链接, 链接器虽然看到了那么多头文件库函数声明，但是对应的 库函数 .o 代码，链接器只会链接一次，避免出现重复定义错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
---test.cpp---
#include<stdio.h>
#include<iostream>
#include "head_file1.h"
int main()
{   
    int t1=1;
    fun(t1);
    std::cout<<"this is test"<<std::endl;
    return 0;
}

---head_file1.h---

void fun(int t1); // 头文件可以全部删掉，并没有用到，即便不删，预处理阶段也会被忽略掉

---head_file1.cpp---
#include<stdio.h>
#include<iostream>

void fun(int t1){
    std::cout<<t1<<std::endl;
    return;
}

发表于 更新于 分类于

今天是除夕，再过几十分钟就到了新年的第一天，除旧迎新不外乎如此。

回想过去的一年，前半年的斗志昂扬，刚过完生日时内心的踌躇满志，再次被隔离时的颓废，面对大变向的疑惑，破碎的经历造就了梦幻的2022。

专业课的学习有种一地鸡毛的感觉，大概是不适应老师的缘故，所幸我从课本上还是学到了一些东西，只是有种根基不牢固的惶恐。在大二上学期，我通过了经济学的辅修，辅修经济学一方面是想对社会运转体系有更深刻的了解；另一方面是出于走一步闲棋，多一条路的想法。CS方面在20岁生日后没有什么太大的进展，只是会写一些算法题，demo没有做，书也没有看，荒废的令我感到不安。

学业荒废的主要原因是我的心态出了问题。22年暑假结束返校后刚开学又再次被封控，中间上了几周课后又再次被封控。网课、网课、网课,摆烂、摆烂、摆烂，在狭窄的宿舍内通过屏幕看老师讲授混乱的知识，debuff太多了，我的学习状态不受控制的在糟糕的课程质量和封控压力下趋向于摆烂。下半年的时光说是虚度也没错。

零点到了，你要新年快乐呀。

2022想看的书也没有看完，只能留给2023的我看了，希望他可以认真读完我想看的书，相信后人（我）的智慧！

想去的地方因为疫情也没有去，同样相信未来的我会去看的！

没有什么好写的了，下半年对我来说是有点糟糕的，没有什么可以记录的。

未来会怎样呢？我不知道，不过怕什么？干就完事了。

2023，要去实习，要充实自己的知识，要身体健康，要开心。

旧的一年过去了，崭新的一年在键盘声中开始了。

发表于 更新于 分类于

今天，是我的生日，农历上的生日。

过去一年，我做了一些改变，也变得更加焦虑和迷茫。

降级转入了物院，从大一重新开始读书，我称之为remake。

学了很多自己喜欢的知识，上着自己喜欢的课程，偶尔会有让我头疼的数学，不过大部分学习时间还是很舒服的。认识了一些很好的朋友，每个周末出去吃饭很是令人愉快。看了一些有意思的书籍，读了很多枯燥的文章，多了一些全新的经历，我的三观在慢慢完善。

22年三月份也就是大一下学期经历了上海疫情，封控，隔离，转运，继续封控。我其实蛮享受被隔离的时光，睡醒开始学习，累了躺着或者玩手机，吃饭洗漱看电影。我在做我自己想做的事情，而不是去上课，去被迫接受知识。那段时光对我来说是很宝贵的，我第一次体会到那样舒服、那样无拘无束的状态。

我阅读了一些对我观念产生很大影响的书籍，《论人类不平等的起源和基础》、《社会契约论》、《资本论》。一些观念被替换被抹去，另一些新的东西在出现。

为了早做打算，我开始认真学习CS方面的知识，从中窥见了和物理不一样的美妙。

我感到迷茫，我要干什么？我的答案是什么？我要去做什么样的事业？我在思考，更多时候在迷茫。就业/考研/保研/出国/体制，面对这些选择，面对瞬息万变的形势，我在思考自己的答案是什么。

我感到焦虑，一停下来就会焦虑，焦虑后带来的是放纵，然后就是更深的焦虑……

我似乎不适合工作？几天前接了个线上家教，周一和周五晚上上课，薪资对我来说很好。然而到那一天的时候，脑子里想的都是要怎么才能讲好，怎么才能让学生有提高，明明只有晚上上一个半小时，教课对我来说也很轻松，我却能在白天时不时的担忧好久。 以后可以慢慢适应的吧。

大二想用家教的钱去旅行，想读更多书，想学更多知识，想去实习。

我的十九岁按下了结束键

我的二十岁刚刚开始

发表于 更新于 分类于

git –version //查看git版本

git config –global user.name 用户名
git config –global user.email 用户邮箱
//设置用户签名

git init //初始化本地库

git status //查看本地库状态

git add 文件名 //提交到暂存区

git commit -m “日志信息” 文件名 //提交到本地库

git reflog //查看历史记录

git log //查看详细历史记录

git reset –hard 版本号 //版本穿梭

git branch 分支名 //创建分支

git branch -v //查看分支

git checkout 分支名 //切换分支

git merge 分支名 //合并分支到当前分支

分支冲突后，人为修改冲突文件后，git add 文件名，git commuit -m “日志信息” (不带文件名)。

git remote add 别名 远程https地址 //给远程仓库起别名(最好与项目名称一致)

git remote -v //查看当前所有远程地址别名

git push 别名 分支 //推送本地分支上的内容到远程仓库

git clone 远程地址/别名 //将远程仓库内容克隆到本地

git pull 远程仓库地址/别名 分支名称 //将远程仓库分支最新内容拉下来后与本地分支合并

发表于 更新于 分类于

优化程序性能

编译器优化

现代编译器已经非常成熟，优化后的代码有时候程序员自己都看不懂。

但是，编译器还是保守，假设你的每个操作都是黑盒子，小心翼翼在不会影响你的操作的前提下进行优化，编译器必须很小心的使用安全的优化

关于指针的例子

1
2
3
4
void test(int *pt1,int *pt2){
    *pt1+=*pt2;
    *pt1+=*pt2;
}

假设我们的本意是 pt1+=2 (*pt2);这样写更快一点。

编译器并不会进行这样更快的优化，因为它无法确定 pt1和pt2是否指向内存中相同的位置。它只能假设不同的指针可能会指向内存中的同一位置。

循环中的低效率

1
2
3
4
5
6
7
8
for(int i=0;i<strlen(s);i++){
    ...
}

int length=strlen(s)
for(int i=0;i<length;i++){
    ...
}

每次循环都要计算strlen(s) 低效率

假如代码修改了字符串S，编译器并不知道这是否会影响strlen(s)，因此每次都会计算，并不会进行优化。

过程中函数多次调用的低效率

1
2
3
4
5
6
7
8
9
int fun1();

void test1(){
    return fun1()+fun1()+fun1();
}

void test2(){
    return 3*fun1();
}

假设我们知道fun1()并不会产生副作用，每次调用结果相同，那么test2更加高效。

编译器不能判断fun1()是否会产生副作用，因此不会把test1优化到test2；

inline代替优化函数调用；

不必要的内存引用

1
2
3
4
5
6
7
8
9
10
for(;j<10;j++)
b[6]+=a[j];


//优化 
int temp=0; // 优化后 该局部变量被保存在寄存器中，不用一次次的进行内存读写
for(;j<10;j++)
temp+=a[j];

b[6]=t;

因为不确定a[j]的变化是否会改变b[6]的数值，因此每次都要从内存读入b[6]，再把更新后的b[6]写进内存,这种内存读写是不必要的，要一次次再内存和寄存器中传送数据。

因为b[6]和a[j]可能指向同一个地址，因此编译器不会进行优化。

流水线处理和并行

进行循环展开，减少循环迭代次数，提高效率。(减少过程中的索引计算和条件分支，减少计算中关键路径的操作数量)。

不相关的计算可以进行流水线处理

循环展开和并行累计多个值一起计算，会提高程序的流水线处理的效率，提高程序并行性。

编译器会自行进行优化，仅作为了解 其实是我现在这部分学的不好

下学期 一定要看看 CAAQA 这本经典书

存储器层次结构

存储技术

SRAM(在CPU芯片上) DRAM(主存) 闪存 等等

如何进行内存读写

cpu将地址传入总线上 发出信号；主存将对应地址的数据x传入总线；cpu 读出数据x 复制到寄存器中。cpu将地址放到总线上，主存读出地址，等待数据字；cpu将数据放到总线上；主存接收数据并且储存到先前指定的地址。

磁盘构造，如何进行磁盘读写(指令，逻辑块号，内存地址)

CPU通知磁盘控制器进行磁盘读写后切换执行其他进程，磁盘写数据到主存中无需CPU操作，写数据结束后 中断 通知CPU。这称为直接内存访问DMA，这种数据传送称为DMA传送

奇怪的SSD(固态硬盘).

局部性原理

程序倾向于使用其地址接近或者等于最近使用过的数据和指令的地址的那些数据和地址。

program tend to use data and instructions with addresses near or equal to those they have used recently.

时间局部性和空间局部性

避免代码出现差的局部性。

缓存不命中的种类

冷不命中：一个空的缓存称为冷缓存，冷缓存必然不命中，称为冷不命中。

冲突不命中：常用的放置策略是将 k+1 层的某个块限制放置在 k 层块的一个小的子集中。比如 k+1 层的块 1,5,9,13 映射到 k层的块 0。这会带来冲突不命中。

容量不命中：当访问的工作集的大小超过缓存的大小时，会发生容量不命中。即缓存太小了，不能缓存整个工作集。

高速缓存存储器

最好看书回忆具体步骤

大概就是，将k个固定大小的字节作为一个整体即“块”，按块储存到高速缓存中，所以要考虑块的大小也会影响到缓存效率（直接映射高速缓存容易引起抖动，例如 p432的例子）

高速缓存确定一个请求是否命中，然后抽取出被请求的字的过程分为三步：

组选择 行匹配 字抽取

具体例子参考 p430

有关写的问题

写命中（写一个已经缓存了的字 w）的情况下，高速缓存更新了本层的 w 的副本后，如何处理低一层的副本有两种方法：

  1. 直写：立即将 w 的高速缓存块写回到低一层中。

    1. 优点：简单
    2. 缺点：每次写都会占据总线流量

  2. 写回：尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到低一层中。

    1. 优点：利用了局部性，可以显著地减少总线流量。
    2. 缺点：增加了复杂性。必须为每个高速缓存行维护一个额外的修改位，表明此行是否被修改过。

写不命中情况下的两种方法：

  1. 写分配：加载相应的低一层的块到本层中，然后更新这个高速缓存块。

    1. 优点：利用写的空间局部性
    2. 缺点：每次不命中都会导致一个块从低一层传送到高速缓存

  2. 非写分配：避开高速缓存，直接把这个字写到低一层中

直写一般与非写分配搭配，两者都更适用于存储器层次结构中的较高层。

写回一般与写分配搭配，两者都更适用于存储器层次结构中的较低层，因为较低层的传送时间太长。

因为硬件上复杂电路的实现越来越容易，所以现在使用写回和写分配越来越多。

程序中利用局部性

写完配套的lab就行了

  1. 注意力集中在内循环中
  2. 按照数据对象存储在内存中的数据，按照步长为1来读数据，利用空间局部性
  3. 一旦从存储器中读入了一个数据对象，就尽可能多使用它，利用时间局部性

发表于 更新于 分类于

程序的机器级表示

隐藏的东西 in higher

程序计数器PC，寄存器(整数寄存器，浮点数寄存器，条件码寄存器)。寄存器可以操作不储存不同字节大小的数据。

阅读汇编代码

反汇编得到汇编代码

了解各个指令的具体含义，sub、movb、movzbw、leaq等等。学会阅读不同的操作数格式。

控制语句

根据条件码寄存器跳转到指定位置，以达到循环语句和判断语句的效果。

switch使用跳转表，根据对应值按照跳转表进行跳转，跳转表对应数值较大时可以进行相应加减运算处理。跳转表范围较大且表项比较稀疏的时候，可以构建二叉树 二分查找。

过程

全局变量在data区域，代码在text区域，局部变量在stack区域，new、malloc的变量在heap区域。

Stack

被调用的函数调用结束时，对栈指针进行操作，之后ret弹出返回地址，返回调用函数。

栈帧管理(每一个函数有自己对应的栈帧)，函数在stack上的储存空间 成为过程的栈帧（stack fram），栈帧会保留需要保留的寄存器 以便在函数调用结束后恢复寄存器原有的值（有的寄存器由caller保存 有的由callee保存）。

寄存器不足够存放本地数据、对局部变量进行&运算、局部变量为数组或者结构，此时局部变量必须存放在内存中。

Array Union Struct

数组地址顺序排列。结构体地址顺序排列。

Union所占地址空间大小为其中最大的数据所占地址空间，相当于对同一地址空间的不同部分赋予不同的别名，在使用时按照别名进行类型转换。

1
2
3
4
union u{
    unsigned i;
    float f;
}u0;

则 i 为 f底层float表示方法的 十进制数值。

sizeof(u0)=4
size0f(u0.i)=sizeof(u0.f)=sizeof(u0)=4

数据对齐

任何K字节的基本对象的地址必须是K的倍数

1
2
3
4
5
6
struct test{
    int i;
    char j;
    int k;
}t1;

则 sizeof(t1)=12

i占四字节，j占一字节但是j后面三字节为空以达到数据对齐目的，K占四字节 所以共十二字节。

同一类型对象尽量放在一起，节省空间。

内存越界引用和缓冲区溢出

attack lab就是基于缓冲区溢出后 修改返回地址 达到攻击的效果。

C对于数组引用不进行边界检查，局部变量和状态信息都保存在stack 越界引用数组容易修改状态信息（返回地址等）进行破坏。

gets读函数对读入数据大小不进行检查，数据溢出缓冲区会导致stack中信息被破坏。

防范手段

写更加strong的代码，进行数据大小检查。

对stack进行破坏检测，存储canary(金丝雀)值(通常该值 末尾以 0 结尾，即使字符数组溢出1位也不影响,因为字符以0结尾，不会修改canary数值，贴心)

stack地址随机化

限制可执行代码区域，

发表于 更新于 分类于

今年一高似乎考的不错。

下午刚睡醒，和同学在群里吹水时说起了今年的高考，我才发现由于取消了提前 交大在我省的分数线降了不少。我高考那一年，是靠着国家专项计划才来了交大，不然只能走提前批，分数不高的人在交大面前没有选择权，于是被调剂。入学没多久，我一直在后悔当时没有去中科大学物理，哪怕后面发现自己适应不了科大物理系的压力，也可以自由转专业。就这样浑浑噩噩的过了一学期，寒假时了解到交大的转专业对提前批有诸多限制，幸运的是我走国家专项计划不受这些限制，大一下我转入了物院。

我对交大是充满感激的，正如我在某个平台上的名字‘remake’,我一直感觉自己的大学因为转专业这个决定被重置了，我的大学生活换了一个方式开始，我很感激交大。

有时候在想，假如当初报了科大或者南大、北航，去学热门专业会怎么样？想了想感觉自己或许会摆烂大学四年。我上大学之前并不是一个自律的人，说得好像我现在是一样 在大学这种自由的环境下，失去了老师的监督，没有面临高考的压力，假如学了CS这些不担心就业的专业，我大概率会跟着培养计划按部就班的摆烂四年。只有经过学化学的磨练，深切体会到英语挂科后的绝望，在挂科后认真思考过自己的出路，我才明白对于我这样一个背景普通，尚未发现自己有什么天赋的人，学习究竟意味着什么。

我思想的改变和交大关系很大，毕竟地狱难度的英语期末考试交大是独一份 现在我还后悔来交大吗？后悔被调剂吗？我不后悔。

动过去学校门口劝学弟学妹们不要为了不浪费一分去盲目冲学校的念头。想了想放弃了，各人有各人的际遇，一年前的我还在后悔来了交大，现在我却为自己感到幸运。再者，高考后的学生观念总是充斥着对于名校的向往 我也向往CMU Stanford，小县城出身的我们即使看了知乎上的言论也大都不会相信专业之间的差距远大于学校，总是以为好学校的专业不会是这样子的，这没办法改变。

发表于 更新于 分类于

开始暑假的集中刷题了，时隔两个月没刷算法，今天发现之前获得的手感和技巧都丧失的差不多了，所以萌生了记笔记的想法。记下一些有价值的题目

LeetCode Easy

剑指offer 05 替换空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string replaceSpace(string s) {
        
        int length=s.size();
        int count=0;
        for(int i=0;i<length;i++){
            if(s[i]==' ')
            count++;
        }
        s.resize(length+2*count);
        int old=length-1;// 从后向前替换 双指针
        int n=length+2*count-1;//n为new 
        while(old>=0){
            if(s[old]==' '){
                s[n--]='0';
                s[n--]='2';
                s[n--]='%';
            }
            else{
                s[n--]=s[old];
            }
            old--;
        }
        return s;    
    }
};

精髓在于，从后向前替换，而不是从前向后替换，后者做法每次替换都要移动后面元素 o(n^2),前者不需要 o(n);因为 从后向前，n走在old后面(相对于前进方向)，从前向后n在old的前面，s[n]依靠s[old],因此 n应该在old后面。

35 搜索插入位置

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int length=nums.size();
        int left=0;
        int right=length-1;
        int mid=left+(right-left)/2;

        while(left<=right){
            int now=nums[mid];
            if(now<target) left=mid+1; 
            else if(now>target) right=mid-1;
            else return mid;
            mid=left+(right-left)/2;
        }
        
        return right+1; 

    }
};

这道题目我的犹豫点在于循环的时候target是否会落在获得的区间之外，比如[0，100，110，200] target=102,第一次迭代后，nums[left]=110；target其实在left的左边，因此在二分处理的时候一直思考很多限制，一个简单的Easy题目却想了很多。后来想明白了，我的犹豫点是对的，但是这不影响什么。

这道题目，可以找到和target相等的目标值也就罢了（704题），找不到也就是需要插入的时候，要把target插入在两个数字中间的区域，这种情况下 按照从大到小排序，某次迭代后target一定会落在获得的区间旁边的区域，也就是right和right+1之间或者left和left-1之间，此后紧挨着target的区间边界left/right不动，另一个边界不断移动，直到 right小于left ,此时迭代终止，而target的位置等于right+1也就是在right和left之间；

二分加暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int length=nums.size();
        int left=0;
        int right=length-1;
        int temp=right-left;
        while(temp>2){
            int mid=left+temp/2;
            int now=nums[mid];
            if(now<target) left=mid+1;
            else if(now>target) right=mid-1;
            else return mid;
            temp=right-left;
        }
        for(int i=left;i<=right;i++){
            if(nums[i]>=target) return i;
        } //这个暴力写法很优雅。
        return right+1;
    }
};

仅仅在区间很小的时候采用了暴力，这可能会更高效一点。

27 移除元素

快慢双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int length=nums.size();
        int right=0;
        int left=0;
        while(right<length){
            if(nums[right]==val) right++;
            else{
                nums[left]=nums[right];
                left++;
                right++;
            }
        }

        return left;

    }
};

本质上是，将两个指针看成在两个相同的数组上操作，而不是一个数组，快指针right将自己所在的数组上的所有不等于val的数值移动到慢指针所在的数组上，(0，right)开区间内的点都!=val。

双指针优化 前后双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int length=nums.size();
        int right=length-1;
        int left=0;
        while(right>=left){
            if(nums[left]==val){
                if(nums[right]!=val){
                    nums[left]=nums[right];
                    right--;
                    left++;
                }
                else right--;
            }
            else left++;
        }

        return left;

    }
};

用后指针指向的元素替换前指针指向的需要删除的元素，直到两指针相遇后进入最后一次循环。

LeetCode Mid

59 螺旋矩阵||

便于理解带注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop_times = n / 2; // 一圈处理两层，需要循环几圈，例如n为奇数3，那么loop_times = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
        int i,j;
        while (loop_times --) {
            i = startx;
            j = starty;//竖着为x 横着为y  y轴上是同一个一维数组的。

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < starty + n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < startx + n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 2;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

习惯写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> answer(n,vector<int>(n,0));
        int loop_times=n/2;
        int end=n/2;
        int start_x=0;
        int start_y=0;
        int number=1;
        int cut_length=1;
        int x,y;
        while(loop_times--){
            x=start_x;
            y=start_y;

            for(;y<n-cut_length;y++){
                answer[x][y]=number++;
            }
            for(;x<n-cut_length;x++){
                answer[x][y]=number++;
            }
            for(;y>cut_length-1;y--){
                answer[x][y]=number++;
            }
            for(;x>cut_length-1;x--){
                answer[x][y]=number++;
            }

            start_x++;
            start_y++;
            cut_length++;
        }

        if(n%2){
            answer[end][end]=number;
        }

        return answer;

        
    }
};

这道模拟有点意思，像这种模拟我一直不太在行，打印乘法表这种大一C++作业题我都有点怵，菜鸡本菜了。

142 环形链表||

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;
        if(head==nullptr||head->next==nullptr) return nullptr;
        slow=slow->next;
        fast=fast->next->next; 
        while(fast!=nullptr&&fast->next!=nullptr&&slow!=fast){
            slow=slow->next;
            fast=fast->next->next;
        }//fast指针经过的长度 是 slow经过的长度的 2 倍数
        if(fast==nullptr||fast->next==nullptr) return nullptr;
        slow=head; //slow从头节点开始 fast从两者在环上相遇的位置开始 两者到入口处长度相等(解方程可得该信息
        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }
        return fast;

    }
};

经典快慢指针做法，后面找环入口用到简单的数学知识。应该设长度，而不是节点数目。

15 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int length=nums.size();
        vector<vector<int>> answer;
        if(length<3) return answer;
        sort(nums.begin(),nums.end());
        
        
        for(int cur=0;cur<length;cur++){
            if(nums[cur]>0) return answer;
            int left=cur+1;
            int right=length-1;
            if(cur>0&&nums[cur]==nums[cur-1]) continue;// 避免排除 -1 -1 2 这种正确情况 cur 在重复序列的第一个
            // cur重复且nums[cur]对应有正确结果 则会出现重复答案，cur不重复且固定 只考虑left重复，结果一样，cur left 不重复且固定，只考虑right重复，结果也可能重复。
            // 故三种情况均需要去重  
            while(left<right){
                
                if(nums[cur]+nums[right]+nums[left]>0){
                    right--;//nums[right] 变为新的数值，但在right=length-1或者上一个判断循环满足三者相加等于0时，不一定变为新的数值，在下一次循环时候才会变化
                    while(left<right&&nums[right]==nums[right+1]) right--;// right位置移动到 (新的)重复的序列的 第一个位置，若为最后一个位置，则排除了nums[right]==nums[left]的正确结果
                }
                else if(nums[cur]+nums[right]+nums[left]<0){
                    left++;
                    while(left<right&&nums[left]==nums[left-1]) left++;
                }
                else{
                    answer.push_back(vector<int>{nums[cur],nums[left],nums[right]});
                    while(left<right&&nums[right]==nums[right-1]) right--;// 去掉right重复，right移动到重复序列的最后一个位置,此时为最后一个是因为 已经符合结果 需要更新数值避免重复。
                    while(left<right&&nums[left]==nums[left+1]) left++;
                    
                    right--; //nums[right]变为新的数值 
                    left++;
                }
            }

        }
        return answer;
    }
};

双指针，去重麻烦。

四数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
	    // 剪枝处理
            if (nums[k] > target && (nums[k] >= 0 || target >= 0)) {
            	break; // 这里使用break，跳出循环
            }
            // 去重 k移动到新的重复序列的最左端 nums[k] 更新, 并且避免排除 -1 -1 -1 3 target为0的正确答案
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
	    	// 2级剪枝处理
		        if (nums[k] + nums[i] > target && (nums[k] + nums[i] >= 0 || target >= 0)) {
		            break; // 跳出 二级循环
		        }
		
                // 正确去重方法
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
                        right--;
                        // 当前元素不合适了，可以去重，right移动到新的重复序列的最右端，nums[right]更新
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if (nums[k] + nums[i]  < target - (nums[left] + nums[right])) {
                        left++;
                        // 不合适，去重
                        while (left < right && nums[left] == nums[left - 1]) left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 去重逻辑应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;// right移动到旧重复序列的最左端
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;//此时nums[right]才更新
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

经典，需要背诵(×

151 颠倒字符串单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    
    void reverse(string& s,int begin,int end){
        while(begin<end){
            swap(s[begin++],s[end--]);
        }
    }// 翻转函数 左闭右闭

    string reverseWords(string s) {
        
        
        while(s[0]==' '){
            s.erase(s.begin());
            
        } // 清除前面的空格
    
        while(s[s.size()-1]==' '){
            s.erase(s.end()-1);
        }// 清除后面空格
        
        int cur=0;
        int length=s.size();
        
        int slow=0;
        reverse(s,0,length-1); // 整体字符串翻转
        
        while(cur<s.size()){ // 删除空格导致size动态变化 所以用s.size() 随时更新 而不是固定的数值
            if(s[cur]==' '){
                reverse(s,slow,cur-1); // 局部单词内部翻转
                slow=cur+1;
            }
            else if(cur==s.size()-1) reverse(s,slow,cur); // 局部最后一个单词翻转
            
            while(s[slow]==' '){
                s.erase(s.begin()+slow);
            }// 清除单词之间多余的空格
            
            cur++;
        }
        return s;
    }
};

巧妙之处在于，先整体翻转 后 局部反转，改变了单词的位置顺序 而 不改变单词内部的字母顺序。

不足之处在于，reverse时间复杂度为o(n)，加上外面循环o(n),一共为o(n^2)，优化的话可以采用双指针，提前清除所有多余空格，时间复杂度为o(n)，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int length=s.size();
int slow=0; 
int fast=0;
while(fast<length){
    if(s[fast]==' '){
        if(slow!=0&&s[slow-1]==' ') slow--;
        s[slow]=s[fast]; // 无法去除两端的空格，两侧存在至多一个空格。
    }
    else{
        s[slow]=s[fast];
    }
    slow++;
    fast++; // slow 和 fast 处理也巧妙，夸我一句。
}
if(s[slow-1]==' ') s.resize(slow-1);// 去除后面多余的一个空格
else s.resize(slow);

if(s[0]==' ') s.erase(s.beigin());

清除空格 时间复杂度o(n)