Jump to content
  • Advertisement
Sign in to follow this  
Endar

STL vector

This topic is 4679 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'd like to know some more about the inner workings of the STL vector. Most of the sites that I can find are simply about using it. In structure, is the vector similar to a linked list? Or is it like a dynamic array that is just resized when necessary?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Endar
I'd like to know some more about the inner workings of the STL vector. Most of the sites that I can find are simply about using it.

In structure, is the vector similar to a linked list? Or is it like a dynamic array that is just resized when necessary?


it is like a dynamic array that is just resized when necessary [smile]



Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The standard guarantees that the vector uses one contiguous block of memory for its internal storage. Which means passing a pointer to the first element ( &v[ 0 ] ) into functions expecting a pointer to an array's first element works. Say various OpenGL routines.


// ville

Share this post


Link to post
Share on other sites
Quote:
Original post by Endar
I'd like to know some more about the inner workings of the STL vector. Most of the sites that I can find are simply about using it.

In structure, is the vector similar to a linked list? Or is it like a dynamic array that is just resized when necessary?


It is a dynamic array that is just resized when necessary. However, it has a few advantages over your standard C-style dynamic array (sCsda from now on):

1) No need for manual memory alloction:

std::vector< int > ints;
ints.push_back( 3 ); //automatically allocates more memory as needed, no manual call to resize()/realloc needed.

2) Keeps ahold of memory for reuse, cutting back on the number of total reallocations if you would have just used realloc each time in a constantly growing and shrinking array.

3) Allocates memory exponentially. If you reallocate every time you add a single item in a sCsda, inserting N items takes O(N*N) time. By allocating exponentially (by which I mean, when a vector of 8 items with memory for only those 8 has an item added, it reallocates so that it has the memory for 16 items, allowing the next 7 to be added without relocation), std::vector reduces this to O(N).

4) Automatically calls (de)constructors as needed.

Share this post


Link to post
Share on other sites
Hmmm, problem.

I'm trying to use a dynamic array that I wrote, which is vaguely similar to vector, in that they are both dynamic arrays :D.

My problem is that I'm wondering how I would get a push_back function to work.


/**
* This class defines a wrapper for a templated dynamic array.
*/

template <class T>
class array
{
private:

unsigned int size; ///< The size of the array
T* arr; ///< Pointer to the array

public:

/**
* Constructor
* \param s The initial size of the array
*/

array(unsigned int s);

/**
* Destructor
*/

~array();

/**
* Overloaded operator []
* \param n The index into the array
* \return A reference to the 'n-1'th object in the array
*/

T& operator[](unsigned int n);

/**
* Delete the array and sets the size to 0
*/

void clear();

/**
* Resize the array to size s.
* \param s The new size of the array
*/

void resize(unsigned int s);

/**
* Returns the size of the array.
* \return The current size of the array.
*/

unsigned int getSize() const { return size; }

/**
* Return the pointer to the array.
* \return The address of the array
*/

T* getPtr() const { return arr; }
};



I mean, for something like this, I could always just add a variable to the class to keep track of the index of the last element in the array, but that seems to be a dead wrong design and use of classes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Endar
Hmmm, problem.

I'm trying to use a dynamic array that I wrote, which is vaguely similar to vector, in that they are both dynamic arrays :D.

My problem is that I'm wondering how I would get a push_back function to work.

*** Source Snippet Removed ***

I mean, for something like this, I could always just add a variable to the class to keep track of the index of the last element in the array, but that seems to be a dead wrong design and use of classes.


In your case, the index is calculatable with: getSize() - 1. Also note that the standard library must mantain seperate size and capacity counts (size = number of objects initialized, capacity = number of objects for which room has been allocated for) to do the exponential allocation and memory reserving that it does.

Also, I should note that the implementors of std::vector are very profficent people who've implemented optimizations you've probably never even heard of. This isn't to say you can't implement a functional dynamic array class, just to say that if your intent for this endeavour is "to make it faster", you're misguided. If it's for the learning experience, that's fine :-).

Share this post


Link to post
Share on other sites
I don't think I'll be adding in the automatic allocation of more than needed to speed up future inserts yet, but my problem was more finding if the last element had actually been used yet, or if it was free.

Share this post


Link to post
Share on other sites
Quote:
Original post by Endar
I don't think I'll be adding in the automatic allocation of more than needed to speed up future inserts yet, but my problem was more finding if the last element had actually been used yet, or if it was free.


I don't see functions that explicitly manage memory seperately from the number of elements, which would imply that the last element has allways been used. However, taking a std::vector corellary:

std::vector< foo > stuff;
stuff.reserve( 6 );
stuff.resize( 2 );
stuff.resize( 3 );

Foo's constructor will be called 3 times, but memory allocated (and only once) for 6+. For this kind of behavior, you need to mantain seperate counts for size and number of initialized elements (capacity) - there's no way around it. Some implementations "store" the capacity as the result of (begin - end) instead, but this forces you to store the end instead of just calculating it from begin + capacity.

So, either way, you're going to need another variable.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!