2

我编写了以下字符串连接函数 ( join) 以减少分配次数和构造最终字符串所花费的时间。我还想编写一个易于使用的附加函数（如果可能的话，单行）。

size_t str_size(const char *str) {
    return std::strlen(str);
}

size_t str_size(const std::string &str) {
    return str.size();
}

template <typename T>
size_t accumulated_size(const T& last) {
    return str_size(last);
}

template <typename T, typename... Args>
size_t accumulated_size(const T& first, const Args& ...args) {
    return str_size(first) + accumulated_size(args...);
}

template <typename T>
void append(std::string& final_string, const T &last) {
    final_string += last;
}

template <typename T, typename... Args>
void append(std::string& final_string, const T& first, const Args& ...args) {
    final_string += first;
    append(final_string, args...);
}

template <typename T, typename... Args>
std::string join(const T& first, const Args& ...args) {
    std::string final_string;

    final_string.reserve(accumulated_size(first, args...));
    append(final_string, first, args...);

    return std::move(final_string);
}

我在相当大量的字符串上使用类的和测试了join针对典型内置 C++ 连接功能的方法。与普通或方法相比，我的方法如何以及为什么在时间执行方面产生更差的结果？operator+=operator+std::stringoperator+=operator+

我正在使用以下类来测量时间：

class timer {
public:
    timer() {
        start_ = std::chrono::high_resolution_clock::now();
    }

    ~timer() {
        end_ = std::chrono::high_resolution_clock::now();
        std::cout << "Execution time: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_ - start_).count() << " ns." << std::endl;
    }

private:
    std::chrono::time_point<std::chrono::high_resolution_clock> start_;
    std::chrono::time_point<std::chrono::high_resolution_clock> end_;
};

我正在比较以下方式：

#define TEST_DATA "Lorem", "ipsum", "dolor", "sit", "ame", "consectetuer", "adipiscing", "eli", "Aenean",\
                    "commodo", "ligula", "eget", "dolo", "Aenean", "mass", "Cum", "sociis", "natoque",\
                    "penatibus", "et", "magnis", "dis", "parturient", "monte", "nascetur", "ridiculus",\
                    "mu", "Donec", "quam", "feli", ", ultricies", "ne", "pellentesque", "e", "pretium",\
                    "qui", "se", "Nulla", "consequat", "massa", "quis", "eni", "Donec", "pede", "just",\
                    "fringilla", "ve", "aliquet", "ne", "vulputate", "ege", "arc", "In", "enim", "just",\
                    "rhoncus", "u", "imperdiet", "", "venenatis", "vita", "just", "Nullam", "ictum",\
                    "felis", "eu", "pede", "mollis", "pretiu", "Integer", "tincidunt"

#define TEST_DATA_2 std::string("Lorem") + "ipsum"+ "dolor"+ "sit"+ "ame"+ "consectetuer"+ "adipiscing"+ "eli"+ "Aenean"+\
                    "commodo"+ "ligula"+ "eget"+ "dolo"+ "Aenean"+ "mass"+ "Cum"+ "sociis"+ "natoque"+\
                    "penatibus"+ "et"+ "magnis"+ "dis"+ "parturient"+ "monte"+ "nascetur"+ "ridiculus"+\
                    "mu"+ "Donec"+ "quam"+ "feli"+ ", ultricies"+ "ne"+ "pellentesque"+ "e"+ "pretium"+\
                    "qui"+ "se"+ "Nulla"+ "consequat"+ "massa"+ "quis"+ "eni"+ "Donec"+ "pede"+ "just"+\
                    "fringilla"+ "ve"+ "aliquet"+ "ne"+ "vulputate"+ "ege"+ "arc"+ "In"+ "enim"+ "just"+\
                    "rhoncus"+ "u"+ "imperdiet"+ ""+ "venenatis"+ "vita"+ "just"+ "Nullam"+ "ictum"+\
                    "felis"+ "eu"+ "pede"+ "mollis"+ "pretiu"+ "Integer"+ "tincidunt"

int main() {
    std::string string_builder_result;
    std::string normal_approach_result_1;
    std::string normal_approach_result_2;

    {
        timer t;
        string_builder_result = join(TEST_DATA);
    }

    std::vector<std::string> vec { TEST_DATA };
    {
        timer t;
        for (const auto & x : vec) {
            normal_approach_result_1 += x;
        }
    }

    {
        timer t;
        normal_approach_result_2 = TEST_DATA_2;
    }
}

我的结果是：

  • 执行时间：11552 ns（join接近）。
  • 执行时间：3701 ns（operator+=()接近）。
  • 执行时间：5898 ns（operator+()接近）。

我正在编译：g++ efficient_string_concatenation.cpp -std=c++11 -O3

4

2 回答 2

4

operator+左侧有一个右值引用std::string。您编写的+=代码从根本上来说并不比一长串+.

它+可以使用指数重新分配，从 10 左右开始。增长因子为 1.5，即大约 9 次分配和重新分配。

递归可能会使事情变得混乱或减慢速度。你可以解决这个问题：

template <typename... Args>
void append(std::string& final_string, const Args&... args) {
  using unused=int[];
  (void)unused{0,(void(
    final_string += args
  ),0)...};
}

这消除了递归，类似地：

template <typename... Args>
size_t accumulated_size(const Args& ...args) {
  size_t r = 0;
  using unused=int[];
  (void)unused{0,(void(
    r += str_size(args)
  ),0)...};
  return r;
}

但是，可能不值得访问那么多字符串来计算它们的长度以节省 8 次重新分配。

于 2017-09-06T14:46:20.310 回答
-1

请不要为此处理字符串。

使用字符串流，或者像这样创建自己的 StringBuilder：https ://www.codeproject.com/Articles/647856/Performance-Improvement-with-the-StringBuilde

推荐使用专门的字符串构建器，因为它具有智能分配管理（有时它们支持字符串块列表，有时 - 预测增长）。分配是困难且非常耗时的操作。

于 2017-09-06T14:26:02.597 回答