🔒 Locked

std::vector -- WTF?

Started by walkingcarcass Jan 13, 2007 at 9:40 AM 7 replies 1.1k views

Original Post

Jan 13, 2007 at 9:40 AM

Hi. I want to extend of std::vector such that it never allows the amount of allocated memory to fall beneath a certain number of entries. I originally presumed that the reserve() method would allow the storage to shrink below its specified amount when items were removed, but now I'm confused.

Quote:
From codeproject.com However, the resize() member function is only capable of increasing the capacity of the vector. The only member capable of changing the size of the internal buffer is clear()

That can't be right since pop_back allows a vector to dynamically shrink, right?

From /usr/include/c++/4.1.2/bits/stl_vector.h
void pop_back() { --this->_M_impl._M_finish; this->_M_impl.destroy(this->_M_impl._M_finish); }
[/quote] So I suppose destroy() must re-size the memory. But _M_impl is an instance of allocator_type and std::allocator doesn't declare a destroy method... and it's asking a lot that the allocator instance should interpret the dynamic END of storage... so... what's going on? N.B. eyeballing "grep -r destroy *" doesn't indicate a destroy method defined ANYWHERE. At the end of the day, I want to put a persistant lower limit on the size of the allocated buffer, even if all its contents are popped or assign()ed to nothing. Since the allocator doesn't (depending on which spec you read) specify a resize() method in its interface, it's the container class that really needs to be changed -- but it's all starting to look like opaque magic. Oh woe.

_the_phantom_

Jan 13, 2007 at 10:01 AM

This might be implimentation specific (the spec is too far away for me to be bothered to look) but I'm pretty sure that once grown a vector will not shink unless you make it do so via the swap() trick.

That is to say; if you push 5 elements on and then pop 5 elements off while the size will return 0 behind the scenes the vector still has enuff memory allocated for those 5 elements so next time you push data on it'll just reuse that lump of memory.

So, having a persistant lower memory limit is just a matter of either calling the constuctor with a min number of elements (which iirc has them default constucted) or by creating without a lower limit and either reserve() or resize() to the size you want.

Sharlin

Jan 13, 2007 at 10:04 AM

pop_back() will not free any memory allocated by the vector. It calls the destructor of the last element and decrements the vector's size -- its capacity stays the same. So next time a push_back() happens, no allocation/copying is necessary; the new element is constructed where the now-destroyed pop_back()'ed element once was.

The vector's capacity does not shrink, except perhaps when calling clear().

Omid Ghavami

Jan 13, 2007 at 10:05 AM

It might be implementation dependent, but the way I understand it pop_back does not reallocate memory. pop_back simply removes the last element.
So no, pop_back does not dynamically shrink the vector if you mean in terms of memory.
resize() inserts or removes elements to the vector so that it's size becomes the requested size. Once again it's probably implementation dependent, but I'm guessing for most implementation it never shrinks the allocated memory.
As for clear(), there recently was a thread were it was discussed whether memory was re-allocated or not.

Quote:
Washu says:
It is unspecified if the memory will be deallocated or not when you call clear. All clear is guaranteed to do is: erase(begin(), end()) which will call the destructors of the elements being erased, but as to the question of freeing up the actual nodes allocated, that is implementation defined.

jflanglois

Jan 13, 2007 at 10:07 AM

I'm not sure what you are trying to do, but allocated size of the vector always has a lower limit:

Quote:
Working Draft: Standard for Programming Language C++ (2006-11-03)
void reserve(size_type n);
Effects: A directive that informs a vector of a planned change in size, so that it can manage the storage allocation accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve().

So if you want to make sure the vector has allocated a minimum size of storage, call reserve( min_size ).

Agony

Jan 13, 2007 at 10:07 AM

[edit]Wow, lot's of faster posters.[/edit]

A vector has two significant values, size and capacity. Size refers to the number of elements that are actually available for use, have been constructed, and so on. This is typically what the programmer is most concerned about. Capacity, on the other hand, is simply how much memory has been allocated for elements, but not necessarily constructed yet. Capacity is always at least as big as size, but sometimes (usually) bigger. The purpose is so that a vector that changes size frequently doesn't need to allocate memory frequently. When you do a push_back(), for example, and there isn't any more memory left, the vector will reallocate memory that is noticeably more than what you're asking for. That way, the next time you do a push_back(), it has plenty of spare memory to use. If it didn't do this, then resizing a vector would be a very painfully inefficient task.

So what you're seeing in the documentation is that the capacity of a vector won't decrease. Once the memory has been allocated, it won't get reallocated, unless capacity needs to increase. A decreased need for capacity won't cause a reallocation.

Are you wanting the actually size of the vector to stay at some minimum, rather than just the capacity of the internal buffer? If so, why? Perhaps there might be a better way to do what you want. If not, you'll just have to manually handle it, or take the time to make a wrapper class around vector to do it for you.

gumpy

Jan 13, 2007 at 10:08 AM

nice. you guys saved me from typing an explanation. [grin]

here's a quick example.

#include <iostream>#include <vector>int main ( int argc, char *argv[] ) {        std::vector<char> v;        std::cout << "\nsize:     " << v.size() << std::endl;        std::cout << "capacity: " << v.capacity() << std::endl;        v.reserve(1024*1024);        std::cout << "\nsize:     " << v.size() << std::endl;        std::cout << "capacity: " << v.capacity() << std::endl;        v.resize(1024*1024);        std::cout << "\nsize:     " << v.size() << std::endl;        std::cout << "capacity: " << v.capacity() << std::endl;        return 0;}

output:

size:     0capacity: 0size:     0capacity: 1048576size:     1048576capacity: 1048576

CTar

Jan 13, 2007 at 10:11 AM

Ok, I guess the vector allocation strategy has been covered, but I haven't seen any mention of destroy yet.

destroy is a member function of all allocators, and all it does is calling the destructor of the pointer passed to it, but it won't deallocate the memory. So it makes sure, that from your point-of-view, the element is destroyed, but it will really save the memory for the next element to be added.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.