will std::deque not reallocate?

[Gernot Frisch]

std::deque<int> d;
d.push_front(13);
int* p13 = &d.begin();
d.push_front(1);
d.push_back(2);

Can I be safe, that p13 points to 13? I mean, unless I erase the 13,
of course.

 

[Noah Roberts]

std::deque<int> d;
d.push_front(13);
int* p13 = &d.begin();
d.push_front(1);
d.push_back(2);

Can I be safe, that p13 points to 13? I mean, unless I erase the 13,
of course.

I don't have the standard in front of me at the moment but I'm pretty
sure that push_front and push_back do not invalidate iterators or
pointers in a deque.

 

[Katharine Meyers]

why not try it out on ur own ? :-(

 

[David Harmon]

On Thu, 7 Dec 2006 18:00:33 +0100 in comp.lang.c++, "Gernot Frisch"

std::deque<int> d;
d.push_front(13);
int* p13 = &d.begin();

int* p13 = &*(d.begin());

d.push_front(1);
d.push_back(2);

Can I be safe, that p13 points to 13? I mean, unless I erase the 13,
of course.

push_front() and push_back() on deque do not invalidate the pointer to
the element. Please be careful, inserting or erasing in the middle (not
at front or back) of the deque will invalidate the pointer. Review
standard section 23.2.1.3 deque modifiers. std::list might be a safer
choice.

 

[David Harmon]

On 7 Dec 2006 09:08:22 -0800 in comp.lang.c++, "Katharine Meyers"

why not try it out on ur own ? :-(

Because "try it" almost never answers the question "is it guaranteed to
be safe?".

 

[Bernd Strieder]

std::deque<int> d;
d.push_front(13);
int* p13 = &d.begin();
d.push_front(1);
d.push_back(2);

Can I be safe, that p13 points to 13? I mean, unless I erase the 13,
of course.

Cited from the docs of SGI STL:

The semantics of iterator invalidation for deque is as follows. Insert
(including push_front and push_back) invalidates all iterators that
refer to a deque. Erase in the middle of a deque invalidates all
iterators that refer to the deque. Erase at the beginning or end of a
deque (including pop_front and pop_back) invalidates an iterator only
if it points to the erased element.

So there are STL libraries around, where no guarantees are given for
references. In an ideal world an invalidated iterator means invalidated
reference.

Microsoft C++ seems to invalidate iterators, but keep up references to
elements on insert and delete at the beginning, so there you might have
luck with the construction above.

I think you should use list instead of deque to be sure you have
reliable and portable code.

Bernd Strieder

 

[Mathias Gaunard]

std::deque<int> d;
d.push_front(13);
int* p13 = &d.begin();

You probably meant int* p13 = &*d.begin();
or int* p13 = &d.front();

d.push_front(1);
d.push_back(2);

Can I be safe, that p13 points to 13?

I think it is, since std::deque is not like std::vector.
It really supports constant time insertion at the beginning and the end,
not just amortized constant time insertion at the end.
That's because std::deque organizes its memory in chunks.

 

[Gernot Frisch]

So there are STL libraries around, where no guarantees are given for

references.

Thank you for clearing up.

 

[Kai-Uwe Bux]

std::deque<int> d;
d.push_front(13);
int* p13 = &d.begin();
d.push_front(1);
d.push_back(2);

Can I be safe, that p13 points to 13? I mean, unless I erase the 13,
of course.

In [23.1.1/Table 68], the standard defines the semantics of push_front() and
push_back() in terms of insert. Whether those operations invalidate
iterators, pointer, or references then depends on what insert() does. Here
is what the standard says about insert() for std::deque [23.2.1.3/1]:

iterator insert(iterator position, const T& x);
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);

Effects: An insert in the middle of the deque invalidates all the
iterators and references to elements of the deque. An insert at either end
of the deque invalidates all the iterators to the deque, but has no effect
on the validity of references to elements of the deque.


Best

Kai-Uwe Bux