Q1: what’s the problem to be solved by virtual inheritance
Q2: consider such a diamond with A as grandparent, B/C virtually deriving from A, then grandchild D. Suppose class C has a foo() method that uses a field A.a. Now, within C, the offset of A.a depends on the inheritance hierarchy, so how does the compiler compile C.foo()?
A: I do see a problem here. In this ABCD case, the offset of A.a is one value, depending on the size of B. However, in a ABJKCD case (J/K virtually subclass A), the offset of A.a will be a different value, depending on the sizes of B/J/K. So the C.foo() method will compile to different object code! Yet the compiler has a single version of C.foo().
The trick is the offset of the A sub-object within C. This offset value can be saved in the vtable of C.
Note if there’s no virtual inheritance, then simpler. Within C, the A sub-object’s offset is a constant. No need to look up vtable.
Q3: appending a million integers to a list vs a vector, which is faster and by how much?
%%A: vector requires reallocation, roughly 20 times, assuming doubling each time, much fewer than 1M allocations for the list. The reallocation entails element-by-element copy, but that’s cheaper than allocations. If I must estimate how much faster, I need to estimate how many allocations and how many copying:
- for list, 1M allocations + 1M copying
- for vector, 20 allocations + about 2M copying
%%A: I still think allocation is a hotspot and much more expensive than copying, perhaps by 10 or 100 times.
%%A: of course, you can pre-allocate for vector, but for this problem we ignore that feature.
Q4: deque — known for fast append/prepend, and random access. How?
%%A: I think it’s implemented as segments of vectors, with the front and back segments not fully occupied and growable. Once one of them reaches a certain size, a new segment is created. RandomAccess is implemented by identifying the host segment. To optimize, segments should have equal length.
Q4b: what if we want to support fast midstream insertion?
%%A: this is a vector limitation inherited by deque. If we need to support it, we may need to allow unequal segment lengths. RandomAccess is now slightly slower. For a given subscript 16, we need to maintain a step function like
- 5-10 in Segment 2
- 11-13 in Segment 3
- 14-20 in Segment 4
- 21-30 in Segment 5
- 31-32 in Segment 6
- … so each time any segment expands, the step function needs an update
- Once we have the step function, a binary search will do, at log(S) where S = Segment count