5 ms·
If you can use C++11, this becomes a non-issue with move semantics. Ownership of internal resources can be transferred, and emplace_back even allows constructi
by mihai_ionic 13y ago
If you can use C++11, this becomes a non-issue with move semantics.
Ownership of internal resources can be transferred, and emplace_back even allows constructing your object in place.
As others said, the O(n) really becomes more like pseudo-O(1) due to cache effects unless you have elements the size of your cache lines (in which case prefetching still helps) or you're only fetching one element at a time and then triggering a context switch (as in a scheduler).
I'm not bashing your library, and if you prefer to use C then that's great, but it's kind of unfair to blame it on the language in the first place.
- rumcajz 13y agoLanguages are designed for specific purposes. I am claiming that C++ is not the best language for system development. The fact that most OSes are not written in C++ is a good indication of the fact. Still, C++ is great for rapid development & corporate development.
- pjmlp 13y ago> The fact that most OSes are not written in C++ is a good indication of the fact. This is just inertia and only true on UNIX world due to how C is tied to UNIX. BeOS, Symbian, Genode -> C++ Mac OS X -> drivers are done in C++ (IOKit) Windows -> C is now official deprecated and C++ is the way to go. (http://herbsutter.com/2012/05/03/reader-qa-what-about-vc-and-c99/ http://herbsutter.com/2012/05/03/reader-qa-what-about-vc-and... && Herb's remarks at BUILD 2012)
- malkia 13y agoThat's all good, but to they use STL in the internals?
- pjmlp 13y agoMaybe not, but C++ is much more than just plain STL.
- malkia 13y agoThat is one of the problems with C++. In "C" land you also might be put to restrictions - for example don't use malloc()/realloc()/free() but some other functions, or don't use the provided assert() but something else, or no Xxxprintf() functions, etc - e.g. most of them are around function calls, that could be caught at preprocessor, compiling, or even runtime level. Now C++ comes with new/delete, dynamic_cast<>, throw/catch/etc, RAII, always export "C" interface (to avoid mangling) - While all of these are useful, due to the constraint where the language has to be used they can be forbidden. It's no longer functions that you are restricting from being called (as in "C"), you are forbidding to use parts of the language that are considered by many as vital, and it's basically a different language at this point.
- mihai_ionic 13y agoI'd like to know what restrictions cause you not to be able to use RAII. Even if that's the only C++ feature that a project were to use, I'd still consider it a net gain. Anything that makes your program less susceptible to manual resource management bugs in "goto cleanup"-style C is worth using. This doesn't just include memory leaks, but more insidious problems like unclear ownership of various system resources (sockets, file handles...). Things not even a GC would help you with in a long-running server process.
- malkia 13y agoYou can't use longjmp/setjmp - http://en.cppreference.com/w/cpp/utility/program/longjmp http://en.cppreference.com/w/cpp/utility/program/longjmp There are several popular "C" libraries that use them - jpeglib comes to mind, but there are others. Also certain language's runtime environment uses it. There is a way to handle it, but you need to take care.
- mihai_ionic 13y agoEven in C, setjmp/longjmp leave all non-volatile automatic storage duration variables on the current stack frame in an indeterminate state if they are modified between the two calls. To get defined behaviour with regards to destructors, you simply have to make sure that the function calling setjmp doesn't internally use RAII. Call a wrapper function to do the setjmp and you're safe. Of course it's a whole other question whether using setjmp/longjmp to implement "exception handling in C" is a good idea in the first place.
- protomyth 13y agoOS X drivers are "a restricted subset of C++"[1] that restricts you from using Exceptions, Multiple inheritance, Templates, and Runtime type information (RTTI). Also, not all drivers use IOKit. 1) https://developer.apple.com/library/mac/documentation/DeviceDrivers/Conceptual/IOKitFundamentals/Features/Features.html#//apple_ref/doc/uid/TP0000012 https://developer.apple.com/library/mac/documentation/Device...
- pjmlp 13y agoI am fully aware of it, besides "a restricted subset of C++" is still C++.
- protomyth 13y agoWell, not exactly. I/O Kit uses a specification called Embedded C++. It has been heavily criticized by C++ folks and is basically dead at this point.
- pjmlp 13y agoI know Embedded C++. Yes, it is true it wasn't well accepted in the community and never really took off. Still it is a C++ subset, not C, which is what this discussion is all about, regarding the use of C++ in kernel space.
- mihai_ionic 13y agoAdd the modern L4 microkernels to that list, e.g.: https://github.com/l4ka/pistachio https://github.com/l4ka/pistachio
- coldtea 13y agoWell, this is just precious. When the first C++ recommendation turned out to be not applicable, the answer is: 1) He can solve the issue by requiring C++11 (!!) 2) Just rely on cache-effects making it pseudo-O(1), unless (insert various cases where it might blow). Sure, he can jump through 200 hoops to use C++, special features, rely on CPU cache behavior, finetune to death, etc -- or, you know, he can use C and be done with it...
- mihai_ionic 13y ago1) It's 2013, all major compilers (GCC, Clang, MSVC, ICC) have supported rvalue-references for multiple releases. 2) You missed the part where there's nothing preventing anyone from using intrusive lists in C++.
- detrino 13y agoRemoval of an element in a vector is definitely O(n), regardless of cache effects.
- mihai_ionic 13y agotemplate <typename T> void remove(std::vector<T>& v, std::size_t i) { std::swap(v[i], v.back()); v.resize(v.size() - 1); }
- detrino 13y agoThat's just a different algorithm that produces different results than .erase() and has nothing to do with cache.
- alexchamberlain 13y agoNo one is saying it is not O(n), they're just saying that the cache effects can be larger than the complexity hit.
- detrino 13y agoExcept the parent did make that claim.
- beagle3 13y ago> If you can use C++11, this becomes a non-issue with move semantics. That wasn't an option for ZeroMQ which was started in 2007.