3 
std::string Concatenate(const std::string& s1,
                        const std::string& s2,
                        const std::string& s3,
                        const std::string& s4,
                        const std::string& s5)
{
    return s1 + s2 + s3 + s4 + s5;
}

默认情况下，return s1 + s2 + s3 + s4 + s5;可能等价于以下代码：

auto t1 = s1 + s2; // Allocation 1
auto t2 = t1 + s3; // Allocation 2
auto t3 = t2 + s4; // Allocation 3

return t3 + s5; // Allocation 4

有没有一种优雅的方法可以将分配时间减少到 1？我的意思是保持return s1 + s2 + s3 + s4 + s5;不变，但效率会自动提高。如果可能的话，也可以避免程序员误用std::string::operator +.

ref-qualifier成员函数有帮助吗？

4

6 回答 6

12

问题的前提是：

s1 + s2 + s3 + s4 + s5 + ... + sn

将需要 n 个分配不正确。

相反，它将需要 O(Log(n)) 分配。第一个s1 + s1会生成一个临时的。随后一个临时（右值）将成为所有后续+操作的左参数。该标准规定，当 a 的 lhsstring +是右值时，实现只需附加到该临时值并将其移出：

operator+(basic_string<charT,traits,Allocator>&& lhs,
          const basic_string<charT,traits,Allocator>& rhs);

Returns: std::move(lhs.append(rhs))

该标准还规定字符串的容量将呈几何级数增长（1.5 到 2 之间的系数很常见）。因此，在每次分配时，容量都会以几何级数增长，并且容量会沿着操作链向下传播+。更具体地说，原始代码：

s = s1 + s2 + s3 + s4 + s5 + ... + sn;

实际上相当于：

s = s1 + s2;
s += s3;
s += s4;
s += s5;
// ...
s += sn;

当几何容量增长与短串优化相结合时，“预先保留”正确容量的价值是有限的。如果此类代码实际上在您的性能测试中显示为热点，我只会费心去做。

于 2014-09-10T00:49:21.457 回答
7 
std::string combined;
combined.reserve(s1.size() + s2.size() + s3.size() + s4.size() + s5.size());
combined += s1;
combined += s2;
combined += s3;
combined += s4;
combined += s5;
return combined;
于 2014-09-10T00:04:54.320 回答
4

没有像过度工程这样的工程。

在这种情况下，我创建了一个类型string_builder::op<?>，该类型可以合理有效地收集一堆要连接的字符串，并在转换为std::string收益时这样做。

它存储提供的任何临时 s 的副本std::string，以及对寿命更长的 s 的引用，作为一种偏执狂。

它最终减少到：

std::string retval;
retval.reserve(the right amount);
retval+=perfect forwarded first string
...
retval+=perfect forwarded last string
return retval;

但它用大量的语法糖来包装它。

namespace string_builder {
  template<class String, class=std::enable_if_t< std::is_same< String, std::string >::value >>
  std::size_t get_size( String const& s ) { return s.size(); }
  template<std::size_t N>
  constexpr std::size_t get_size( const char(&)[N] ) { return N; }
  template<std::size_t N>
  constexpr std::size_t get_size( char(&)[N] ) { return N; }
  std::size_t get_size( const char* s ) { return std::strlen(s); }
  template<class Indexes, class...Ss>
  struct op;
  struct tuple_tag {};
  template<size_t... Is, class... Ss>
  struct op<std::integer_sequence<size_t, Is...>, Ss...> {
    op() = default;
    op(op const&) = delete;
    op(op&&) = default;
    std::tuple<Ss...> data;
    template<class... Tuples>
    op( tuple_tag, Tuples&&... ts ): data( std::tuple_cat( std::forward<Tuples>(ts)... ) ) {}
    std::size_t size() const {
      std::size_t retval = 0;
      int unused[] = {((retval+=get_size(std::get<Is>(data))), 0)..., 0};
      (void)unused;
      return retval;
    }
    operator std::string() && {
      std::string retval;
      retval.reserve( size()+1 );
      int unused[] = {((retval+=std::forward<Ss>(std::get<Is>(data))), 0)..., 0};
      (void)unused;
      return retval;
    }
    template<class S0>
    op<std::integer_sequence<size_t, Is..., sizeof...(Is)>, Ss..., S0>
    operator+(S0&&s0)&& {
      return { tuple_tag{}, std::move(data), std::forward_as_tuple( std::forward<S0>(s0) ) };
    }
    auto operator()()&& {return std::move(*this);}
    template<class T0, class...Ts>
    auto operator()(T0&&t0, Ts&&... ts)&&{
      return (std::move(*this)+std::forward<T0>(t0))(std::forward<Ts>(ts)...);
    }
  };
}
string_builder::op< std::integer_sequence<std::size_t> >
string_build() { return {}; }

template<class... Strings>
auto
string_build(Strings&&...strings) {
  return string_build()(std::forward<Strings>(strings)...);
}

现在我们得到：

std::string Concatenate(const std::string& s1,
                        const std::string& s2,
                        const std::string& s3,
                        const std::string& s4,
                        const std::string& s5)
{
  return string_build() + s1 + s2 + s3 + s4 + s5;
}

或更通用和有效的：

template<class... Strings>
std::string Concatenate(Strings&&...strings)
{
  return string_build(std::forward<Strings>(strings)...);
}

有无关的动作，但没有无关的分配。它适用于 raw"strings"没有额外的分配。

活生生的例子

于 2014-09-10T01:40:27.757 回答
1

您可以使用如下代码：

std::string(s1) + s2 + s3 + s4 + s5 + s6 + ....

这将分配一个未命名的临时（第一个字符串的副本），然后将每个其他字符串附加到它。智能优化器可以将其优化为与其他人发布的 Reserve+append 代码相同的代码，因为所有这些函数通常都是可内联的。

这通过使用 operator+ 的移动增强版本来工作，它被定义为（大致）

std::string operator+(std::string &&lhs, const std::string &rhs) {
    return std::move(lhs.append(rhs));
}

与 RVO 结合使用，意味着string不需要创建或销毁额外的对象。

于 2014-09-10T00:19:01.037 回答
0

经过一番思考，我认为至少考虑一种稍微不同的方法可能是值得的。

std::stringstream s;

s << s1 << s2 << s3 << s4 << s5;
return s.str();

虽然它不能保证只分配一次，但我们可以预期 astringstream会针对累积相对大量的数据进行优化，所以很有可能（除非输入字符串很大）它将保持分配的数量非常少。

同时，特别是如果单个字符串相当小，它肯定会避免我们期望的情况，例如a + b + c + d在哪里（至少在 C++03 中）我们期望看到在处理过程中创建和销毁的一些临时对象评估表达式。事实上，我们通常可以期望这会得到与表达式模板之类的结果几乎相同的结果，但复杂性要低得多。

但是有一些缺点：iostreams（通常）有足够的包袱，比如相关的语言环境，特别是如果字符串很小，创建流的开销可能比我们在单独分配中节省的开销更大。

使用当前的编译器/库，我希望创建流的开销会使其变慢。对于较旧的实现，我必须进行测试才能完全确定（而且我没有足够旧的编译器来做这件事）。

于 2014-09-10T00:05:21.657 回答
0

这个怎么样：

std::string Concatenate(const std::string& s1,
                        const std::string& s2,
                        const std::string& s3,
                        const std::string& s4,
                        const std::string& s5)
{
    std::string ret;
    ret.reserve(s1.length() + s2.length() + s3.length() + s4.length() + s5.length());
    ret.append(s1.c_str());
    ret.append(s2.c_str());
    ret.append(s3.c_str());
    ret.append(s4.c_str());
    ret.append(s5.c_str());
    return ret;
}

有两种分配，一种非常小，用于构造std::string另一种为数据保留内存。

于 2014-09-15T08:24:51.200 回答