串联和压缩std :: vector

问题描述 投票:1回答:4
的最佳方法

Disclaimer:这个问题更多是理论上的,而不是实际上的。我想找出各种不同的方式来做到这一点,并以速度为新年蛋糕锦上添花。

问题

我希望能够存储字符串列表,并能够根据需要将它们快速组合为1。简而言之,我想压缩一个看起来像

的结构(当前为std::vector<std::string>
["Hello, ", "good ", "day ", " to", " you!"]

to

["Hello, good day to you!"]
  • 有没有惯用的方法来实现这一点,比如ala python的[ ''.join(list_of_strings) ]
  • 就时间而言,用C ++实现此目标的最佳方法是什么?

可能的方法

我首先想到的是

  • 循环到向量,
  • 将每个元素附加到第一个,
  • 同时删除该元素。

We will be concatenating with += and reserve()。我认为+=

方法1(贪婪方法)

之所以这样称呼,是因为它忽略了约定并就地运行。

reserve()

现在我知道,您会说这是冒险且不好的。因此:

方法2(“避风港”)

之所以这样称呼,是因为它在迭代容器时不会修改容器。

max_size()

但是,也许我们可以使用另一个容器而不是// Save as greedy_approach.cpp #include <iostream> #include <vector> int main() { // Our test object, with 5 strings std::vector< std::string > my_strings = { "Hello, ", "good ", "day ", "to ", "you!" }; // Suppose already calculated / known int total_characters_in_list = 7 + 5 + 4 + 3 + 4; // Reserve the size for all characters, less than max_size() my_strings[0].reserve(total_characters_in_list); // There are strings left, ... for(auto itr = my_strings.begin()+1; itr != my_strings.end();) { // append, and... my_strings[0] += *itr; // delete, until... my_strings.erase(itr); } // Just to check it's success. std::cout << my_strings[0]; return 0; }

在那种情况下,还有什么?

(可能)方法3(伟大的印度“绳子”把戏)

我听说过std::string,但不知道是否可以(以及如何)在这里使用它。


基准和判决:

按其时间效率(当前和令人惊讶的顺序)是:

// Save as safe_haven.cpp
#include <iostream>
#include <vector>

int main()
{
    // Our test object, with 5 strings
    std::vector< std::string > my_strings = { "Hello, ", "good ", "day ", "to ", "you!" };
    // Suppose already calculated / known
    int total_characters_in_list = 7 + 5 + 4 + 3 + 4;
    // Store the whole vector here
    std::string condensed_string;
    condensed_string.reserve(total_characters_in_list);

    // There are strings left...
    for(auto itr = my_strings.begin(); itr != my_strings.end(); ++itr)
    {
        // append, until...
        condensed_string += *itr;
    }
    // remove all elements except the first
    my_strings.resize(1);
    // and set it to condensed_string
    my_strings[0] = condensed_string;

    // Just to check it's success.
    std::cout << my_strings[0];
    return 0;
}

定时:

std::vector

我们能做得更好吗?

c++ string performance time
4个回答
0
投票

默认情况下,我会使用rope data structure。只需构造蒸汽,从向量中的所有字符串中输入流,然后返回输出字符串即可。它不是很有效,但是很清楚它的作用。

[在大多数情况下,在处理字符串和打印时不需要快速方法-因此,“易于理解和安全”的方法更好。另外,当今的编译器擅长在简单情况下优化效率低下的问题。

最有效的方法...这是一个很难的问题。一些应用需要多方面的效率。在这些情况下,您可能需要利用多线程。


0
投票

使用safe_haven: 0.13684312179998959 greedy_approach: 0.1369105681000074 (很快使用NUM_OF_ITERATIONS = 100 test_cases = [ 'greedy_approach', 'safe_haven' ] for approach in test_cases: time_taken = timeit.timeit( f'system("{approach + ".exe"}")', 'from os import system', number = NUM_OF_ITERATIONS ) print(approach + ": ", time_taken / NUM_OF_ITERATIONS) ),您可以这样做:

std::stringstream

range-v3


0
投票

就我个人而言,我将构造第二个向量以容纳单个“压缩”字符串,构造该压缩字符串,然后在完成后交换向量。

C++20 ranges

[如果由于某种原因引发了异常,则原始向量将保持不变,并进行清除-即,此函数提供了强大的异常保证。

可选地,为减小“压缩的”字符串的大小,在上面初始化std::vector<std::string> v{"Hello, ", "good ", "day ", " to", " you!"}; std::string s = v | ranges::view::join; 后,可以这样做

Demo

关于将其与替代方法进行比较的效率,这取决于。我也不确定它是否相关-如果将字符串继续添加到向量中并需要添加,则很有可能从某个地方获取字符串(并将它们附加到向量中)的代码中都有一个对程序性能的影响大于将其压缩的行为。


0
投票

您也可以尝试 void Condense(std::vector<std::string> &strings) { std::vector<std::string> condensed(1); // one default constructed std::string std::string &constr = &condensed.begin(); // reference to first element of condensed for (const auto &str : strings) constr.append(str); std::swap(strings, condensed); // swap newly constructed vector into original }

constr

不会更快,但是至少它更紧凑。

© www.soinside.com 2019 - 2024. All rights reserved.