8

I'm looking in the C++ Standard (draft n3797), and I can't find any documentation of pop_back as it applies to std::vector, only for std::list. Is it really missing?

Specifically I was looking for the guarantee that pop_back doesn't change the capacity. Or is there such a guarantee at all? (I expect that iterators and references to other elements will remain valid, but I can't find that guarantee, and it wouldn't restrict the case of removing the last element, anyway)

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • 1
    In particular I mean the *Effects*, *Complexity*, and *Throws* documentation, which are given for other members. Table 101 is not a specification. (`pop_back` is also mentioned in the `vector` synopsis 23.3.6.1p2, but that is not a specification either, just a prototype) – Ben Voigt Nov 12 '13 at 22:57
  • 1
    Well under `resize` it says *If sz <= size(), equivalent to calling pop_back() size() - sz times.* which implies that pop_back does not change capacity. – Shafik Yaghmour Nov 12 '13 at 23:04
  • As far as I know, capacity is only altered when it's not sufficient for adding new elements into vector, when decreasing size capacity remains unattended. There's even a trick with `swap` method to reduce the capacity when needed. – Niyaz Ivanov Nov 12 '13 at 23:05
  • @ShafikYaghmour: That implies no such thing. `resize()` does not reduce capacity only because (1) it is defined in terms of `pop_back` and (2) `pop_back` does not reduce capacity. Where is (2) documented? – Ben Voigt Nov 12 '13 at 23:08
  • @BenVoigt `resize` is specified in [terms of erase as discussed here](http://stackoverflow.com/a/1155721/1708801) which concludes `resize` does not effect capacity which gives us (2). – Shafik Yaghmour Nov 12 '13 at 23:15
  • @Shafik: Please, show me where `vector::pop_back` (not `basic_string::pop_back`) or `vector::resize` is specified in terms of `erase`. – Ben Voigt Nov 12 '13 at 23:18
  • @ShafikYaghmour: That answer is outdated (I wrote it), I think Ben is right that the reasoning no longer holds. – GManNickG Nov 12 '13 at 23:39
  • @BenVoigt: I just read quickly through the containers section and indeed saw no mention of `pop_back` & capacity. The only two paths I can think of are 1) iterators to non-removed elements must remain valid, and reallocating would break that, or 2) it doesn't say capacity should/may change, so it definitely won't. 1) has the problem that a resize could be done in place, though I'm unsure C++ actually recognizes this as a possibility. 2) has the problem that it's wishful at best, though obviously in practice capacity is never reduced, hence the creation of `shrink_to_fit`. – GManNickG Nov 12 '13 at 23:41
  • @GManNickG: Also, in the not-so-rare case of `resize(0)`, their are no iterators/references/pointers with that pesky requirement of remaining valid. – Ben Voigt Nov 12 '13 at 23:42
  • @BenVoigt: Good point, that definitely clears option 1 away. I always did find the containers underspecified... – GManNickG Nov 13 '13 at 00:23
  • @GManNickG ok, got it, good to know. – Shafik Yaghmour Nov 13 '13 at 01:07

1 Answers1

1

No it doesn't missed. In a table in 101 §23.2.3, you can see pop_back exists for vector.

16 Table 101 lists operations that are provided for some types of sequence containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time.

enter image description here

 

Paragraph 16 mentioned they should implement to take amortized constant time.

masoud
  • 55,379
  • 16
  • 141
  • 208
  • Check first comment to question. – Ben Voigt Nov 12 '13 at 23:09
  • BTW, I think in previous drafts, that table made `pop_back` equivalent to an `erase` call, which therefore gave it all the formal specification listed for `erase`. – Ben Voigt Nov 12 '13 at 23:11
  • Yes and also, do you think _"...amortized constant time..."_ isn't talking about the complexity? – masoud Nov 12 '13 at 23:13
  • I agree that covers the complexity. And the *Requires* precondition is stated in the table. There's still stuff missing, though. – Ben Voigt Nov 12 '13 at 23:14
  • Do you mean thid _"Effects: Equivalent to erase(size() - 1, 1)"_? But it's in the strings section ?! – masoud Nov 12 '13 at 23:15
  • 1
    Yeah, I saw it for strings, and mistakenly thought that prior spec for vector also used it. But now I can't find any such thing. – Ben Voigt Nov 12 '13 at 23:20