size and iterator of deque

[George2]

Hello everyone,


I am studying the C++ Standard Library book. In 6.3 Deques, it is mentioned,

1.

Iterators must be smart pointers of a special type rather than ordinary pointers because they must jump between different blocks.

What means "smart pointers of a special type" here? I do not understand if smart pointers here means auto_ptr something.

2.

In systems that have size limitations for blocks of memory (for example, some PC systems), a deque might contain more elements because it uses more than one block of memory. Thus, max_size() might be larger for deques.

I do not quite understand why we need special care about "more elements, ... more than one block of memory". I have this confusion is because deque is implemented as chunks of memory internally, which is already more than one blocks of memory, it has nothing to do with size limitations. What does the author mean here?

Why "max_size() might be larger for deques"?


thanks in advance,
George

[laserlight]

1.

Iterators must be smart pointers of a special type rather than ordinary pointers because they must jump between different blocks.

What means "smart pointers of a special type" here? I do not understand if smart pointers here means auto_ptr something.

Basically, the iterator for a deque is a smart pointers, not an ordinary pointer. auto_ptr is an example of a smart pointer - a type that behaves like a pointer, but is not an ordinary pointer.

I do not quite understand why we need special care about "more elements, ... more than one block of memory". I have this confusion is because deque is implemented as chunks of memory internally, which is already more than one blocks of memory, it has nothing to do with size limitations. What does the author mean here?

It is just a tidbit of information that tells you max_size() might return a value larger than expected. If this does not concern you, ignore it.

[George2]

Thanks laserlight,


1.

Basically, the iterator for a deque is a smart pointers, not an ordinary pointer. auto_ptr is an example of a smart pointer - a type that behaves like a pointer, but is not an ordinary pointer.

http://msdn2.microsoft.com/en-us/library/z50625f7.aspx

The above is the only sample I found about iterator for deque. Do you have a better sample or description about what do you mean "the iterator for a deque is a smart pointers, not an ordinary pointer", especially what is the differences between deque::iterator and other iterator of container?

2.

It is just a tidbit of information that tells you max_size() might return a value larger than expected. If this does not concern you, ignore it.

This is max_size sample from MSDN,

http://msdn2.microsoft.com/en-us/library/17y0taey.aspx

I do not quite understand what do you mean than expected? What is expected?


regards,
George

[CornedBee]

1) Iterators for vectors could, in theory, be implemented as typedefs for normal pointers, because all they have to do is traverse a continuous memory block. In practice, modern implementations don't do that anymore, because it causes all sorts of confusion, but it's possible.
Iterators for deque cannot be typedefs for normal pointers. They have to be more complex classes.
The comment in the book is slightly misleading, because smart pointers are usually expected to manage memory in some way.

2) Consider the old segmented memory models of 16-bit systems. There, a single allocation might not be allowed to span segments and thus be limited to 64 kilobytes. A vector, which needs all its memory from a single allocation, would thus be limited to "(segment size - overhead) / object size" elements.
A deque, with its non-contiguous blocks, can have each block in its own segment, and only needs to worry about the pointer block, which means it can store a total of "((segment size - overhead) / object size) * ((segment size - overhead) / far pointer size)" elements.

[George2]

Thanks CornedBee,


Vector has to use continuous memory block? Is it a mandatory requirement of Spec?

2) Consider the old segmented memory models of 16-bit systems. There, a single allocation might not be allowed to span segments and thus be limited to 64 kilobytes. A vector, which needs all its memory from a single allocation, would thus be limited to "(segment size - overhead) / object size" elements.
A deque, with its non-contiguous blocks, can have each block in its own segment, and only needs to worry about the pointer block, which means it can store a total of "((segment size - overhead) / object size) * ((segment size - overhead) / far pointer size)" elements.

regards,
George

[vart]

Vector has to use continuous memory block? Is it a mandatory requirement of Spec?

yes &v[0] is pointer to continuos block of memory containing all vector members

[George2]

Thanks vart,

yes &v[0] is pointer to continuos block of memory containing all vector members

In my experience, vector always use continuous memory block -- by reading vector internal implementation code. But using continuous memory block is a requirement of Spec or not?

If not, it means some other vendor may not use continuous memory block.

regards,
George

[vart]

A vector is a sequence container 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().

This is the quate from the C++ standard draft http://www.open-std.org/jtc1/sc22/wg...2007/n2461.pdf
that you could find by yourself

[George2]

Thanks vart,


Found it. Question answered.

This is the quate from the C++ standard draft http://www.open-std.org/jtc1/sc22/wg...2007/n2461.pdf
that you could find by yourself

regards,
George

[robatino]

yes &v[0] is pointer to continuos block of memory containing all vector members

Assuming v is nonempty, of course - otherwise v[0], and hence &v[0], invokes undefined behavior (as CornedBee pointed out in a previous thread). On the other hand, v.begin() is a valid iterator either way.

[George2]

Hi robatino,


I do not know what do you mean "otherwise v[0], and hence &v[0], invokes undefined behavior"? Could you show some code please? Here is my code, using &v[0] is good.

#include <vector>

using namespace std;

int foo(const int* buf)
{
	int temp;
	// watch the content of buf here
	for (int i = 0; i < 5; i++)
	{
		temp = buf [i];
	}
	return 0;
}

int main()
{
	vector<int> vc;

	vc.push_back (100);
	vc.push_back (200);
	vc.push_back (300);
	vc.push_back (400);
	vc.push_back (500);

	foo(&vc[0]);

	return 0;
}

Assuming v is nonempty, of course - otherwise v[0], and hence &v[0], invokes undefined behavior (as CornedBee pointed out in a previous thread). On the other hand, v.begin() is a valid iterator either way.

regards,
George

[vart]

Hi robatino,


I do not know what do you mean "otherwise v[0], and hence &v[0], invokes undefined behavior"?

He is talking about empty vector

vector<int>v;
v[0] ; //undefined

[George2]

Got your idea, thanks vart!

He is talking about empty vector

vector<int>v;
v[0] ; //undefined

regards,
George