Vector implmeneted as a list

[isaisa]

hi All
i have a basic doubt as i was reading about the STL class Vector.
There are some operations that are provided in the vector. As the vector class template provides the stack operations, list operations. There are some functions which are related to memory as in size(), capacity(), reserve().
Now the query is : when i try to use the vector class as a list, how reserve() can be used and what is the significance ? when i say reserve(100), does this mean that the 100 * sizeof (<build in data type / user defined data type>) bytes gets sequentially allocated but not initialized ? what is the use of sequential allocation when i try to use vector as a list?

Some help on explaining how reserve() works will be appriaciated...

thanks in advance
sanjay

 

[cpjust]

reserve( n ) will allocate n objects in the vector if the vector doesn't already have at least n objects allocated. Different STL implementations will have different default sizes, so the following line:

vector<char> str;

without even calling reserve() may allocate a certain number of char's to the vector by default. Calling size() will report 0 because you haven't added anything to the vector yet, but capacity() may report 100. This way, if you start adding chars to the vector, it won't have to keep allocating memory each time (which can be expensive if done too often). When you add items to the vector and you exceed the vector's capacity, it will automatically reallocate new memory (usually twice the current capacity) and copy everything from the existing buffer to the new buffer, then add your new item to the end.

It is impossible to shrink a vector, string, list... If you call reserve() with a number smaller than capacity(), it will do nothing.
One workaround you can use to "shrink" a vector, string, list... is to use the "swap trick".

vector<char>( str ).swap( str );

See this site for information about how the swap trick works, or search google for a billion other sites:

http://www.codeproject.com/vcpp/stl/std_vector.asp

I'd highly recommend reading "Effective STL" by Scott Meyers, ISBN: 0-201-74962-9. It should answer just about any question you ever had about STL.

 

[uolj]

Note that you can use the vector "as a list", but it is still implemented the same way (as an array). There are no pointers to or from nodes despite the fact that some of the vector's member functions are similar to those of a list.

 

[isaisa]

hi uolj
Thanks for the reply ....In the case which you discussed, the overall time complexity of the implementation is bound to go high to the order of O. Although to the end user, the implementation seems like list. My point is that vector implementation as list has got no practical aplication. please suggest if there is any ....

hi cpjust,
thanks for your reply ..... i got the confussion clear ...

sanjay

 

[uolj]

The term "as list" is vague. Can you be more specific? What list operations are you asking about?

The insert and remove functions can be expensive with vectors if done in the beginning or middle, but there can be reasons why you might want to have that capability. For the most part the STL designers avoided including in the interface those functions that would be severely inefficient, but some were allowed because they do have valid use cases.

One example I can think of is a list of files in a folder (imagine windows explorer in Details mode). If you create a new file you can insert it into the middle of the list, but you might want to store the files in a vector to take advantage of the faster sorting by different data. The insert would rarely happen, so the inefficiency of insert might be acceptable in order to keep the benefits of the other vector functionality.