c++ - std::vector push_back 是瓶颈

Question

这是我的算法的作用: 它需要一个长的 std::string 并根据它是否大于宽度将它分成单词和子单词:

inline void extractWords(std::vector<std::string> &words, std::string &text,const AguiFont &font, int maxWidth)
{


    words.clear();

    int searchStart = 0;
    int curSearchPos = 0;
    char right;
    for(size_t i = 0; i < text.length(); ++i)
    {
        curSearchPos = i;

        //check if a space is to the right
        if( i == text.length() - 1)
            right = 'a';
        else
            right = text[i + 1];

        //sub divide the string if it;s too big
        int subStrWidth = 0;
        int subStrLen = 0;
        for(int x = searchStart; x < (curSearchPos - searchStart) + 1; ++x)
        {
            subStrWidth += font.getTextWidth(&text[x]);
            subStrLen ++;
        }
        if(subStrLen > maxWidth && subStrLen > 1)
        {
            for(int k = 2; k <= subStrLen; ++k)
            {
                subStrWidth = 0;
                for(int p = 0; p < k; ++p)
                {
                    subStrWidth += font.getTextWidth(&text[searchStart + p]);
                }
                if(subStrWidth > maxWidth)
                {
                    searchStart += k - 1;

                    words.push_back(text.substr(searchStart,k - 1));
                    break;

                }
            }
        }

        //add the word
        if((text[i] == ' ' && right != ' ' ) || i == text.length() - 1)
        {

                if(searchStart > 0)
                {
                    words.push_back(text.substr(searchStart ,(curSearchPos - searchStart) + 1));

                }
                else
                {
                    words.push_back(text.substr(0 ,(curSearchPos - searchStart) ));
                    words.back() += text[curSearchPos];

                }

            searchStart = i + 1 ;
        }
    }


}

如您所见，我使用 std::vectors 来插入我的话。该载体通过引用给出。 std::vector 是静态的，它在调用 extractWord 的过程中。奇怪的是，将其设置为静态会导致更多的 CPU 消耗。分析后，我看到我进行了大量的堆分配，但我不知道为什么，因为 std::vector 即使在 vector 被清除后也应该保留其项目。是否有一种不太密集的方式来做到这一点？字符串长度未知，结果字符串的数量也未知，这就是我选择 std::vector 的原因，但是是否有更好的方法？

谢谢

*实际上我认为我的子串生成很慢

Answer 1

通常，如果向 vector 添加元素是一个瓶颈，您应该使用 std::vector<T>::reserve提前预留一些空间。这应该会降低调用 push_back 的可能性。将触发内存重新分配。

也就是说，字符串处理通常会非常占用 CPU，重新分配字符串对象的 vector 需要很多复制。每次 vector 重新分配内存时，每个字符串对象都需要复制到内存中的另一个位置。 (幸运的是，一旦 C++0x 移动构造函数到位，这将大大缓解。)

此外，您每次都清除 vector 这一事实并不会改变每次调用 push_back 的事实。结果将字符串对象复制到 vector 中，这可能是您看到的所有堆分配的原因。不要忘记 std::string 的每个实例需要在堆上分配内存来存储字符串。