Or maybe, if lucky to be on a market where there are more jobs than developers, avoid the companies that think they are the next Google on their interview process.
Naturally one should have a base knowledge of data structures and algorithms complexity, to the point relevant to the job, and naturally knowing which book to open when needed.
Because there are an infinite number of half-breed data structures that you could think of to balance tradeoffs.
The STL has to restrict itself to somewhat stereotypical data structures that are intuitive to understand, yet can be composed to create such tailored data structures.
What you suggest is basically a tradeoff for speed of front removal against wasting some memory.
There are an infinite number of such subtle tradeoffs that can be done. Some line need to be drawn somewhere.
The STL is not intended to contain all possible variants of data structures in existence. It should provide you with a minimal set of containers that are _good enough_ for most use cases. In the case where front insertion is important to you, you can use std::deque. If you want a mix of the pros and cons of deque and vector, then it's fair to say that's on you to implement it.
All the rest is for dedicated libraries / custom containers to implement.
The question the grandparent comment wrote was "Explain why popfront would not be implemented in the current vector in O(1) by simply pointing the front pointer forward one element?"
Answering that with "there are tradeoffs and STL had to pick one" is misunderstanding the point of this question; the _premise_ of the question is that there are tradeoffs and STL picked this one and we can safely assume they have some reason; the leading question is highlighting an interesting case where the tradeoff isn't trivially obvious regarding difficult-to-use capacity laying at the front of the vector after the popfront operation happens if you implement that operation in O(1).
I guess I still don't clearly see what the leading question is pointing at.
Should that be: _why was it not important to optimize for vector pop front?_
If that is the case, then I feel like the overall philosophy of vector vs deque answers that question.
Vectors are tailored to be good at random access and back insertion/removal, at the expense of wasting capacity.
Overall, that means vectors are focused for append-mostly workloads, thus why they often have and aggressive capacity reallocation factor.
Having a vector double down on unused capacity consumption by allowing constant time front removal was, I guess, deemed useless, since one would most likely be using a deque for such access patterns.
I'm thinking it's maybe it's "too obvious" for you that makes you misunderstand the point.
It's just:
- Look at these big-O, see that pop front isn't O(1)
- Here's a proposed pop front that is O(1) (move the pointer forward)
- Reason about why they didn't choose that.
It's already an aha moment for people to realize that the capacity left at front is generally harder to use than keeping unused capacity at the end. In the spirit of the leading question that aspect is something the reader can reasonably realize after thinking about it, not something that is intended to already be obvious before you start thinking.
because vectors are not designed for that. When they mean "dynamic" they literally just mean ontiguous memory, removing the first element would leave an empty space at the beginning. To maintain contiguity, all other elements would need to be shifted one position forward. This operation is linear in time complexity
O(n), as it depends on the number of elements in the vector.
Also Vectors manage their own memory allocation and deallocation. If the begin pointer is incremented without moving the elements, the vector would still be holding onto memory that it's not actually using for storage of active elements. This can lead to inefficient memory usage.
Basically speaking: they are designed to modify the end, keep adding, take a bit off, split them at a point, but not really take away from the beginning ( and I mean literally the first element)
If an STL container lacks a method, it's a hint that 'here be dragons'. For example, random access of a std::list: it's possible, but you don't want the uninformed to be doing it without considering the consequences simply because it's easy to write.
What do you do about the memory allocated for the first element? That's a decision for the programmer to think about, not for the standard to enforce. A std::deque may deallocate.
You're arguing that there aren't STL methods for doing inefficient things.
But the parent took that as a given. Their comment translates as, "why doesn't the STL allow efficient removal at the front of a vector" (which would be possible in principle, e.g. python bytearray is similar but supports it). Part of the answer is that it would need an extra internal data member.
BTW the pop on std::stack refers to the back so doesn't help with pop_front (and vector already supports pop_back).
Naturally one should have a base knowledge of data structures and algorithms complexity, to the point relevant to the job, and naturally knowing which book to open when needed.