C++: The most important complexities
sandordargo.com
sandordargo.com
Also note that all <algorithm>s have built-in fully automatic parallelism via <execution>, a massively underused feature. In typical CPP fashion though, their newer views:: counterparts lack those overloads for the moment.
…but in order for this to really matter, communication is required, since even the best developers don’t scale.
(But I'm about to move it to GPU)
(Not std::map, at the time it must have been something like tsl:: hopscotch_map).
Note also that nowadays for instance boost comes with state-of-the-art flat_map and flat_unordered_map which gives both the cache coherency for small sizes and the algorithmic characteristics of various kinds of maps
For an unsuccessful search, the vector version would do 100 key comparisons, and the hashtag would do a single hash, lookup the bucket, and almost certainly find it empty.
So, if you make the comparison function relatively expensive, I can see the hash map being faster at search.
Even relatively short string keys might be sufficient here, if the string data isn’t stored inline. Then, the key comparisons are likely to cause more cache misses than accessing a single the bucket.
Of course, the moment you start iterating over all items often, the picture will change.
Given the predictable access nature of vectors and their contiguous layout in the memory, the CPU backend will be able to take advantage of those facts and will be able to hide the memory latency (even within the L1+L2+L3 cache) by pre-fetching the data on consecutive cache-lines just as you go through the loop. Accessing the data that resides in L1 cache is ~4 cycles.
The "non-branchiness" of such code will make it predictable and as such will make it a good use of BTB buffers. Predictability will prevent the CPU from having to flush the ROB and hence flushing the whole pipeline and starting all over again. The cost of this is one of the largest there are within the CPU and it is ~15 cycles.
OTOH searching the open-addressing hashmap is the super-set of that - e.g. almost as if you're searching over an array of vectors. So, only the search code is: (1) By several factors larger, (2) Much more branchy, (3) Less predictable and (4) Less cache-friendly.
Algorithmically speaking, yes, what you're saying makes sense, but I think the whole picture can only be made once the hardware details are also taken into account. Vector approach will literally be only bound by the number of cycles it takes to fetch the data from L1 cache and I don't see that happening for a hash-map.
This is never a scenario that should happen, because if you are going to retrieve an arbitrary element it should be in a hash map or sorted map.
This is a very poor way to choose a data structure. How many items you want to store is not what someone should be thinking about.
How you are going to access it is what is important. Looping through it - vector. Random access - hash map. These two data structures are what people need 90% of the time.
If you are putting data on the heap it is already because you don't know how many items you want to store.
If you can picture them in your mind using blocks and arrows, the big-Os fall out of them naturally. To find an element, do you have to follow one pointer, then another? Do you have a choice at each junction? Is it contiguous? Hashmaps you have to convince yourself that it is indeed constant time, but once you get it you won't be in doubt.
Do the same for "what if I have to rearrange it, adding or removing an element?" and you get a bunch of other logical big-O answers.
There's a bunch of things made up of these things (LRU cache) and you can similarly logic your way to the answer, but I don't think I've come across an algo problem that isn't just a mash of these basic structures.
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.
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)
https://www.boost.org/doc/libs/master/doc/html/container/non...
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.
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).
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.
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.
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.
Additionally, you can just do:
std::stack<T, std::vector<T>>
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).
This is not considering the time you need to get to that element before erasing, which is O(n). The most frequent fallacy about lists.
Someone had to do it, sorry.
>std::array is a dynamically sized sequence container
A bit of a shame because C++ 14 and onward really closed all those gaps that devs used to rely on boost to get extended use out of, but I guess that's how a culture develops where there is no central package management repo.
That's why the yearly salary of a senior C++ dev can vary a lot, usually from 1x to 10x.
As you yourself have implied, you have to _start_ somewhere.