5 ms·

As someone coming from Java, why is pop_back undefined behavior? An error or noop is something I expect, but undefined behavior?

• dezgeg 4y ago
  It presumably allows the implementation to be a tiny bit faster, by avoiding a compare and branch for the empty case.
• st_goliath 4y ago
  I suppose it causes an integer underflow and tryies to in-place destruct in an empty buffer? The std::vector class is somewhat inconsistent about safety and maps a lot of it's operations directly to unsafe, raw array access. The C++ STL contains a lot of historical baggage and design inconsistencies. For instance, while std::vector has an `at(index)` method, that does proper bounds checking and throws an exception if the index is out of range, it also has an overloaded `operator []` that mimics array syntax that will happily write out of bounds, trashing the heap.
  • gpderetta 4y ago
    STL was designed to have no overhead over the corresponding C code. If push_back (and all other functions) had an extra check even when it was guaranteed non-empty by construction, it would have been a non-starter for many users. Consider that it took many years for compilers to reach the near zero overhead for STL as it is, removing precondition checks would have been beyond the ability of many compilers 20 years ago, and it still challenging today. Of course the actual overhead went down since and today we expect code to be more robust by default, but the original design principles were different. If you want safety by default, check your compiler documentation and compile with lightweight assertions enabled even in release builds.
    • simiones 4y ago
      This makes sense for std::vector::operator[], but not for pop_back and push_back - as those don't have any equivalent for a C array. Instead, it's just another example of C++ optimizing for speed as opposed to correctness.
      • gpderetta 4y ago
        The equivalent C code is what you would write inline to do a pop_back on an array. You can't write a fast pop_back for std::vector if it didn't provide one by default as the fields you would need to manipulate are private. And yes, it is indeed an instance of C++ optimizing for speed, which is exactly what I said.
        • simiones 4y ago
          std::vector exposes the exact same API as a C array, in terms of being able to write an external pop_back() function, since C arrays only expose the ability to access a particular element - no more, no less (and std::vector::resize() can be used instead of realloc() if that is desired).
          • gpderetta 4y ago
            The equivalent of of std vector is an array+size+capacity field. pop_back would litterally be capacity--. resize has overhead as it needs to handle resize up as well as down.
            • simiones 4y ago
              Sure, and I'm saying in C you could write: struct stack { int[] elems; int len, cap; }; int pop_back(struct stack *x) { elem = x->elems[x->len - 1]; x->len--; return elem; } while in C++ you could have written: struct stack { std::vector elems; int len, cap; }; int pop_back(stack& x) { elem = x[x.len - 1]; x.len--; return elem; } If you wanted C-style speed, with no safety.
              • zabzonk 4y ago
                that is not valid c. and in valid c++ (which this isn't) you would not need those two integer values.
                • 4y ago
• tubszonk 4y ago
  Because in c++ we assume the programmer doesn't make logic mistakes, and optimize for speed instead. A novice programmer can add assert() as needed.
  • Ygg2 4y ago
    To use a car analogy - We removed seatbelts to go faster, just don't make mistakes while driving.
  • spoiler 4y ago
    I'm not a novice programmer (close to 15 year in total) and I still make mistakes. ¯\_(ツ)_/¯ Maybe I'm just stupid
• Liquid_Fire 4y ago
  Java is memory safe, at a runtime cost (sometimes that cost is trivial, sometimes it isn't). It will insert a check every time you do a pop. C++ is not. It's a precondition of calling pop_back() that the vector is not empty. It will not insert a runtime check - it leaves you to decide whether one is needed. Your C++ toolchain will probably have an option to make (usually debug) builds check and complain if you actually call pop_back() on an empty vector.
  • Ygg2 4y ago
    So is Rust, and never did I hear a peep about `pop` is too slow better call unsafe.
• zabzonk 4y ago
  typically, c++ library functions do not use a possibly expensive check if the caller could have performed it themselves, should they have wished to. in this case, the caller could have tested if the container was empty before calling the function.
• dureuill 4y ago
  I had more bugs pop up from people calling front() on an empty vector than from direct out of range bounds. I guess people are more cautious when they are manipulating indices than when calling a method that takes 0 arguments? Debug asserts are nice, but not sufficient when the code path causing the empty vec is only encountered by a production user from a different country at 2am. Enabling the asserts in release mode will at least prevent undefined behaviour and malevolent users from harming the system, but the best interface is the one that returns an optional, so as to make the "vector was empty" case explicit. That way it has a higher chance to be considered by the authors of the code or their reviewers.
  • planede 4y ago
    Well, front() returns a reference. std::optional can't hold references. The closest you get is a plain pointer, with a null pointer for an empty container.
    • dureuill 4y ago
      Other languages allow to return `Option<&T>`. That's what I'm using these days. I suppose a raw ptr is what I would use on C++ to model that case though, yes.
      • planede 4y ago
        Yeah, for some reason `std::optional<T&>` is cursed and can't get through standardization. People can't decide what should happen on assignment.
        • dureuill 4y ago
          I guess a raw pointer is good enough an approximation in that case, it is just annoying that suddenly you can no longer use an optional because your type is a reference
• planede 4y ago
  pop_back on an empty container is a programmer error. A pop_back defined as noop would only leave the program in a slightly more defined state, but quite likely you can't really reason about the behavior of the program after. And implementations would not be allowed to diagnose the erroneous pop_back at runtime. IMO if pop_back had a defined behavior, it should be immediate termination of the program, with a diagnostic message. The standard does this for some erroneous behaviors, like failing to join or detach a thread before destruction, failing to catch an exception in various contexts or throwing an exception during stack unwinding. Undefined behavior already allows the behavior of terminating the program with a diagnostic message, and some implementation provide options to have this behavior. It might not be very discoverable though, which is a pity. It would be nice if some higher level build tools provided easier options for "fortifying" C and C++ code, but I doubt that there are options that uniformly apply across compilers and standard library implementations.
• dannymi 4y ago
  It's C++. Its goal is speed over all else. So it tries to carve out space for where the optimizer can assume lots of things are true. Since they don't use anything like Hoare logic they have to get their assertions from somewhere else, inferring them as follows (among other things): Undefined behavior just means that the specification does not say what will happen--so you can't rely on it as a user. The upside is that the compiler (and the compiler writers) can assume that places where the undefined behavior would occur in your program cannot be reached in practice--and thus optimize your program better. STL, which these containers are part of, is famously speed-optimized. STL (like C++) was designed for speed first (if at all possible then zero-cost abstractions) and thus does very little error checking on its own. Also, C++ is compiled ahead of time--so whatever optimizations it wants to make it has to do BEFORE it starts the program. That means it cannot adapt to the concrete runtime circumstances on the fly (like Java can) and so they have to keep even the worst case runtime down in everything they do. If they did check whether the thing is empty beforehand then that would cause a slowdown (at least that's the idea--better measure it), mostly because now there would be a branch in the first place. Hence they avoid doing that.
  • pjmlp 4y ago
    Yet we get stuff like std::regex, the speeding train of regular expression parser engines.
    • Gibbon1 4y ago
      My theory is the compiler maintainers don't themselves use 90% of the language features they implement. So they can't begin to care how well they work for people writing other types of software.
  • kllrnohj 4y ago
    > STL, which these containers are part of, is famously speed-optimized. STL (like C++) was designed for speed first (if at all possible then zero-cost abstractions) and thus does very little error checking on its own. Only kinda? A bunch of the containers then make other promises or leak details that prohibit meaningful optimizations. An extra branch in std::vector::pop_back() is such a pointless savings compared to, say, that std::map is basically mandatory red-black tree or that std::unordered_map must store elements in a linked list to preserver iterators across removals. Like almost none of the containers in the STL are "fast" at this point. std::vector is probably about the best, but even it is missing small-size optimizations (and that's ignoring the hair-brained bool specialization that then breaks everything)
• taneq 4y ago
  Because unlike Java, which is designed to bore you to death, C++ is designed to gaslight you into madness.
• jcelerier 4y ago
  I don't really see how one could make it a real no-op, and an error would imply that pop_back would look like if(empty()) { /* some error handling mechanism */ } ... rest of the code ... and every added branch adds some minimal but non zero cost
  • tialaramex 4y ago
    However really often this is a case you actually care about, and so if you don't capture it in pop you end up asking a predicate. I have a whole bunch of Rust code that does: while let Some(thing) = container.pop() { /* ... */ } There is indeed a branch, that pop function might return None - but when it does our while loop exits, the container is empty and we're done. My guess is that the idiomatic C++ here checks !empty() for the loop and then calls pop() on the container if it's not empty so in these cases we're doing the same work except we made it more error prone.