c++ - 使用标准模板库中的堆栈

Question

我只是编写了一个小程序来将一个字符从字符串转移到堆栈上并打印它的最高值。它们只是简单的代码，但概念不同，请问哪一种代码效率更高，为什么？

第一个代码

#include<string>
#include<iostream>
#include<stack>
using namespace std;
int main(){
   string str ;
   stack<char> s;
   cin >> str ;
   for(int i=0;i<str.size();i++){
       cout << str[i] << "\n";
       s.push(str[i]);
       cout << "Top of the stack " << s.top() << endl;}
 cout << "\n" << endl;
 return 0;}

第二个代码使用迭代器

#include<string>
#include<iostream>
#include<stack>
using namespace std;
int main(){
   string str ;
   stack<char> s;
   cin >> str ;
   for(string::iterator itr = str.begin();itr!=str.end();itr++){
             cout << *itr << "\n";
             s.push(*itr);
             cout << "Top of the stack " << s.top() << endl;}
 cout << "\n" << endl;
 return 0;}

它们只是两个简单的代码，我只想知道哪种方法更有效？？

Answer 1

如果以方法做多少基本操作来定义效率，我相信这两种方法没有区别。如您所知，std::string 的实现基于简单的字符数组(就像 std::vector)，这意味着字符存储为连续的内存块。这允许在恒定数量的操作中访问有效范围内的任何元素(O(1))。因此，检索第 i 个字符 str[i] 需要 O(1) 操作，就像访问数组的条目一样。同样，在第二种方法中，您使用迭代器，粗略地说，迭代器是指向此上下文中数组中位置的指针。因此，访问它们的内容 *itr 并将它们进一步移动一个位置 itr++ 与沿 array 移动指针并检索它的效率相同内容。

因此，关键思想是 std::string 中的字符存储在连续数组中，这赋予了它这种能力。您可能希望将其实现与 std::map 进行比较，其中底层实现是一个红黑树，当然，它不是一个数组。因此 [] 运算符以对数时间运行(与 std::string 中的常数相反)。

编辑:

如评论中所述，cout 输出的成本相对较高(但仍为 O(1))。因此，如果您想检查“真实”效率，则必须在程序启动时删除输出或调用 std::ios_base::sync_with_stdio(false); 以提高 的速度cout.