Can I assume the memory is continuous?

[linq936]

Hi,
When I use a vector iterator I normally do this way:

vector<int>::iterator itr = vec.begin();
for (; itr != vec.end(); ++itr ){
}

Note I am comparing if itr equals to vec.end(). I am wondering if I
could use "less than":

for (; itr < vec.end(); ++itr ){
}

I know this is not good in the system that virtual memory is not
used since memory can be segmented. But if we just assume the program
only runs on virtual memory system, then it is ok to write the code
using "less than". Am I right? As I see in virtual memory allocated
memory is always continuous.

 

[Victor Bazarov]

Hi,
When I use a vector iterator I normally do this way:

vector<int>::iterator itr = vec.begin();
for (; itr != vec.end(); ++itr ){
}

Note I am comparing if itr equals to vec.end(). I am wondering if I
could use "less than":

for (; itr < vec.end(); ++itr ){
}

I know this is not good in the system that virtual memory is not
used since memory can be segmented. But if we just assume the program
only runs on virtual memory system, then it is ok to write the code
using "less than". Am I right? As I see in virtual memory allocated
memory is always continuous.

Sure. Beware, though, that if you change your container to, say,
std::list, it's not going to work. Why do you really want the '<',
anyway?

V

 

[Adrian]

Vectors guarantee that the elements are in 1 contiguous block of
memory.

So for vectors you can use iter < vector.end().

Since iterators act as smart pointers this will always work.

It will not work for containers like map, set, list though as there is
not such guarantee about where elements are located in memory.


Adrian

 

[Pete Becker]

Vectors guarantee that the elements are in 1 contiguous block of
memory.

So for vectors you can use iter < vector.end().

The question isn't whether the memory is in one block, but whether the
container's iterator is a random access iterator. That's required for
vector and for deque (which doesn't guarantee a contiguous block).
Random access iterators support <. Other iterators do not.

 

[Kai-Uwe Bux]

Hi,
When I use a vector iterator I normally do this way:

vector<int>::iterator itr = vec.begin();
for (; itr != vec.end(); ++itr ){
}

Note I am comparing if itr equals to vec.end(). I am wondering if I
could use "less than":

for (; itr < vec.end(); ++itr ){
}

Yes, you can.

I know this is not good in the system that virtual memory is not
used since memory can be segmented. But if we just assume the program
only runs on virtual memory system, then it is ok to write the code
using "less than". Am I right?

No. In the above, using "less than" is _always_ ok regardless of the
platform.

What makes operator< work in your example is that std::vector<>::iterator is
a random access iterator. As such it must support operator<, and for
iterators into the same sequence it will tell you which element comes
first. See clause [24.1.5].

Thus, you could use "less than" also for std::deque<>::iterator.


On the other hand, what is wrong with != in the code? It is clearly more
idiomatic for iterating over a sequence (since other iterator categories do
not have operator<).

As I see in virtual memory allocated memory is always continuous.

Irrelevant. You seem to think that std::vector<>::iterator is a pointer.
That may be the case, but is not guaranteed by the standard.

On the other hand, std::vector<> (as opposed to all other sequence types)
guarantees that memory is contiguous. That, however, is entirely unrelated
to the question whether operator< can be used with std::vector<>::iterator.


Best

Kai-Uwe Bux

 

[Juha Nieminen]

Since iterators act as smart pointers this will always work.

You mean iterators act as *pointers*, not as *smart pointers*,
which are a bit different.

 

[Juha Nieminen]

Note I am comparing if itr equals to vec.end(). I am wondering if I
could use "less than":

for (; itr < vec.end(); ++itr ){

Actually I think that if you use an iterator which does not support
comparison with "less than", you will get a compilation error (this will
happen eg. with a list iterator). If it compiles, it should work as you
expect.

 

[Adrian]

You mean iterators act as *pointers*, not as *smart pointers*,
which are a bit different.

I meant smart as in them knowing about user types not as in boost etc

 

[Adrian]

The question isn't whether the memory is in one block, but whether the

container's iterator is a random access iterator. That's required for
vector and for deque (which doesn't guarantee a contiguous block).
Random access iterators support <. Other iterators do not.

Knew I should have checked the standard before posting

Thanks

 

[Juha Nieminen]

I meant smart as in them knowing about user types not as in boost etc

I don't even understand what that means.

 

[James Kanze]

You mean iterators act as *pointers*, not as *smart pointers*,
which are a bit different.

And what's the difference? The usual definition of a "smart
pointer" is a class type which supports the usual pointer
operations. Iterators certainly fit the bill in that regard.

 

[Juha Nieminen]

And what's the difference? The usual definition of a "smart
pointer" is a class type which supports the usual pointer
operations. Iterators certainly fit the bill in that regard.

The definition of "smart pointer" I have heard is one which
uses reference counting for automatically freeing the memory
allocated behind the pointer.

 

[Richard Herring]

The definition of "smart pointer" I have heard is one which
uses reference counting for automatically freeing the memory
allocated behind the pointer.

Is std::auto_ptr a smart pointer? Is boost::scoped_ptr? Neither of those
uses reference counting, but both are in some sense "smart" - their
destructors automatically delete the referenced objects (which may
involve more than just "freeing the memory") and they enforce particular
(different) contracts regarding ownership.

 

[Juha Nieminen]

Is std::auto_ptr a smart pointer? Is boost::scoped_ptr? Neither of those
uses reference counting, but both are in some sense "smart" - their
destructors automatically delete the referenced objects (which may
involve more than just "freeing the memory") and they enforce particular
(different) contracts regarding ownership.

No need to nitpick. I believe that you understood what I meant.

 

[Richard Herring]

No need to nitpick. I believe that you understood what I meant.

I understood the literal meaning of what you posted. I still don't
understand what point you were trying to make.

 

[James Kanze]

The definition of "smart pointer" I have heard is one which
uses reference counting for automatically freeing the memory
allocated behind the pointer.

And where did you hear this definition. I've never heard it.
The definition of a smart pointer is simply a user defined type
which behaves like a pointer (at least in some contexts or some
ways). Always has been, at least.

 

[Juha Nieminen]

And where did you hear this definition. I've never heard it.

http://en.wikipedia.org/wiki/Smart_pointer

"In computer science, a smart pointer is an abstract data type that
simulates a pointer while providing additional features, such as
automatic garbage collection or bounds checking. These additional
features are intended to reduce bugs caused by the use of pointers while
retaining efficiency. Smart pointers typically keep track of the objects
they point to for the purpose of memory management."

"The use of pointers is a major source of bugs: the constant allocation,
deallocation and referencing that must be performed by a program written
using pointers makes it very likely that some memory leaks will occur.
Smart pointers try to prevent memory leaks by making the resource
deallocation automatic: when the pointer to an object (or the last in a
series of pointers) is destroyed, for example because it goes out of
scope, the pointed object is destroyed too."

Memory management seems to be the key concept.

 

[Ron Natalie]

Any single allocation in C++ is contiguous.
The relationship between multiple allocations
(either distinct objects or successive calls
to memory allocators) is outside the scope
of specified behavior. Specifically the
standards for C and C++ did provide for the
fact that they may run on segmented architectures.

 

[James Kanze]

"In computer science, a smart pointer is an abstract data type that
simulates a pointer while providing additional features, such as
automatic garbage collection or bounds checking.

Which is exactly the definition I gave. A class (abstract data
type) which simulates a pointer while providing additional
features.

These additional
features are intended to reduce bugs caused by the use of pointers while
retaining efficiency. Smart pointers typically keep track of the objects
they point to for the purpose of memory management."

"The use of pointers is a major source of bugs: the constant allocation,
deallocation and referencing that must be performed by a program written
using pointers makes it very likely that some memory leaks will occur.
Smart pointers try to prevent memory leaks by making the resource
deallocation automatic: when the pointer to an object (or the last in a
series of pointers) is destroyed, for example because it goes out of
scope, the pointed object is destroyed too."

Memory management seems to be the key concept.

That's not what the first paragraph you quote says. What it
says is that memory management is a "typical" use. Which
implies that there are others. (And in fact, the first sentence
mentions one other: bounds checking.)

As usual, of course Wikipedia is of mixed quality. The first
paragraph above is actually fairly close to the truth. The
second is very debatable, and really only applies to C++, and
then only to one particular class of smart pointers in C++, and
arguably only to organisations which don't know how to manage
development in C++. Smart pointers exist outside of C++ (since
Java calls its pointers references, they are smart references in
Java), and have been used for many other purposes even in C++.

 

[Juha Nieminen]

Which is exactly the definition I gave. A class (abstract data
type) which simulates a pointer while providing additional
features.

The original claim was that "comparing vector iterators with < will
always work because iterators work like smart pointers".

Exactly what are these "additional features" of vector iterators,
compared to raw pointers, which allow comparing them with the < operator?

My objection was that the claim makes no sense because *regular* raw
pointers can be compared with the < operator and vector iterators having
the same property doesn't make them any "smarter".

Besides, as wikipedia hints, smart pointers in C++ are almost
exclusively used for memory management. I would say that to the point
that "smart pointer" in C++ *means* "a pointer which manages the memory
it points to". I'm not the only one who thinks like this. Look for
example at:

http://www.boost.org/libs/smart_ptr/smart_ptr.htm

"Smart pointers are objects which store pointers to dynamically
allocated (heap) objects. They behave much like built-in C++ pointers
except that they automatically delete the object pointed to at the
appropriate time."

Maybe the boost documentation is also "of mixed quality".