c++ - 关于 std::vector 的两个简短问题

Question

1. 当一个 vector 被创建时，它有一个默认的分配大小(可能这不是使用正确的术语，也许是步长？)。当元素数量达到此大小时，将调整 vector 的大小。这个大小的编译器是特定的吗？我能控制吗？这是个好主意吗？

2. 重复调用 vector::size() 重新计算元素的数量(O(n) 计算)或者这个值是否存储在某处(O(1)查找)。例如，在下面的代码中

   // Split given string on whitespace
   vector<string> split( const string& s )
   {
       vector<string> tokens;
       string::size_type i, j;
       i = 0;
       while ( i != s.size() ) {
           // ignore leading blanks
           while ( isspace(s[i]) && i != s.size() ) {
               i++;
           }
           // found a word, now find its end
           j = i;
           while ( !isspace(s[j]) && j != s.size() ) {
               j++;
           }
           // if we found a word, add it to the vector
           if ( i != j ) { 
               tokens.push_back( s.substr(i, j-i) );
               i = j;
           }
       }
       return tokens;
   }
   

假设 s 可以非常大，我应该只调用一次 s.size() 并存储结果吗？

谢谢!

Answer 1

在大多数情况下，除非您提前知道项目的数量，否则您应该不理会分配，这样您就可以预留正确的空间量。

至少在我所知道的每种情况下，std::vector::size() 只是返回一个存储值，因此它具有恒定的复杂性。理论上，C++ 标准允许它不这样做。有理由允许其他一些容器，主要是 std::list，而不是为这些容器做一个特殊情况，他们只是建议所有容器使用恒定时间，而不是对任何容器都要求它。我无法想象一个计算元素的 vector::size -- 我觉得这样的事情从来没有存在过。

P.S.，一个更简单的方法来做你上面的代码所做的事情，是这样的:

std::vector<string> split(std::string const &input) {
    vector<string> ret;
    istringstream buffer(input);

    copy(istream_iterator<string>(input),
         istream_iterator<string>(),
         back_inserter(ret));

    return ret;
}

编辑:IMO，The C++ Standard Library，作者 Nicolai Josuttis 是关于此类事情的极好引用。