如果可能，总是更喜欢 std::string(ptr, size) 而不是 std::string(first, last)？

Question

考虑：

#include <string>
#include <string_view>

using namespace std;

string sv2s_1(string_view sv)
{
    return string(sv.data(), sv.size());
}

string sv2s_2(string_view sv)
{
    return string(sv.begin(), sv.end());
}

在sv2s_1中，string需要最多分配一次内部缓冲区。

在sv2s_2中，string不知道内部缓冲区应该有多大，所以它必须一个一个地推回字符，并且可能会多次重新分配和复制内部缓冲区.

前提是first和last是随机访问迭代器,string(first, last)可以使用last - first 快速获取其内部缓冲区的大小，因此性能等于 string(ptr, size).

问题：如果first和last是随机访问迭代器，

C++标准是否保证string(first, last)等价于string(ptr, size)性能？

Answer 1

std::basic_string's doc 保证以下两个构造函数的复杂度为线性：

constexpr basic_string( const CharT* s,
                        size_type count,
                        const Allocator& alloc = Allocator() ); // (4)

template< class InputIt >
constexpr basic_string( InputIt first, InputIt last,
                        const Allocator& alloc = Allocator() ); // (6)

虽然性能不是保证，也不应该使用另一个来实现。

注意：采用迭代器的构造函数 (6) 采用 InputIterator，而不是 RandomIterator（即使实现可能会在迭代器类别上分派）。

Answer 2

我在标准中没有看到这样的要求。 X(i, j) 构造一个等于范围 [i, j) 的序列容器的标准 says 并且表达式的复杂度取决于序列。

查看特定实现，libstdc++ precomputes 前向、双向和随机访问迭代器的范围大小：

template<typename InIterator>
void basic_string<CharT, Traits, Alloc>::
_M_construct(InIterator beg, InIterator end, std::forward_iterator_tag) {
    // ...
    size_type dnew = static_cast<size_type>(std::distance(beg, end));
    // ...
}

注意 std::bidirectional_iterator_tag 和 std::random_access_iterator_tag are derived 来自 std::forward_iterator_tag，并且可以隐式转换成它，所以这个 _M_construct 重载被调用 forward 、双向和随机访问迭代器（以及 C++20 中的连续迭代器）。

如果可能，总是更喜欢 std::string(ptr, size) 而不是 std::string(first, last)？

Always prefer std::string(ptr, size) to std::string(first, last) if possible?

c++

string

performance

standards

time-complexity