Can I assume the memory is continuous?

Discussion in 'C++' started by linq936, Sep 13, 2007.

  1. linq936

    linq936 Guest

    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.
     
    linq936, Sep 13, 2007
    #1
    1. Advertising

  2. linq936 wrote:
    > 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Sep 13, 2007
    #2
    1. Advertising

  3. linq936

    Adrian Guest

    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
     
    Adrian, Sep 13, 2007
    #3
  4. linq936

    Pete Becker Guest

    On 2007-09-13 13:11:15 -0400, Adrian <> said:

    > 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.

    --
    Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
    Standard C++ Library Extensions: a Tutorial and Reference
    (www.petebecker.com/tr1book)
     
    Pete Becker, Sep 13, 2007
    #4
  5. linq936

    Kai-Uwe Bux Guest

    linq936 wrote:

    > 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
     
    Kai-Uwe Bux, Sep 13, 2007
    #5
  6. Adrian wrote:
    > 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, Sep 13, 2007
    #6
  7. linq936 wrote:
    > 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.
     
    Juha Nieminen, Sep 13, 2007
    #7
  8. linq936

    Adrian Guest

    On Sep 13, 12:22 pm, Juha Nieminen <> wrote:
    > Adrian wrote:
    > > 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.


    I meant smart as in them knowing about user types not as in boost etc
     
    Adrian, Sep 13, 2007
    #8
  9. linq936

    Adrian Guest

    > 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
     
    Adrian, Sep 13, 2007
    #9
  10. Adrian wrote:
    > On Sep 13, 12:22 pm, Juha Nieminen <> wrote:
    >> Adrian wrote:
    >>> 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.

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


    I don't even understand what that means.
     
    Juha Nieminen, Sep 13, 2007
    #10
  11. linq936

    James Kanze Guest

    On Sep 13, 8:22 pm, Juha Nieminen <> wrote:
    > Adrian wrote:
    > > 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.


    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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Sep 14, 2007
    #11
  12. James Kanze wrote:
    > 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.
     
    Juha Nieminen, Sep 14, 2007
    #12
  13. In message <46ea9421$0$3218$>, Juha Nieminen
    <> writes
    >James Kanze wrote:
    >> 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.


    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.

    --
    Richard Herring
     
    Richard Herring, Sep 14, 2007
    #13
  14. Richard Herring wrote:
    >> 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.


    No need to nitpick. I believe that you understood what I meant.
     
    Juha Nieminen, Sep 14, 2007
    #14
  15. In message <46eaf32f$0$3217$>, Juha Nieminen
    <> writes
    >Richard Herring wrote:
    >>> 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.

    >
    > 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.

    --
    Richard Herring
     
    Richard Herring, Sep 17, 2007
    #15
  16. linq936

    James Kanze Guest

    On Sep 14, 4:00 pm, Juha Nieminen <> wrote:
    > James Kanze wrote:
    > > 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.


    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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Sep 18, 2007
    #16
  17. James Kanze wrote:
    > 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.
     
    Juha Nieminen, Sep 18, 2007
    #17
  18. linq936

    Ron Natalie Guest

    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.
     
    Ron Natalie, Sep 18, 2007
    #18
  19. linq936

    James Kanze Guest

    On Sep 18, 12:15 pm, Juha Nieminen <> wrote:
    > James Kanze wrote:
    > > 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.


    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++.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Sep 19, 2007
    #19
  20. James Kanze wrote:
    >> "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.


    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".
     
    Juha Nieminen, Sep 19, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. howa
    Replies:
    7
    Views:
    441
    Alf P. Steinbach
    Dec 3, 2006
  2. Tomás Ó hÉilidhe

    Assume program under constant attack

    Tomás Ó hÉilidhe, Jan 19, 2008, in forum: C Programming
    Replies:
    7
    Views:
    304
    Syren Baran
    Jan 22, 2008
  3. Tomás Ó hÉilidhe

    Operator Overloading: Assume rational use

    Tomás Ó hÉilidhe, Jun 7, 2008, in forum: C++
    Replies:
    4
    Views:
    305
    Kai-Uwe Bux
    Jun 7, 2008
  4. Francis Moreau
    Replies:
    17
    Views:
    517
    Tim Rentsch
    Jan 4, 2011
  5. Josh Sharpe
    Replies:
    1
    Views:
    213
    Brian Candler
    Sep 21, 2010
Loading...

Share This Page