在C++中，等价于CPython字符串连接的是什么？

Question

在C++中，等价于CPython字符串连接的是什么？

6

可能重复：
简单的字符串拼接

昨天，当我写这篇文章时，有人在SO上问了一个问题。

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方法），这是一个深刻而有趣的问题，涉及到微妙的低级细节、高级算法复杂性考虑，甚至线程！尽管如此，它的表述方式非常简短明了。

我转发原始问题并将其作为自己的问题，因为在它被删除之前我没有机会提供正确的答案，而且我的努力让原始问题重新出现，以便我可以帮助增加对这些问题的普遍理解，都失败了。

我已经将原来的标题“选择Python还是C++”更改为……

C++中等价于CPython字符串连接的方法是什么？

从而缩小了问题的范围。

- Cheers and hth. - Alf

在我看来，那个原始问题应该被恢复（并且在10分钟内可能会被恢复）。 - Blender

当最初提出这个问题时，它的语气是“如何在C++中连接字符串？”，并附有一个Python示例来帮助解释。在C++中，字符串是可变的。按照提问的方式，我认为可变性并不重要。 - chris

@Blender，虽然这很有趣，但这绝不是恢复原始问题的理由。原始问题中没有提到与复杂性相关的问题，更不用说与多线程相关的问题了。如果原始发布者对细节感兴趣，他或她会做出基本准备（例如查找std::string::operator+并询问“它与Python的__add__有何不同？”）。恢复该问题会发送错误的信息。它会邀请人们发送更多那些研究不足、质量低劣、重复、琐碎的问题。 - jogojapan

@chris：你错了。这个问题的原文在这里被引用了。既然你几乎不可能没有注意到这一点，我相信你不是完全诚实的。 - Cheers and hth. - Alf

@jogojapan：关于“原问题中没有提到与复杂性或多线程相关的问题”，如果提问者知道哪些是相关的，那他就不需要问了，对吧？此外，在SO上的答案不应该仅限于读者通过心灵感应猜测提问者的意图。相反，它们应该回答所提出的问题（例如，为了帮助其他人！）。就像克里斯的评论一样，你的评论中存在着明显的逻辑缺失。而且，根据我的阅读理解，由于强调的重点，你的评论也存在着大量的误导。 - Cheers and hth. - Alf

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cheers and hth. - Alf · Accepted Answer

代码片段的一般含义。

给定的代码片段

x = 'wow'
x.__add__( x )

在Python 2.x和Python 3.x中，字符串具有不同的意义。

在Python 2.x中，默认情况下，字符串是窄字符串，每个编码单元占用一个字节，相当于基于C++ char的字符串。

在Python 3.x中，字符串是宽字符串，保证表示Unicode，相当于C++ wchar_t基础字符串的实际用法，并且每个编码单元未指定为2或4个字节。

忽略效率，__add__方法在两个主要Python版本中都表现相同，对应于C++ std::basic_string运算符+（例如适用于std::string和std::wstring），例如引用CPython 3k文档：

object.__add__(self, other)
…用于计算表达式x + y，其中x是具有__add__()方法的类的实例，会调用x.__add__(y)。

例如，CPython 2.7代码：

x = 'wow'
y = x.__add__( x )
print y

通常会被写作

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;
}

与原问题中给出的许多错误答案的主要区别在于，C++对应是一个表达式，而不是更新。

人们可能自然而然地认为方法名__add__表示字符串对象值的更改，即更新，但就Python代码中可以直接观察到的可观察行为而言，Python字符串是不可变字符串。它们的值永远不会改变。这与Java和C#相同，但与C++的可变std::basic_string字符串非常不同。

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

CPython 2.4仅针对狭窄字符串添加了以下优化：

在形如s = s + "abc"和s += "abc"的语句中，字符串拼接在某些情况下现在更加高效。这种优化在其他Python实现（例如Jython）中不存在，因此您不应该依赖它；当您想要高效地将大量字符串粘合在一起时，仍然建议使用字符串的join()方法。（由Armin Rigo贡献。）

虽然听起来不起眼，但在适用的情况下，这种优化可以将拼接序列从二次时间复杂度O(n^2)降为线性时间复杂度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的更新赋值来更新对象，因为没有观察者。同样，也适用于追加c。

这有点像量子力学：你无法观察到这种肮脏的事情正在发生，只有在没有任何人观察机制的情况下才会完成，但是你可以通过收集性能统计数据来推断它一定已经发生了，因为线性时间与二次时间完全不同！

使用什么方法实现线性时间？好吧，可以使用与C++ std::basic_string相同的缓冲区加倍策略进行更新，这意味着每次缓冲区重新分配时只需要复制现有缓冲区内容，而不是每次追加操作都要复制。这意味着复制的总成本最坏情况下是最终字符串大小的线性，就像总和（表示每次缓冲区加倍复制的成本）1 + 2 + 4 + 8 + … + N 小于2*N一样。

在C++中实现线性时间字符串连接表达式。

为了忠实地复制CPython代码片段到C++中，

应该捕获操作的最终结果和表达式特性，
还应该捕获其性能特征！

直接将CPython的__add__翻译为C++的std::basic_string + 会导致无法可靠地捕获CPython的线性时间。C++的+字符串连接可能会像CPython优化一样被编译器优化。也可能不会-这意味着你已经告诉一个初学者，Python线性时间操作的C++等效操作是具有二次时间复杂度的东西-嘿，这就是你应该使用的...

对于性能特征，C+++=是基本答案，但是，它无法捕捉Python代码的表达式特性。

自然的答案是一个线性时间的C++字符串构建器类，它将连接表达式转换为一系列+=更新，以便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.
}