35 ms·
C++: The most important complexities
- jeffreygoesto 3y ago> removing an item from a random location: with erase() which has a complexity of O(1) for one element 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.
- verall 3y agoBut std::list doesn't invalidate iterators, so in situations where you can keep a reference back to whatever item you need, it's quite nice.
- gpderetta 3y agoI haven taken advantage of O(1) removal on linked lists (although typically intrusive ones, not std::list) many times, but I'm pretty sure not once I did a linear scan specifically to find the element to be removed. Typically you save the iterator on some index on insertion.
- harrid 3y agoYes... But you don't need to memorize all this, and it leaves out a simple rule: vectors (or arrays) outperform everything else if the dataset is small. Small is usually in the order of 100-300, but can vary wildly. 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.
- varjag 3y agoNot quite. Many other datastructures can be shoehorned into contiguous, cache efficient representations.
- csjh 3y agoNever heard of `execution`, great tip. Is there some big caveat or just generally unknown?
- harrid 3y agoYou need to be aware that these invocations are going to blast your cores full throttle as you obviously don't have fine grained control. But as long as your data is easily parallelized on a vector with computations that don't depend on each other, it's a game changer. I use it all the time to multithread things with literally a single line of code.
- lionkor 3y agoI looked into it (my video, probably too long https://youtu.be/9oh66SF91LA?si=azDCSOAJKA9Gpzim https://youtu.be/9oh66SF91LA?si=azDCSOAJKA9Gpzim), and the general result was that they make sense for non-small datasets and are a solid way to to parallelize something without having to pull in OpenMP or something.
- coffeeaddict1 3y agoThey're only supported in MSVC and GCC (for the latter you need to link against Intel's TBB to make it work). Support in libc++ (Clang) is work in progress.
- pca006132 3y agoClang does support parallel stl already (requires either TBB or OpenMP). Our project https://github.com/elalish/manifold https://github.com/elalish/manifold made use of this to speed up mesh processing algorithms a lot.
- coffeeaddict1 3y agoDoes it? You mean if you link against libstdc++ instead of libc++?
- 3y ago
- 01100011 3y agoI rarely meet a CS major who will accept that small things will always stay small. They will frequently talk you into more complex data structures with the assurance that you are just too stupid to realize your problem will suddenly need to scale several orders of magnitude. Do they teach you in CS-101 to interpret '+' as the exponential operator? It often feels that way.
- baq 3y agoThere’s computer science and there’s software engineering. The best developers are good at both. …but in order for this to really matter, communication is required, since even the best developers don’t scale.
- pca006132 3y agoAre they fresh graduates? It is very important to understand the workload distribution for any optimization. Even if small things can sometimes get large, optimizing for the small case can often yield large gain as they may occur frequently. And complex data structures are usually worse in the small case...
- papichulo2023 3y agoiirc, on msvc, execution parallel delegates to the OS (windows) to decide how many threads to create, at it is usually more than the total number of vcpu contrary to the usual recommendation.
- harrid 3y agoIt's very much implementation defined yes. I'm currently using this for something that runs for about 10 seconds, and even music playback and mouse cursor movement gets affected. (But I'm about to move it to GPU)
- Arelius 3y agoYes, but actually small can often be much larger then 100-300 depending on the specifics. Programmers often vastly underestimate how fast cache, and prefetch can go compared to complicated data structures.
- jcelerier 3y ago... Or much smaller, I remember a benchmark for a case I had a few years ago, the cutoff I had for a map being faster than std::vector/array & linear probing was closer to N=10 that 100. (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
- gpderetta 3y agoExactly. I measured vector vs an efficient linear probing hash map very recently and the cutoff was single digit. Even against unordered_map or plain std::map the cutoff was surprisingly low (although in this case I would trust a synthetic benchmark significantly less).
- Arelius 3y agoSure, the point here is with all the specific context specific details, your most likely comparing apples versus oranges. So simple complexity analysis or a general rule without benchmarks and a good understanding of the system and how it interacts with your details is not going to solve your problem.
- menaerus 3y agoSo you're saying that if I had had to store 100 elements in the memory, I would be better off using hashmap instead of vector/array? What type of elements did you use in your experiment or how large they were and what was your access pattern?
- 3y ago
- elromulous 3y agoIt's even more true for larger collections. Stroustrup gave a talk on this back at GoingNative2012. Tl;Dr: "Use a Vectah" -Bjarne https://youtu.be/YQs6IC-vgmo https://youtu.be/YQs6IC-vgmo
- CyberDildonics 3y agoA vector should be people's default data structure, but this presentation is bizarre, because it is based on looping through every element of a vector or a list to find the element you want. 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.
- maldev 3y agoIsn't that because view performs the procedure and access when the data is accessed? It's mainly meant so that you don't have to load all this memory in or stall when accessing the view, and if you don't need that capability, the regular algorithm stl is better.
- CyberDildonics 3y agovectors (or arrays) outperform everything else if the dataset is small. Small is usually in the order of 100-300, but can vary wildly. 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.
- pjmlp 3y agoOr 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.
- harrid 3y agoA tricky question in the context of this: why doesn't vector have a constant time pop_front? By just incrementing the begin pointer
- swolpatrol 3y agobecause 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)
- nly 3y agoOne of the top guides to learn and accept as a C++ developer is "Boost has it": https://www.boost.org/doc/libs/master/doc/html/container/non_standard_containers.html#container.non_standard_containers.devector https://www.boost.org/doc/libs/master/doc/html/container/non...
- gpderetta 3y agoTIL. It also has a (small) list of downsides.
- foma-roje 3y agoAn often missed c++ Container is std::deque, which has constant O(1) complexities in adding and removing from front and back, and accessing random elements. This is missing in the article.
- mike_hock 3y agoTypo: The section about std::vector starts with "std::array is a dynamically sized sequence container" (lol).
- fzy95 3y agoAt the std::vector section I think the std::array is used instead of std::vector >std::array is a dynamically sized sequence container
- repelsteeltje 3y agoYup, spotted the same. Looks like a copy-paste / typo
- bottled_poe 3y agoUmmm.. this is pretty basic stuff. If you don’t know this, you probably shouldn’t be claiming to be a c++ developer.
- skrebbel 3y agoI’ll never understand the aversion of C++ developers to useful learning resources and documentation.
- johnnyanmac 3y agoIt's nice to know, but the fact is that C++ is the wild west and my domain avoids using STD anyway. 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.
- mgaunard 3y agoThere is a very large spectrum of quality for C++ developers. That's why the yearly salary of a senior C++ dev can vary a lot, usually from 1x to 10x.
- elteto 3y agoAnd? Were you born knowing C++? Is that a genetic trait? As you yourself have implied, you have to _start_ somewhere.
- lordnacho 3y agoI think don't try to memorize the big-Os. Just read through a basic DS&A text, and see the standard structures: vectors, trees, linked lists, hashmaps. 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.
- vore 3y agoI think it's pretty rare you would ever use std::list and rarer still std::forward_list – the on-paper complexities might be okay but the memory locality is so bad you should almost always be using std::vector or std::deque.
- mchicken 3y agoUnless you want to splice lists here and there. I'm quite disappointed the article doesn't mention these features, as for most of my career, they were the only reason to prefer std::list to other containers.
- pca006132 3y agoFeel that it is also important to know when iterators/references to elements will be invalidated, in addition to knowing the complexities of the operations.