LeetCode 30-Day Challenge: Is This Cheating?
Today's problem, problem #4, for the the LeetCode 30-day programming challenge was the complete opposite of yesterday. They present the partitipant with:
Given an array
nums, write a function to move all
0's to the end of it while maintaining the relative order of the non-zero elements.
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
Um... that's just
At first I hesitated for fear of being cheeky and not trying hard enough, but then I thought to myself, "Wouldn't you rather see
std::stable_partition in production code rather than a roll-your-own implementation by some whiz kid?" So I submitted it, and it was accepted, and it was fast. (The STL can be fast, who knew?)
I am, however, looking for an example, or preferably a document, explaining how it's implemeneted in the STL so that I can understand what's going on under the hood. Google isn't turning up anything helpful. I tried looking through the GCC and Clang source code but their
stable_partition functions look tightly coupled with other functions and there are some confusing looking optimization tricks going on in there.