2

Let's say I have my own implementation of std::vector, which provides begin() and end() functions for iterations. It may happen that size()==capacity() and pointer returned by end() is not owned by me. Will it be safe or do I need to ensure that size() < capacity()?

I know this dilemma can be overcome by using custom iterator classes, but here I am talking about the simpler case when begin() simply returns a pointer to the start of buffer, and end() to the begin()+size().

Toby Speight
  • 27,591
  • 48
  • 66
  • 103
unknown.prince
  • 710
  • 6
  • 19

3 Answers3

5

The standard prohibits dereferencing an invalid pointer (and the standard goes a great length describing what may invalidate a pointer, for example the life-time of the pointee, life-time of the memory chunk itself and the alignment of the pointer).

One can hold an invalid pointer as long as the user of that pointer doesn't dereference it, and in some cases as long as the user of that pointer doesn't read it (see comment section).

as you suggested yourself, end is simply return begin() + size()

David Haim
  • 25,446
  • 3
  • 44
  • 78
  • My reading of the standard suggests to me that the `std::cout << i` statement is UB. – Bathsheba Jun 20 '18 at 13:22
  • @Bathsheba elaborate. – David Haim Jun 20 '18 at 13:23
  • 2
    Per [this](https://stackoverflow.com/a/44182938/4342498) it is implementation defined behavior in C++14 and beyond and UB in C++11 on back. – NathanOliver Jun 20 '18 at 13:31
  • Huh, we all learned something new today. let me remove that part. – David Haim Jun 20 '18 at 13:33
  • 1
    It is still legal to assign to it, you just can't read from it. – NathanOliver Jun 20 '18 at 13:34
  • OK, now I'm confused (and I'll probably delete my answer soon), reading a pointer of invalid memory/object is UB? or just deallocated memory? cuz if it's the first, how come `end` works? – David Haim Jun 20 '18 at 13:37
  • 2
    @DavidHaim Using a pointer after `delete` and comparing to a past then end pointer are different things. Both of them are not dereferencable but the past then end pointer can be compared to while the deleted pointer can't be. – NathanOliver Jun 20 '18 at 13:42
  • One-past-the-end pointer is isn't an invalid pointer. `delete` renders a pointer invalid. – Passer By Jun 20 '18 at 13:55
  • i have to admit that I wasnt sure about `std::cout << i;`. Anyhow I think we all agree that `deleted` pointers are no good and mostly relevant for language lawyers only – 463035818_is_not_an_ai Jun 20 '18 at 14:35
2

A T* value is valid if it points to a T (which may be a sub-object of an array) or if it points one-beyond-the-end of a T[]. All other values are invalid, and using such a value is undefined behaviour.

This means you can compare (<, ==, etc) valid pointers, but not invalid pointers.

A T* value is dereferenceable if it points to a T. Dereferencing an invalid pointer, or a one-beyond-the-end pointer is undefined behaviour. This is a different set of values to valid pointers.

begin()+size() will give you a valid pointer, which is not dereferenceable.

Caleth
  • 52,200
  • 2
  • 44
  • 75
2

Your first problem is that it isn't possible at this time to hand roll a standard compliant std vector. There is no way to create a buffer with room for K Ts of which the first N are in an array of Ts, then resize this to N+1 Ts without reallocating the first N.

This is due to the fact that a buffer containing N (or N+1) adjacent Ts is not an array of Ts, and pointer arithmetic on T*s won't work quite right (under the standard) within a mere buffer of adjacent Ts, the way it works with a real array of Ts.

This is because the standard limits how far you can do pointer arithmetic on a T* to be within the T or one after; even if the T lives in a packed struct or buffer. Such limitations restrict how "reachable" objects are; if you have a struct with 3 ints, no arithmetic on an int* could modify more than one, so certain caching can be assumed to work and the compiler doesn't have to go back to RAM each access.

The unitended side effect is that there is no way to legally implement std vector. This is a flaw imnthe standard, the comittee is aware of it, and I asume someone is fixing it (for all I know it is fixed in , I don't think I missed the fix in ).

That being said, you can ignore all this, because most compilers get sufficiently confused by manual object construction in a contiguous buffer that their code to exploit the assimptions doesn't break your hand rolled vector.

Regardless, defined pointers values are those into an array, those one-past-the-end of an array, and individual objects can be treated as arrays of size 1 for this purpose. Pointers one-past-the-end exhibit UB if dereferenced even if an object exists there. Pointers in that range can be compared with < >= etc with each other (but not with pointers within/one-past other arrays). None will compare == to null, and all will compare != to null. != and == I believe work as you'd expect with them.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • Sounds familiar. C++98 forgot to state that `std::vector` is contiguous, even though everyone knew it was. – MSalters Jun 21 '18 at 07:43