字符串反转算法对比

发表于 | 分类于

原地字符串反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
// #include <algorithm>
using namespace std;

int main() {
    int input = 0;
    cin >> input;
    string str = to_string(input);
    // reverse(str.begin(), str.end());
    auto first = str.begin();
    auto last = str.end();
    while (first != last && first != --last) {
        std::iter_swap(first, last);
        first++;
    }
    cout << str;
}

从后往前重新构造字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;

int main() {
    int input = 0;
    cin >> input;
    string str = to_string(input);
    string ret;
    for (int i = str.size() - 1; i >= 0; i--) {
        ret += str[i];
    }
    cout << ret;
}

总结

最容易想到的就是从后往前重新构造字符串，重新构建字符串的过程会涉及多次扩容操作

无论std::string 变量存储在栈上或堆上，它的底层字符数据存储在堆上。

下面是 std::string 类型的 operator+ 操作符的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Modifiers:
/**
       *  @brief  Append a string to this string.
       *  @param __str  The string to append.
       *  @return  Reference to this string.
       */
basic_string&
operator+=(const basic_string& __str)
{ return this->append(__str); }

/**
       *  @brief  Append a C string.
       *  @param __s  The C string to append.
       *  @return  Reference to this string.
       */
basic_string&
operator+=(const _CharT* __s)
{ return this->append(__s); }

/**
       *  @brief  Append a character.
       *  @param __c  The character to append.
       *  @return  Reference to this string.
       */
basic_string&
operator+=(_CharT __c)
{
    this->push_back(__c);
    return *this;
}

string::append源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
*  @brief  Append a string to this string.
*  @param __str  The string to append.
*  @return  Reference to this string.
*/
basic_string&
append(const basic_string& __str)
{ return _M_append(__str._M_data(), __str.size()); }

template<typename _CharT, typename _Traits, typename _Alloc>
    basic_string<_CharT, _Traits, _Alloc>&
    basic_string<_CharT, _Traits, _Alloc>::
    _M_append(const _CharT* __s, size_type __n)
    {
      const size_type __len = __n + this->size();

      if (__len <= this->capacity())
	{
	  if (__n)
	    this->_S_copy(this->_M_data() + this->size(), __s, __n);
	}
      else
	this->_M_mutate(this->size(), size_type(0), __s, __n);

      this->_M_set_length(__len);
      return *this;
    }

由此可见，重新构建字符串的过程会涉及多次扩容操作

故使用原地反转算法效率会高

这里想到了使用reverse预先分配容量，避免多次扩容，与vector::reverse同理

使用reverse后与原地反转相比哪个效率高呢？？？

哈哈哈这里我感觉效率差不多

std::string reverse用法

使用 reserve() 函数预先分配容量，避免多次扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// string::reserve
#include <iostream>
#include <fstream>
#include <string>

int main ()
{
  std::string str;

  std::ifstream file ("test.txt",std::ios::in|std::ios::ate);
  if (file) {
    std::ifstream::streampos filesize = file.tellg();
    str.reserve(filesize);

    file.seekg(0);
    while (!file.eof())
    {
      str += file.get();
    }
    std::cout << str;
  }
  return 0;
}

std::swap和std::iter_swap

C++中，std::swap和std::iter_swap是两个用于交换值的函数，但它们的使用场景和功能略有不同。

### std::swap:

- 功能：std::swap用于交换两个值。

- 用法：std::swap接受两个参数，通过引用将它们交换。

- 示例：

1
2
3
4
int a = 5;
int b = 10;
std::swap(a, b);
// 现在a为10，b为5

### std::iter_swap:

- 功能：std::iter_swap用于交换迭代器指向的两个元素的值。

- 用法：std::iter_swap接受两个迭代器作为参数，交换它们指向的值。

- 示例：

1
2
3
4
5
std::vector<int> vec = {1, 2, 3, 4};
auto it1 = vec.begin() + 1;
auto it2 = vec.begin() + 2;
std::iter_swap(it1, it2);
// 现在vec为 {1, 3, 2, 4}

在使用上，std::swap更适用于普通值的交换，而std::iter_swap更适用于需要交换容器中元素的迭代器。

作者：张泽中