优化字符串

Posted on | Edited on

C++的std::string是C++标准库中使用最广泛的特性之一，例如google的chromium，std::string对内存管理器的调用次数占到了内存管理器被调用的总次数的一半

前面也提到过，只要涉及内存被频繁分配/复制的地方，就有优化的可用武之地

字符串是动态分配的

C++的std::string实际上是一个char的数组，其大小是固定的，如果调用+运算，新字符串的大小超过原字符串的大小，就会发生以下操作

  • 申请一块内存
  • 将新字符串复制到内存中
  • 释放掉原有字符串

如果是以下的代码，就会发生频繁的内存分配

1
2
3
4
5
std::string str = "a";
for (int i = 0; i < 100; i++)
{
    str = str + "b";
}

字符串是值

在赋值语句和表达式中，字符串的行为和值一样，例如你使用str1=str2+str3+str4，那么str2+str3的结果会保存在一个临时变量中，然后用其和str4相加，这时又会产生一个临时变量，然后用于赋值给str1

消除临时变量

我们可以分析一下这段代码的情况

1
str = str + "b";

这段代码调用的是operator+，其函数源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class _CharT, class _Traits, class _Alloc>
inline basic_string<_CharT,_Traits,_Alloc>
operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
          const _CharT* __s) {
  typedef basic_string<_CharT,_Traits,_Alloc> _Str;
  typedef typename _Str::_Reserve_t _Reserve_t;
  _Reserve_t __reserve;
  const size_t __n = _Traits::length(__s);
  _Str __result(__reserve, __x.size() + __n, __x.get_allocator()); //临时字符串
  __result.append(__x);
  __result.append(__s, __s + __n);
  return __result;
}

首先，我们看到的是其返回值，是basic_string<_CharT,_Traits,_Alloc>，也就说，其会存在一次复制，将内部用于保存新字符串的临时变量复制出去

临时字符串的构建是使用append进行构建的，append的部分源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
basic_string& append(const basic_string& __s) 
  { return append(__s.begin(), __s.end()); }

basic_string& append(const basic_string& __s,
                     size_type __pos, size_type __n)
{
  if (__pos > __s.size())
    _M_throw_out_of_range();
  return append(__s.begin() + __pos,
                __s.begin() + __pos + min(__n, __s.size() - __pos));
}

basic_string& append(const _CharT* __s, size_type __n) 
  { return append(__s, __s+__n); }

然后我们再看看operator+=

1
2
3
basic_string& operator+=(const basic_string& __s) { return append(__s); }
basic_string& operator+=(const _CharT* __s) { return append(__s); }
basic_string& operator+=(_CharT __c) { push_back(__c); return *this; }

看返回值，返回的是引用，减少了一次复制，然后新字符串的构建也是使用的append，因此不用多说，自然是operator+=更胜一筹

因此可以使用str+="b"替换之前的str=str+"b"

减少内存的重新分配

无论是+=/+都会使得字符串不断增长，假设，std::string的内存管理如std::vector一般，也就是预先分配较大块的内存,例如两倍，那么如果append的字符串不断增长，例如

1
2
3
4
a = "a";
a += "aaaaaa";
a += "bbbbbbbbbbbbbbbbb";
a += "ccccccccccccccccccccccccccccccc";

的情况，那么频繁的内存分配和复制依旧可能会发生，此时，有一种策略则是预先分配空间，然后减少内存的分配和复制，这种策略对于很多动态分配的容器都是有用的

1
str.reserve(length);

减少对参数字符串的复制

这个在很多书籍都有提到过，通过使用引用传递，消除参数的复制，不过值得注意的是，这种策略对于对象才起作用，如果是对于一般的基本类型，这种策略的效果甚微

使用迭代器消除指针解引用

std::string的实质是字符数组，因此也会支持下标访问，例如str[i]，其源码如下

1
2
const_reference operator[](size_type __n) const
  { return *(_M_start + __n); }

我们可以通过迭代器直接进行操作，而不必进行这次多余的函数调用(不过某些时候会导致可读性下降)

消除对返回值的复制

我们可以将接收返回值的变量的引用传入，直接改变，而不是用返回值对其进行赋值

不过，这种策略只适合对结果字符串进行频繁操作的情况

使用字符数组代替字符串

这种策略用于对性能要求极高的情况下，使用C风格的字符串函数来手动编写函数，进行手动的内存管理，不过该种策略难度较高，而且不易使用，但是却能带来显著的性能提升(前提是所有函数都使用得当的情况下)

使用更好的算法

对于某些情况我们可以通过改进算法来达到更高的效率

例如，从字符串中删除某些字符，下面有几种方法，我们逐一分析

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
//1
void remove_ctrl_ref_result_it(std::string &result, std::string const &s)
{
    result.clear();
    result.reserve(s.length());
    for (auto it = s.begin(), end = s.end(); it != end; ++it)
    {
        if (*it > 0x20)
        {
            result += *it;
        }
    }
}

//2
void remove_ctrl_block(std::string &result, std::string s)
{
    result.clear();
    result.reserve(s.length());
    for (size_t b = 0,i = b, e=s.length(); b < e; b = i+1)
    {
        for (i = b; i < e; ++i)
        {
            if (s[i] < 0x20)
                break;
        }
        result += s.substr(b, i-b);
    }
}

//3
void remove_ctrl_block_append(std::string &result, std::string s)
{
    result.clear();
    result.reserve(s.length());
    for (size_t b = 0, i = b, e = s.length(); b < e; b = i + 1)
    {
        for (i = b; i < s.length(); ++i)
            if (s[i] < 0x20)
                break;
        result.appen(s, b, i-b);
    }
}

//4
std::string remove_ctrl_earse(std::string s)
{
    for (size_t i = 0; i < s.length();)
        if (s[i] < 0x20)
            s.erase(i,1);
    	else
            ++i;
    return s;
}

下面是分析：

代码1，频繁地进行字符复制

代码2，将字符复制改为字符串复制，减少了内存复制的频率

代码3，在代码2中，存在以下函数

1
2
3
4
5
6
basic_string substr(size_type __pos = 0, size_type __n = npos) const {
    if (__pos > size())
      _M_throw_out_of_range();
    return basic_string(_M_start + __pos, 
                        _M_start + __pos + min(__n, size() - __pos));
  }

这个会造成一次新字符串的复制

将其改为append将会消除这次复制

代码4，对同一个字符串进行操作，只涉及到少量的内存复制，除了返回字符串涉及到内存复制，其他操作都不会涉及，性能优于前三者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

basic_string& erase(size_type __pos = 0, size_type __n = npos) {
  if (__pos > size())
    _M_throw_out_of_range();
  erase(_M_start + __pos, _M_start + __pos + min(__n, size() - __pos));
  return *this;
}  

iterator erase(iterator __position) {
                              // The move includes the terminating null.
  _Traits::move(__position, __position + 1, _M_finish - __position);
  destroy(_M_finish);
  --_M_finish;
  return __position;
}

总结

上面介绍到优化方式需要对代码进行推敲后使用，切不可盲目乱用，盲目优化不可取，但是一些策略是可以通用的

例如传递参数的时候使用引用传递，减少临时变量的产生，以及使用更好的算法