std::string和多个连接

4

让我们考虑这段代码片段,并假设a、b、c和d都是非空字符串。

    std::string a, b, c, d;
    d = a + b + c;

计算这3个std::string实例的总和时,标准库实现会创建第一个临时std::string对象,将ab的缓冲区连接起来复制到其内部缓冲区中,然后在临时字符串和c之间执行相同的操作。
一位程序员强调,与其这种行为不同,可以定义operator+(std::string, std::string)返回一个std::string_helper。该对象的作用就是将实际的连接延迟到它被转换为std::string的时刻。显然,operator+(std::string_helper, std::string)也应该被定义为返回相同的helper,它将“记住”它有一个额外的连接要执行。
这样的行为可以节省创建n-1个临时对象、分配它们的缓冲区、复制它们等CPU成本。所以我的问题是:为什么它不已经像这样工作?我想不出任何缺点或限制。

1
最明显的缺点是增加了复杂性。 - PlasmaHH
在C++11中,由于右值引用的存在,临时对象可以被重复利用。 - avakar
4
复杂性对用户来说是隐藏的,因此并不特别糟糕。主要缺点是它引入了隐式的用户定义类型转换,这会破坏依赖于从std::string的隐式转换的现有代码。 - Mike Seymour
@MikeSeymour:这是对所提问题的真正回答。到目前为止,其他答案只是提供了解决方法。 - Benjamin Lindley
1
这个示例代码只使用一个临时变量,进行N次分配和复制,是吗? - Mooing Duck
显示剩余2条评论
6个回答

6

为什么它不能像那样工作?

我只能推测为什么最初是这样设计的。也许字符串库的设计者根本没有想到; 也许他们认为(参见下文)额外的类型转换可能会在某些情况下使行为过于令人惊讶。它是最早的C++库之一,我们所认为的很多智慧在过去几十年中根本不存在。

至于为什么它没有被改成那样工作:这可能会通过添加一个额外的用户定义类型转换破坏现有的代码。隐式转换最多只能涉及一个用户定义转换。这是由C++11,13.3.3.1.2 / 1指定的:

用户定义的转换序列由初始标准转换序列后跟 用户定义的转换 再后跟第二个标准转换序列组成。

考虑以下示例:

struct thingy {
    thingy(std::string);
};

void f(thingy);

f(some_string + another_string);

如果 some_string + another_string 的类型是 std::string,那么这段代码就没有问题。它可以通过转换构造函数隐式转换为 thingy 类型。但是,如果我们改变了 operator+ 的定义以得到另一种类型,那么就需要两次转换(从 string_helperstring 再到 thingy),从而无法编译。
因此,如果字符串构建的速度很重要,你需要使用其他方法,比如使用 += 进行连接。或者按照Matthieu的答案所述,不用担心它,因为C++11以不同的方式解决了效率问题。

2
这种技术在我学习C++(大约1990年)时就已经很出名了,所以我怀疑原因不是原始设计者没有听说过它。更有可能的是,他认为这对于std::string的典型用途来说是不良设计。 - James Kanze
@JamesKanze:好的,我的知识只能回溯到90年代中期,所以我只能推测更早期的发展。 - Mike Seymour
@Mike:但是 std::string_helper 应该有一个隐式转换运算符到 std::string,这样代码编译不就足够了吗? - qdii
@qdii:不行,因为代码已经需要从stringthingy的一个隐式用户定义转换。总体转换不能涉及第二个转换。 - Mike Seymour
@MatthieuM:这基本上与James的答案相同。我会回复你们中能引用标准的人之一 :) - qdii

6
明显的答案是:因为标准不允许。这会通过在某些情况下引入额外的用户定义转换来影响代码:如果C是一个具有接受std::string的用户定义构造函数的类型,则会发生这种情况:
C obj = stringA + stringB;

非法的。

你指的是哪种自定义转换?在这种情况下,std::string_helper 将是属于标准库的一个类。你能否详细说明一下? - qdii
@qdii:即使如此,它仍将被视为用户定义的转换。就编译器而言,标准库的类是常规类(没有魔法)。 - Matthieu M.
@qdii:“用户定义”的意思是“不是语言内置的”;标准库算作“用户”。 - Mike Seymour

4

这要看情况。

在 C++03 中,可能会存在一些轻微的效率问题(类似于 Java 和 C# 中它们使用字符串池)。可以通过以下方式缓解这种情况:

d = std::string("") += a += b +=c;

这并不是真正的...惯用语。

在C++11中,右值引用重载了operator+。这意味着:

d = a + b + c;

转化为:

d.assign(std::move(operator+(a, b).append(c)));

这个版本的C++11几乎达到了最高效的水平。

C++11版本中唯一的低效之处是内存没有在一开始就被完全保留,因此可能会有重新分配和复制(每个新字符串都需要)。然而,由于追加操作是摊销O(1)的,除非C比B要长得多,否则最坏情况下只会发生一次重新分配和复制。当然,我们在这里谈论的是POD复制(所以是一个memcpy调用)。


+1:这很有趣。你说的“附加是摊销O(1)”是什么意思? - qdii
@qdii: Amortized O(1)是算法复杂度分析中使用的术语。它意味着它并不总是O(1)(因为有时附加会触发内存重新分配+复制),但平均而言它是O(1)。这通常通过底层缓冲区的指数增长来完成,因此随着事物的增长,重新分配的次数越来越少。例如,每次需要更多存储空间时将存储空间加倍是一种适当的策略。 - Matthieu M.

2
听起来好像已经有类似的东西了:std::stringstream。只不过你需要用<<代替+。仅仅因为存在std::string::operator +,并不意味着它是最高效的选项。

0

我认为如果你使用+=,那么速度会稍微快一些:

d += a;
d += b;
d += c;

它应该更快,因为它不会创建临时对象。或者简单地说,

d.append(a).append(b).append(c); //same as above: i.e using '+=' 3 times.

@MooingDuck:到底是什么没有更快? - Nawaz
你的帖子中的任何代码都应该比原帖中的代码少12个字节的memcpy。 - Mooing Duck

0
不使用一系列单独的+连接,特别是在循环中这样做的主要原因是它具有O(n2)的复杂度。
一个具有O(n)复杂度的合理替代方案是使用简单的字符串构建器,例如:
template< class Char >
class ConversionToString
{
public:
    // Visual C++ 10.0 has some DLL linking problem with other types:
    CPP_STATIC_ASSERT((
        std::is_same< Char, char >::value || std::is_same< Char, wchar_t >::value
        ));

    typedef std::basic_string< Char >           String;
    typedef std::basic_ostringstream< Char >    OutStringStream;

    // Just a default implementation, not particularly efficient.
    template< class Type >
    static String from( Type const& v )
    {
        OutStringStream stream;
        stream << v;
        return stream.str();
    }

    static String const& from( String const& s )
    {
        return s;
    }
};


template< class Char, class RawChar = Char >
class StringBuilder;


template< class Char, class RawChar >
class StringBuilder
{
private:
    typedef std::basic_string< Char >       String;
    typedef std::basic_string< RawChar >    RawString;
    RawString   s_;

    template< class Type >
    static RawString fastStringFrom( Type const& v )
    {
        return ConversionToString< RawChar >::from( v );
    }

    static RawChar const* fastStringFrom( RawChar const* s )
    {
        assert( s != 0 );
        return s;
    }

    static RawChar const* fastStringFrom( Char const* s )
    {
        assert( s != 0 );
        CPP_STATIC_ASSERT( sizeof( RawChar ) == sizeof( Char ) );
        return reinterpret_cast< RawChar const* >( s );
    }

public:
    enum ToString { toString };
    enum ToPointer { toPointer };

    String const&   str() const             { return reinterpret_cast< String const& >( s_ ); }
    operator String const& () const         { return str(); }
    String const& operator<<( ToString )    { return str(); }

    RawChar const*     ptr() const          { return s_.c_str(); }
    operator RawChar const* () const        { return ptr(); }
    RawChar const* operator<<( ToPointer )  { return ptr(); }

    template< class Type >
    StringBuilder& operator<<( Type const& v )
    {
        s_ += fastStringFrom( v );
        return *this;
    }
};

template< class Char >
class StringBuilder< Char, Char >
{
private:
    typedef std::basic_string< Char >   String;
    String  s_;

    template< class Type >
    static String fastStringFrom( Type const& v )
    {
        return ConversionToString< Char >::from( v );
    }

    static Char const* fastStringFrom( Char const* s )
    {
        assert( s != 0 );
        return s;
    }

public:
    enum ToString { toString };
    enum ToPointer { toPointer };

    String const&   str() const             { return s_; }
    operator String const& () const         { return str(); }
    String const& operator<<( ToString )    { return str(); }

    Char const*     ptr() const             { return s_.c_str(); }
    operator Char const* () const           { return ptr(); }
    Char const* operator<<( ToPointer )     { return ptr(); }

    template< class Type >
    StringBuilder& operator<<( Type const& v )
    {
        s_ += fastStringFrom( v );
        return *this;
    }
};

namespace narrow {
    typedef StringBuilder<char>     S;
}  // namespace narrow

namespace wide {
    typedef StringBuilder<wchar_t>  S;
}  // namespace wide

然后,您可以编写高效明了的代码,例如...

using narrow::S;

std::string a = S() << "The answer is " << 6*7;
foo( S() << "Hi, " << username << "!" );

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接