• Advertisement
Sign in to follow this  

vector

This topic is 4264 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

How does std::vector prevent memory fragmentation? I can't find a source which describes the nature of vector. :/

Share this post


Link to post
Share on other sites
Advertisement
I know that. But I'm wondering about the memory fragmentation part. How does it allocate more memory? What does push_back() do? Does it just grab enough memory to fit the new element or does it double the memory...?

Share this post


Link to post
Share on other sites
When the currently allocated array is full, vector allocates a larger array (e.g. 1.5 or 2x the size), copies the data over and releases the old array.

Share this post


Link to post
Share on other sites
:) k thanx that's exactly what i was looking for.

Edit: When/why should I use iterators? They seem to be some kind of optimization. I don't see a difference between using an iterator and directly accessing the elements.

Share this post


Link to post
Share on other sites
Quote:
Original post by biscuitz
Edit: When/why should I use iterators? They seem to be some kind of optimization. I don't see a difference between using an iterator and directly accessing the elements.


This page does a good job of explaining iterators: What Is an Iterator in C++, Part 1.

Here's the summary
Quote:
The iterator pattern describes a set of requirements that allows a consumer of some data structure to access elements in it with a familiar interface, regardless of the internal details of the data structure. The C++ standard library containers supply iterator interfaces, which makes them convenient to use and interoperable with the standard algorithms.



Also, not all containers allow you to access their elements with with operator[] (std::list in this example)

 #include <list>
#include <iostream>

int main()
{
// create a list with 4 elements, each with a value of 5
std::list<int> foo(4, 5);

// Won't compile - you can't access elements of a std::list with operator[]
//for (std::list<int>::size_type i = 0; i < foo.size(); ++i)
//std::cout << foo << std::endl;

// Works
for (std::list<int>::iterator itor = foo.begin(); itor != foo.end(); ++itor)
std::cout << *itor << std::endl;

}


Using iterators gives you to a consistent way to work with elements of different types of containers.

[Edited by - Will F on June 24, 2006 6:40:41 PM]

Share this post


Link to post
Share on other sites
Iterators are awesome because you can do almost C# kinds of things with them. They let you use the algorithms provided in the standard library and they integrate nicely with other libraries such as boost and stlsoft. They are also faster than doing for loops, because they don't use vector.at() or vector.size() operations. Well, you can probably outperform iterators by using raw pointers, but that's kind of error prone.

Compare this iterator code versus regular for loop code:

std::vector<int> integers;

//fill with random numbers (uses iterators to do its thing)
BOOST_FOREACH(int &i, integers)
i = rand();

//as opposed to:
for(int i=0; i<integers.size(); i++)
integers = rand();

//fill with zeros
std::fill(vector.begin(), vector.end(), 0);

//as opposed to:
for(int i=0; i<integers.size(); i++)
integers = 0;

//find the first occurence of 1
std::vector<int>::const_iterator it = std::find(integers.begin(), integers.end(), 1);

//as opposed to:
int it;
for(size_t i=0; i<integers.size(); i++)
{
if(integers == 1)
{
it = i;
break;
}
}

//find the next occurence of 1
std::vector<int>::const_iterator it = std::find(it, integers.end(), 1);

//as opposed to:
for(size_t i=it; i<integers.size(); i++)
{
if(integers == 1)
{
it = i;
break;
}
}

//sort
std::sort(integers.begin(), integers.end());

//as opposed to: (forget it)



Share this post


Link to post
Share on other sites
The expand on the above, imagine that you were using a vector in your code to store data. But then you think, "ya know, I'm adding and deleting stuff a LOT from this project, maybe if switch to std::list this will be quicker."

So you take a look at your code and you always access vector like this:
myVector = someValue;
Unfortunately for you, std::list doesn't let you use
myList = someValue;
And with good reason, it takes i time to get to the ith element vs. constant time with a vector.

For an example of how you can easily switch your code from vector to list take a look at the following example. Just uncomment the typedef and comment up the other one. Same thing for sorting. std::list has it's own sorting method so you need to switch that. Only two lines to change, versus many more otherwise.

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

int main()
{
// typedef std::list<int> int_container;
typedef std::vector<int> int_container;
int_container i;
i.push_back(10);
i.push_back(5);
i.push_back(20);
i.push_back(1);
i.push_back(100);
i.push_back(9);
i.push_back(0);
i.push_back(13);
i.push_back(200);
i.push_back(23);

for(int_container::iterator p = i.begin(); p != i.end(); ++p)
{
std::cout << *p << " ";
}

std::cout << std::endl;

// i.sort();
std::sort(i.begin(), i.end() );

for(int_container::iterator p = i.begin(); p != i.end(); ++p)
{
std::cout << *p << " ";
}
}

Share this post


Link to post
Share on other sites
*after spending half an hour reading and *trying* to learn* So iterators just make my stl's more compatible with each other.

Share this post


Link to post
Share on other sites
Iterators are esencially special kinds of pointers for containers.

As with pointers, derefferencing an itterator is faster than subscripting the vector, albiet by a tiny amount. Just like *ptr is faster than Array[x].

Share this post


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

  • Advertisement