StefanPochmann's solution is great. His solution maintains the mid-iterator by the smaller half. Thus I want to try to maintain the mid-iterator with the larger half. And this turned out to be non-trival and I gained a lot from thinking about it, so I post my mirroring solution here along with my respect. The key points are:

- maintain the invariant: guarantee the mid-iterator movement happens on the correct situation.

For smaller half solution it means mid-- when inserting`nums[i] < *mid`

and mid++ when removing`nums[i-k] <= *mid`

; for larger half solution it means mid++ when inserting`nums[i] >= *mid`

and mid-- when removing`nums[i-k] >= *mid`

, thanks to point 2. - The C++ 11 standard: newly inserted elements follow their equivalents already in the container. *This makes operating on the smaller half easier.
- lower_bound and upper_bound semantic

```
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
multiset<int> window(nums.begin(), nums.begin() + k);
auto mid = next(window.begin(), k / 2);
vector<double> medians;
for (int i=k; ; i++) {
// Push the current median.
medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);
// If all done, return.
if (i == nums.size())
return medians;
// Insert nums[i].
window.insert(nums[i]);
if (nums[i] >= *mid)
mid++;
// Erase nums[i-k].
if (nums[i-k] >= *mid)
mid--;
window.erase(prev(window.upper_bound(nums[i-k]),1));
}
}
};
```