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

Question

可能重复:
简单字符串连接

昨天,在我写这篇文章时,有人问道

如果我有一个字符串x='wow' 应用addpython中的函数:

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

我怎么能用C++做到这一点？

将add(不存在的)修正为__add__(标准方法)这是一个深刻而有趣的问题,涉及微妙的低级细节,高级算法复杂性考虑,甚至线程!,但它的制定时间非常短简洁的方式.

我将原来的问题 作为我自己的问题重新发布 ,因为我没有机会在删除之前提供正确答案,并且我努力恢复原来​​的问题,以便我可以帮助增加对这些问题的一般理解,失败.

我把原来的标题"select python or C++"改为......

• 在C++中,CPython字符串连接的等价物是什么？

从而缩小了一点问题.

Answer 1

代码段的一般含义.

给定的代码段

x = 'wow'
x.__add__( x )

在Python 2.x和Python 3.x中有不同的含义.

在Python 2.x中,字符串默认为窄字符串,每个编码单元一个字节,对应于char基于C++ 的字符串.

在Python 3.x中,字符串是宽字符串,保证代表Unicode,对应于wchar_t基于C++ 的字符串的实际使用 ,同样每个编码单元具有未指定的2或4字节.

忽略效率,该__add__方法在两个主要Python版本中的行为相同,对应于C++ +运算符std::basic_string (即for 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提供.)

它可能听起来不是很多,但是在适用的情况下,这种优化在最终结果的长度n中减少了从二次时间 O(n ²)到线性时间 O(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保留对该对象的引用.这意味着可以通过追加的更新分配来更新对象,因为没有观察者.同样也适用于.bc

这有点像量子力学:你无法观察到这种肮脏的事情发生,并且当有可能有人观察到这些阴谋时它永远不会被完成,但是你可以推断出你收集的关于性能的统计数据肯定会发生这种情况. ,线性时间与二次时间有很大不同!

如何实现线性时间？好吧,通过更新,std::basic_string可以完成与C++相同的缓冲加倍策略,这意味着现有缓冲区内容只需要在每次缓冲区重新分配时复制,而不是每次追加操作.这意味着复制的 总成本在最终字符串大小中处于最差线性,与总和相同(表示在每个缓冲区复制的成本加倍)1 + 2 + 4 + 8 + ... + N小于2*N.

C++中的线性时间字符串连接表达式.

为了忠实地再现C++中的CPython代码片段,

• 应该捕捉到最终结果和表达性质,

• 并且应该捕获它的性能特征!

将CPython直接转换__add__为C++ std::basic_string +无法可靠地捕获CPython线性时间.C++ +字符串连接 可以由编译器以与CPython优化相同的方式进行优化.或者不是 - 这意味着一个人告诉初学者C++相当于Python线性时间操作,是二次时间的东西 - 嘿,这是你应该使用的...

对于性能特征,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.
}