positivedelta2211's blog

Unexpected WA
By positivedelta2211, 3 years ago, In English

1066C - Books Queries I'm trying to solve this problem using deque, but get WA, can any one tell me why it is wrong 155581257

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

== But, unlike vectors, deques are not guaranteed to store all its elements in contiguous storage locations: accessing elements in a deque by offsetting a pointer to another element causes undefined behavior. == I think, you can't use difference of addresses.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Difference of addresses of deque's items surely not to be used. But in code used only differences of iterators, which is correct.

    Problem is there: http://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4861.pdf#subsubsection.22.3.8.4
    An insertion at either end of the deque invalidates all the iterators to the deque. So using stored iterators after push_back/pop_back is UB.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Difference of iterators is difference of addresses, as i understand. On non-linear containers metod 'distance()' need to be used to get count of elements between two iterators.

      Invalidation will cause troubles as well. So, method 'distance ()' doesn't help to solve the problem.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nope, difference of iterators is literally answer to question "how many times I need to decrement". operator- must be correct for all RandomAccessIterators. Deque provides RandomAccessIterator. It not just pointer but more complex struct.

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you.

      → Reply