It seems like Qt went from red-black tree to skip list in Qt4 and back to red-black tree in Qt5.

yeah it turns out that complex code, when its properly encapsulated and implemented in a bug-free manner, is not such a cost after all.

A correct skiplist is easier to NIH than a correct red-black tree (which for me was the final boss of the DS class in college), but has performance edge cases a red-black tree doesnt, if you treat it like a search tree.

▲

ahartmetz 2 days ago | parent [-]

I think it was more about binary size. There are a few sentences in the Qt containers documentation about them being "optimized to minimize code expansion".

▲

torginus 2 days ago | parent [-]

I mean that could mean a lot of things. By default, in C++, an std::vector<float> and std::vector<int> are two entirey separate classes with distinct methods getting compiled, even though in this particular the methods would be identical. Moreover, since templates are in headers, every object file gets their own compiled copy.

I'm sure there's some cleverness in there to mitigate the problem somewhat, but the problem still fundamentally exists

You can mitigate this manually to some degree, by making the generic classes call out to non-generic functions, of which there's guaranteed to be just 1 copy. I'm guessing that's what Qt does (among other things) when mentioning this

	▲	outpost_mystic2 a day ago \| parent \| next [-]
		Sorry if this is a dumb question but wouldn't vector<float> and vector<int> generate different code on get/set? Since floats go in different registers/need different instructions to load/store them to memory? Or is it something like, actually all of the std::vector functions technically operate on T&, and manipulating the pointers can use the same code, and really it's the optimizer that has to think about float vs int registers or something
	▲	ahartmetz a day ago \| parent \| prev [-]
		Well, you can do two or three main things: - Use an algorithm and implementation that needs a small amount of code for each instance (that is where the skip list is useful) - Have a shared "out of line" (not inline) implementation for bulky parts of the implementation, where possible - Support the compiler + linker feature to merge identical functions by making code identical between template instantiations of similar enough types