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

Question

1. 创建向量时,它具有默认分配大小(可能这不是正确的术语,可能是步长？).当元素数量达到此大小时,将调整向量的大小.这个尺寸编译器是否具体？我可以控制它吗？这是一个好主意吗？

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计算元素的东西 - 我真的没有这样的东西曾经存在过.

PS,一个更简单的方法来执行上面的代码,是这样的:

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

编辑:由Nicolai Josuttis撰写的IMO,C++标准库,是对此类内容的极好参考.