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是静态的,它在proc中调用extractWord.奇怪的是,使其静止导致更多的CPU消耗.在分析之后,我看到我正在进行大量的堆分配但是我不知道为什么因为std :: vector即使在向量被清除之后也应该保留它的项目.这样做可能不那么密集吗？字符串长度未知,结果字符串的数量也不是我选择std :: vector的原因,但是有可能有更好的方法吗？

谢谢

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

Answer 1

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

也就是说,字符串处理通常可能是CPU密集型的,并且重新分配字符串对象的向量需要大量复制.每次向量重新分配内存时,每个字符串对象都需要复制到内存中的另一个位置.(幸运的是,一旦C++ 0x移动构造函数到位,这将大大减轻.)

此外,您清除向量的事实,每次不改变的事实,每次调用push_back的结果复制一个字符串对象到载体中,这可能是所有你看到的堆分配的原因.不要忘记每个std::string需要在堆上分配内存以存储字符串的实例.