由于写这个 Lab1 的笔记距离完成 Lab1 实验1 已经过去了很久，所以可能会比较简略

Lab1 介绍

在 Lab1 中，需要实现一个流重组器：将传入的没一份打乱的字节流重新组合形成原来的有序的字节流。即实现 StreamReassembler 类。

为什么要这样做？ TCP 对处理乱序和重复包的健壮性来自于它能将字节流的任意摘录拼接回原始流的能力。在离散的可测试模块中实现这一功能将使处理传入段变得更加容易

注意：

• 每个流碎片由起始位置，长度，字符串内容组成
• 碎片会重叠，但是不会有冲突
• 一个字节没有被写入 _output 当且仅当它前面的那个字符没有被写入 _output。换而言之如果一个标号为 index 的字节存在，并且 [0, index - 1] 的字符存在那么它就必须被写入 _output 中。（0 号字符一存在就要被写入 _output 中）
• 会存在字符串内容为空的带有 EOF 标志的碎片

需要理解关于 StreamReassembler 类的 capacity 的指的是什么，实际上你需要保证 _output 中未被读取的字节数 + 未重组完成的字节数 <= capacity。

具体实现上一些博客是用 std::set 维护，对于相交情况分类讨论。我开始想着反正都带 $\log $ 的，直接用 std::map 暴力模拟即可。

但是这么搞常数比较大，通过 Lab1 的测试时间超过了 1s，7/26 测试点为 0.62s，没有达到最低要求：

后来我发现只需要稍微改变一下就能够把 std::map 换成 std::vector 了，速度顿时提升了不少，还去掉了 $\log $ 。

代码

就只放 std::vector 版本了

声明部分：

//! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order,
//! possibly overlapping) into an in-order byte stream.
class StreamReassembler {
  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::vector<std::pair<char, bool> > _stream; //!< The current part of the reassembled byte stream
    size_t _cur_index;   //!< The index of the first byte of the reassembled byte stream
    size_t _eof_index;         //!< The index of the last byte of the entire stream
    size_t _unassembled_bytes_cnt; //!< The number of bytes that have not yet been reassembled

  public:
    //! \brief Construct a `StreamReassembler` that will store up to `capacity` bytes.
    //! \note This capacity limits both the bytes that have been reassembled,
    //! and those that have not yet been reassembled.
    StreamReassembler(const size_t capacity);

    //! \brief Receive a substring and write any newly contiguous bytes into the stream.
    //!
    //! The StreamReassembler will stay within the memory limits of the `capacity`.
    //! Bytes that would exceed the capacity are silently discarded.
    //!
    //! \param data the substring
    //! \param index indicates the index (place in sequence) of the first byte in `data`
    //! \param eof the last byte of `data` will be the last byte in the entire stream
    void push_substring(const std::string &data, const uint64_t index, const bool eof);

    //! \name Access the reassembled byte stream
    //!@{
    const ByteStream &stream_out() const { return _output; }
    ByteStream &stream_out() { return _output; }
    //!@}

    //! The number of bytes in the substrings stored but not yet reassembled
    //!
    //! \note If the byte at a particular index has been pushed more than once, it
    //! should only be counted once for the purpose of this function.
    size_t unassembled_bytes() const;

    //! \brief Is the internal state empty (other than the output stream)?
    //! \returns `true` if no substrings are waiting to be assembled
    bool empty() const;
};

成员函数实现部分：

StreamReassembler::StreamReassembler(const size_t capacity) : _output(capacity), _capacity(capacity), 
                                                              _stream(capacity), _cur_index(0),
                                                              _eof_index(std::numeric_limits<size_t>::max()), 
                                                              _unassembled_bytes_cnt(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) {
    auto st = max(index, _cur_index);
    auto ed = min(index + data.size(), min(_cur_index + _capacity - _output.buffer_size(), _eof_index));
    if (eof) _eof_index = min(_eof_index, index + data.size());
    for (size_t i = st, j = st - index; i < ed; ++i, ++j) {
        auto &t = _stream[i % _capacity];
        if (t.second == true) {
            if (t.first != data[j])
                throw runtime_error("StreamReassembler::push_substring: Inconsistent substrings!");
        } else {
            t = make_pair(data[j], true);
            ++_unassembled_bytes_cnt;
        }
    }
    string str;
    while (_cur_index < _eof_index && _stream[_cur_index % _capacity].second == true) {
        str.push_back(_stream[_cur_index % _capacity].first);
        _stream[_cur_index % _capacity] = { 0, false };
        --_unassembled_bytes_cnt, ++_cur_index;
    }
    _output.write(str);
    if (_cur_index == _eof_index) _output.end_input();
}

size_t StreamReassembler::unassembled_bytes() const { return _unassembled_bytes_cnt; }

bool StreamReassembler::empty() const { return unassembled_bytes() == 0; }

测试

std::map 版本

std::vector 版本