关于std :: vector的两个简短问题(Two short questions about std::vector)

关于std :: vector的两个简短问题(Two short questions about std::vector) 当一个矢量被创建时，它有一个默认的分配大小（可能这不是正确的术语，可能是步长？）。 当元素的数量达到这个尺寸时，矢量被调整大小。 这个大小的编译器是特定的 我可以控制它吗？ 这是一个好主意吗？

重复调用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()并存储结果？

谢谢！

When a vector is created it has a default allocation size (probably this is not the right term to use, maybe step size?). When the number of elements reaches this size, the vector is resized. Is this size compiler specific? Can I control it? Is this a good idea?

Do repeated calls to vector::size() recount the number of elements (O(n) calculation) or is this value stored somewhere (O(1) lookup). For example, in the code below

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

assuming s can be very large, should I call s.size() only once and store the result?

Thanks!

最满意答案

在大多数情况下，除非您事先知道项目的数量，否则应该单独分配分配，以便可以保留正确的空间量。

至少在我知道的每种情况下， 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 的C ++标准库是一个很好的参考资料。

In most cases, you should leave the allocation alone unless you know the number of items ahead of time, so you can reserve the correct amount of space.

At least in every case of which I'm aware, std::vector::size() just returns a stored value, so it has constant complexity. In theory, the C++ standard allows it to do otherwise. There are reasons to allow otherwise for some other containers, primarily std::list, and rather than make a special case for those, they simply recommend constant time for all containers instead of requiring it for any. I can't quite imagine a vector::size that counted elements though -- I'm pretty no such thing has ever existed.

P.S., an easier way to do what your code above does, is something like this:

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

Edit: IMO, The C++ Standard Library, by Nicolai Josuttis is an excellent reference on such things.