使用标准模板库中的堆栈

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;}

第二个代码使用Iterator

#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)).因此,检索ith字符str[i]需要O(1)操作,就像访问数组的条目一样.类似地,在第二种方法中,您使用迭代器,粗略地说,这是指向此上下文中数组中位置的指针.因此,访问其内容*itr并将它们进一步移动一个位置itr++与将指针沿阵列移动并检索其内容具有相同的效率.

同样,关键的想法是将字符std::string存储在连续数组中,从而赋予它这样的功能.您可能希望将其实现与std::map底层实现是红黑树的位置进行比较,当然,这不是一个数组.因此,[]操作员以对数时间工作(与常数相反std::string).

编辑:

正如评论中提到的,cout输出相对昂贵(但仍然是O(1)).因此,如果您想检查"真实"效率,您必须std::ios_base::sync_with_stdio(false);在程序启动时删除输出或调用以提高速度cout.