Sign in to follow this  

Std::Vector question

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

So, earlier I was working with these and I know that the vector probably allocates memory with the 'new' operator. My question is this : Does the std::vector guarantee that memory is contiguous? The only way I can think this is possible is to copy the entire contents on each action ( be it inserting extending ect.). Of course, my strong assumption is that the vector does not do this, and that is the necessity of the iterator ?

Share this post


Link to post
Share on other sites
Quote:
Original post by VprMatrix89
My question is this : Does the std::vector guarantee that memory is contiguous

Yes. The C++ standard guarantees that.

[edit]

Just for reference:

Quote:
C++ International Standard
23.2.4 Class template vector
1 A vector is a kind of sequence that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

Share this post


Link to post
Share on other sites
Quote:
Original post by VprMatrix89
Then I'm still confused as to the point of the iterator, as its just a pointer? If a normal pointer would suffice, whats the use?

An iterator is not a pointer. Rather, in a way, a pointer is a type of iterator. This might help a little. Basically think of this: if you have a general algorithm, how can you get it to work with multiple containers? Clearly you can't simply use pointers (because some containers don't use contiguous memory). But if each container defines some iterator type that has a common interface, your general algorithm can work with lots of different containers. For example, try writing a reverse function that reverses the contents of some ordered container. That function is going to need iterators if it's going to work for both contiguous arrays and linked lists.

Share this post


Link to post
Share on other sites
Quote:
Original post by VprMatrix89
Then I'm still confused as to the point of the iterator, as its just a pointer? If a normal pointer would suffice, whats the use?


1) By not making the assumption that a vector iterator is a pointer, you can write generic code that doesn't care (more than necessary) about iterator types.

2) It's a level of abstraction.

3) The iterator may implement bounds checking (although not required to) which a pointer cannot. This is particularly useful for debug builds (although I understand that with VC++ you have to explicitly turn off the bounds checking even in release mode).

4) Certain member functions of the vector expect iterators. A pointer will not be acceptable here, at least not portably.

5) In general, it's the other way around: pointers are a kind of iterator. Specifically, they're the iterator type for arrays. For example:


// The usual C++ way
std::string message = "hello world";
std::string::iterator end = std::remove(message.begin(), message.end(), 'e');
message.erase(end, last);

// ZOMG, not std::string!
char[] message = "hello world";
// 'message' is decayed into a pointer to the beginning of the buffer, and
// pointer arithmetic gives us a pointer to the end of the buffer.
char* end = std::remove(message, message + sizeof(message), 'e');
// Add a null terminator to "erase" the garbage at the end of the string.
*end = '\0';

Share this post


Link to post
Share on other sites

This topic is 3153 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this