与C++中的cPython字符串连接等价的是什么？

Question

Possible Duplicate:
Simple string concatenation

昨天，在我写这篇文章的时候，有人这样问我

if i have a string x='wow' applying the function add in python :

x='wow'
x.add(x)
'wowwow'

how can i do that in C++?

将add（不存在）修改为__add__（一个标准 方法）这是一个深刻而有趣的问题，涉及到微妙的低 级别详细信息、高级算法复杂性考虑因素，以及 连线都穿！，但它的表述方式非常简洁。在

我在重贴 the original question 因为我自己没有机会提供正确的 在它被删除之前回答，我努力使原来的问题恢复，所以 我认为我可以帮助增加对这些问题的普遍理解，但失败了。在

< >我把原来的标题“选择Python或C++”改为…

C++中的cPython字符串连接是等价的？在

这样就把问题缩小了一点。在

Answer 1

代码片段的一般含义

给定的代码段

x = 'wow'
x.__add__( x )

在python2.x和python3.x中有不同的含义

在Python2.x中，字符串默认为窄字符串，每个编码单元有一个字节， 对应于C++ +{{CD1}}的字符串。在

在python3.x中，字符串是宽字符串，保证代表Unicode， 对应于C++的实际使用 ^基于{}的字符串，并且同样使用未指定的2或4个字节 每个编码单元。在

不考虑效率，__add__方法在两个主要方面表现相同 Python版本，对应于C++ {^ std::string和std::wstring），例如引用CPython 3k documentation：

object.__add__(self, other)
… to evaluate the expression x + y, where x is an instance of a class that has an __add__() method, x.__add__(y) is called.

例如，cpython2.7代码

^{pr2}$

通常写为

x = 'wow'
y = x + x
print y

对应于C++代码：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    auto const x = string( "wow" );
    auto const y = x + x;
    cout << y << endl;
}

一个主要的区别是许多错误的答案 the original question， C++对应是一个E-EM>表达式EEM>，而不是更新EME>。在

可能很自然地认为方法名__add__表示更改 字符串对象值的更新，但与可观察到的 行为Python字符串是不可变的字符串。他们的价值观永远不会改变 在Python代码中可以直接观察到。这与Java和 C，但是非常不同于C++的可变^ ^ {CD5}}字符串。在

CPython中的二次到线性时间优化

添加了CPython 2.4 the following 优化，仅适用于窄字符串：

String concatenations in statements of the form s = s + "abc" and s += "abc" are now performed more efficiently in certain circumstances. This optimization won't be present in other Python implementations such as Jython, so you shouldn't rely on it; using the join() method of strings is still recommended when you want to efficiently glue a large number of strings together. (Contributed by Armin Rigo.)

听起来可能不多，但在适用的情况下，这种优化 从二次时间O（n²）减少一个串联序列 到线性时间O（n），长度为最终结果的n。在

首先，优化用更新替换连接，例如

x = x + a
x = x + b
x = x + c

或者为了这个问题

x = x + a + b + c

被替换为

x += a
x += b
x += c

在一般情况下，会有许多对字符串对象的引用x 因为Python字符串对象必须看起来是不可变的，所以第一个 无法更改该对象的字符串赋值。因此，总的来说，它有 创建一个全新的字符串对象，并将该（引用）分配给x。在

此时，x持有对该对象唯一的引用。也就是说 对象可以通过附加b的update赋值进行更新，因为 没有观察员。对c的追加也是如此。在

这有点像量子力学：你不能观察到这个肮脏的东西 如果有人能观察到，那就永远也做不到 但你可以根据统计数据推断出 你收集关于性能的信息，因为线性时间和二次时间是完全不同的！在

如何实现线性时间？好吧，用同样的缓冲策略 在C++ +^ {CD5> }中可以加倍，这意味着 现有的缓冲区内容只需要在每次缓冲区重新分配时复制， 而不是每次追加操作。也就是说 复制的总成本在最终字符串大小中是最差的线性的 与总和相同（表示每个缓冲区复制的成本加倍） 1+2+4+8+…+N小于2*N

< H2> C++中的线性时间串连接表达式

为了忠实地复制C++中的cPython代码片段，

• 应捕获操作的最终结果和表达式性质，

• 同时也要抓住它的性能特点！

一个Cpththon ^ {CD3>}的直接转换为C++ +{}{{CD4}}失败 可靠地捕获CPython线性时间。C++ ^ {< CD4}}字符串级联 编译器可以用与CPython相同的方式优化 优化。或者没有，这意味着你已经告诉初学者 一个Python线性时间运算的C++等价物是具有二次性的 时间-嘿，这是你应该用的

对于性能特性，C++ +{}是基本的答案，但是，这确实是 不能捕捉Python代码的表达式性质。在

自然的答案是一个线性时间C++ +String > String Builder <强>类 一个连接表达式到一系列的+=更新，以便Python代码

from __future__ import print_function

def foo( s ):
    print( s )

a = 'alpha'
b = 'beta'
c = 'charlie'
foo( a + b + c )    # Expr-like linear time string building.

大致相当于

#include <string>
#include <sstream>

namespace my {
    using std::string;
    using std::ostringstream;

    template< class Type >
    string stringFrom( Type const& v )
    {
        ostringstream stream;
        stream << v;
        return stream.str();
    }

    class StringBuilder
    {
    private:
        string      s_;

        template< class Type >
        static string fastStringFrom( Type const& v )
        {
            return stringFrom( v );
        }

        static string const& fastStringFrom( string const& s )
        { return s; }

        static char const* fastStringFrom( char const* const s )
        { return s; }

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

        string const& str() const { return s_; }
        char const* cStr() const { return s_.c_str(); }

        operator string const& () const { return str(); }
        operator char const* () const { return cStr(); }
    };
}  // namespace my

#include <iostream>
using namespace std;
typedef my::StringBuilder S;

void foo( string const& s )
{
    cout << s << endl;
}

int main()
{
    string const    a   = "alpha";
    string const    b   = "beta";
    string const    c   = "charlie";

    foo( S() << a << b << c );      // Expr-like linear time string building.
}