4

Why does pushing an element on one of the ends of a std::deque invalidate all the existing iterators (All references remain valid though)?

I understand that deque is implemented as an array of arrays and that pushing an element on either end won't cause any reallocation of existing elements. And this is why references remain valid. But so should the iterators.

I also understand that the iterator of a deque is of type RandomAccessIterator and that this iterator should support some operations like adding/subtracting a constant number, ++, -- etc.

What I don't understand is that which of the operations that should be supported by RandomAccessIterator cannot be implemented by the underlying structure of std::deque.

nishantsingh
  • 4,537
  • 5
  • 25
  • 51
  • Sure, existing elements won't move. What about meta-data that iterators may depend on? That **array** of arrays. – StoryTeller - Unslander Monica Jun 25 '18 at 09:09
  • @StoryTeller We could keep the metadata in one place and have a pointer in the iterator class for that? – nishantsingh Jun 25 '18 at 09:13
  • 2
    And what happens when you need to reallocate that meta-data? Such as when you add another array to the array of arrays? – StoryTeller - Unslander Monica Jun 25 '18 at 09:14
  • @StoryTeller Let's say we keep a linked list data structure for the meta data. We always keep the first node fixed, i.e. we would never reallocate it. And we keep the pointer to the first node in the iterator class? – nishantsingh Jun 25 '18 at 09:16
  • 1
    [advancing](https://en.cppreference.com/w/cpp/iterator/advance) a `RandomAccessIterator` is required to be constant time, which is incompatible with the other complexity requirements of `std::deque` – Caleth Jun 25 '18 at 09:18
  • @user3286661 "We always keep the first node fixed" -> not a general `deque` anymore. You can remove from the front of a `deque`. – Caleth Jun 25 '18 at 09:20
  • @Caleth How about keeping a pointer to a pointer to the metadata as a member of iterator class then? ptra -> ptrb -> metadata. iterator will have ptra, we would only ever change metadata and ptrb. – nishantsingh Jun 25 '18 at 09:24
  • 1
    @user3286661 You are now complicating access to make some minor promises w.r.t. modification. I'm not sure it's worth it for a container in `std`. By all means, implement a `modify_safe_deque` with whichever (lack of) iterator invalidation you can come up with. What's your use case for keeping iterators across modifications that this is would be worth it? – Caleth Jun 25 '18 at 09:56
  • @Caleth No real use case for me as of now. I was asking just out of curiosity. – nishantsingh Jun 25 '18 at 10:05

0 Answers0