"move them all back one notch [,] at once". I always thought of memmove() as an atomic operation (unless we move really big chunks of memory). Just like Stephan says, CPUs like to deal with contiguous blocks of memory, which fit in their caches - then moving one or a 1000 takes the same time. Supposedly. The key here is we're not moving the 999 ptrs one by one - they all live in one contiguous block of memory, of size 4000 or 8000 bytes (32- or 64-bit ptrs), so we just need to move one memory block of size 999*4 , 4 bytes down. The target and source regions overlap, but that's OK (I think).
wow, it took C++ only 20 years to correct its most glaring deficiency, the excessive copying on assignment.
why would vector need a linear time (38:10) to re-condense itself after erasure of an element? It is contiguous, and all it holds are pointers - why couldn't memmove() be used just to move them all back one notch at once, in constant time? Of course this is only for the case of non-inlined values, where you have an extra indirection level necessary for that, just like for the rvalue references. I guess in its quest for "efficiency" STL stores "light" values inside vector cells themselves, instead of boxing them up and storing just a pointer to the actual value on heap. Still, the implementation could distinguish between the two cases, right?
Jul 14, 2010 at 5:05 AM
Just started watching this. About co/contravariance w.r.t. subtyping: producer types are covariant, and consumer types are contravariant to subtyping. Apple is a subtype of Fruit: wherever Fruit is used, Apple can be used too: A <: F. That is because any quality Fruit has, Apple has too.
Array read is a producer: give it an Int and it gives you an Apple. Now, A <: F => (Int->A) <: (Int->F). Wherever we use (Int->F), it gives us Fruits, so we must be prepared to handle Fruits there. But it's OK to use (Int->A) instead 'coz it'll give us Apples, which can go instead of Fruits always.
With consumers it's the other way around. A<:F => (F->Int) <: (A->Int). Wherever we use Apples consumer, (A->Int), it is prepared to use Apples. So it means we must be supplying it with Apples. So we can use fruits consumer (F->Int) in its place, because this fruits consumer can always use Apples instead of Fruits.
Graphically, we can envision the producers/consumers as pipes with a certain diameter - small for apples, bigger for fruits. There are many more fruits than there are apples - bananas too etc. Now, for a wide inlet of fruits consumer (us, in the 1st case), it can just as well handle all input from a narrower outlet of an apples producer. In the 2nd case, the narrow outlet of apples producer (us) can just as well go into a wider inlet of fruits consumer in general.
Array read is a producer; array write is a consumer. Does this make sense?
EDIT: and in general, covariant, when translated from Latin I gess, just means "changing with the direction of change", and contravariant means "changing in the opposite direction of change". Say we do something that enlarges one thing, and another one grows too, than it is covariant to the first w.r.t. our action. If it consistently shrinks, we say it's contravariant to the first w.r.t. our action.
For example, imagine you travel from city A to city B in one straight line. The further you go along the route, the further you are from the city A, so your distance from city A is covariant with the distance you travel in the car. But the distance to city B is contravariant to it - it grows smaller as you travel. I guess a "travel operator" in its covariant form will reflect the enlargement of the distance as measured from the origin point. But in its contravariant form it will show the shrinkage of distance as measured to the destination.
Or take rotation: say we have a point on a plane, in some coordinate system. Now let's apply rotation to that plane. Point's coordinates will change WITH the plane's rotation, or covariantly. But what if we apply rotation to the coordinate system instead? Now the point's coordinates will change _in the opposite direction_ to the rotation, or contravariantly. That's where these terms come into physics from.