从源码分析string和vector的内存增长逻辑教程

std string内存增长逻辑是怎样的？跟std vector有什么异同？
各个stl实现版本有不同，这里只举例SGI和VS2019的版本说明。

1. vector的内存增长逻辑

1）SGI STL版本
vector的insert函数源码(此处只摘录出内存申请逻辑相关的代码)：

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  if (n != 0) {
    if (size_type(end_of_storage - finish) >= n) {
      ...
    }
    else {
      const size_type old_size = size();        
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      ...
    }
  }
}

从源码可知，如果要插入的元素个数小于现有的元素个数，那么新开辟的内存大小等于当前元素个数两倍的内存大小。如果要插入的元素个数大于现有的元素个数，那么新开辟的内存大小等于当前元素个数加上要插入的元素个数的内存大小。

2）VS2019版本

    size_type _Calculate_growth(const size_type _Newsize) const {
        // given _Oldcapacity and _Newsize, calculate geometric growth
        const size_type _Oldcapacity = capacity();

        if (_Oldcapacity > max_size() - _Oldcapacity / 2) {
            return _Newsize; // geometric growth would overflow
        }

        const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;

        if (_Geometric < _Newsize) {
            return _Newsize; // geometric growth would be insufficient
        }

        return _Geometric; // geometric growth is sufficient
    }

从源码可知，vs版本是新开辟内存为当前的capacity * 1.5倍的大小。

2. string的内存增长逻辑

1）SGI STL版本

template <class charT, class traits, class Allocator>
inline basic_string <charT, traits, Allocator>::Rep *
basic_string <charT, traits, Allocator>::Rep::
create (size_t extra)
{
  extra = frob_size (extra + 1);
  Rep *p = new (extra) Rep;
  p->res = extra;
  p->ref = 1;
  p->selfish = false;
  return p;
}

template <class charT, class traits, class Allocator>
inline size_t basic_string <charT, traits, Allocator>::Rep::
frob_size (size_t s)
{
  size_t i = 16;
  while (i < s) i *= 2;
  return i;
}

从源码可知，一个空的string的初始大小为16。当size大于16时，内存增长逻辑则跟SGI版本vector不同，新的capacity为当前的2倍，而vector时当前size的2倍。

2）VS2019版本

    size_type _Calculate_growth(const size_type _Requested) const { // determines the next array size to allocate
        const size_type _Max    = max_size();
        auto& _My_data          = _Get_data();
        const size_type _Masked = _Requested | _ALLOC_MASK;
        if (_Masked > _Max) { // the mask overflows, settle for max_size()
            return _Max;
        }

        const size_type _Old = _My_data._Myres;
        if (_Old > _Max - _Old / 2) { // similarly, geometric overflows
            return _Max;
        }

        return _Max_value(_Masked, _Old + _Old / 2);
    }
    
    static constexpr size_type _ALLOC_MASK =
        sizeof(value_type) <= 1
            ? 15
            : sizeof(value_type) <= 2 ? 7 : sizeof(value_type) <= 4 ? 3 : sizeof(value_type) <= 8 ? 1 : 0;

从源码可知，一个空的string，初始的capacity是15。当size大于15时，内存增长逻辑则跟VS版本 vector一样，新的capacity为当前的1.5倍。

3. string和vector<char>的比较

通过上面的分析，两者在内存管理和数据结构方面基本是相同的。只是string针对字符串操作做了更多的扩展。

1. 转换为C-style字符串。c\_str() data()
2. length() 等同于size()
3. 重载输入输出流操作符。 operator<< operator>>
4. 字符串拼接。operator+ operator+=