std::nth_element

void nth_element(RandomIt First, RandomIt Nth, RandomIt Last, Pr Pred);

按 Pred 比較,將第 Nth 元素就定位後就停止排序,也就是原本完整排序 [First, Last),可以知道第 Nth 元素是什麼值,用此方法就不用全部排完。

預設是用 < 比較,因此第 Nth 元素就定位後,Nth 左邊元素都比 Nth 小,但不必是有序的;Nth 右邊元素都比 Nth 大,也不必是有序的。

這個函式可以用在選股情境中,例如一台洗價機選出台股普通股中總量最大的 30% 股票,但不必按總量排好序,就可直接將股票資料傳送給兩隻手機,因為 UI 顯示可能會有另外的排序規則,一隻手機可能想按照股票代碼排序,另一隻則可能想按照漲跌幅排序。

完整程式如下:

#include <algorithm>

struct Stock {
    std::string name;
    double price;
    unsigned long volume;
};

int main()
{
    std::vector stocks = {
    {“2201.TW”, 18.45, 2449},
    {“2723.TW”, 138.0, 1010},
    {“3008.TW”, 3835, 650},
    {“1521.TW”, 56.3, 29},
    {“4107.TW”, 106.5, 152},
    {“2059.TW”, 307.0, 297},
    {“5274.TW”, 1100, 172},
    {“3293.TW”, 593, 819},
    {“2330.TW”, 304.5, 51234},
    {“5904.TW”, 472.0, 163}
    };

    std::cout << “before nth_element:\n{ Name, Price, Volume}\n”;
    for (const auto& stock : stocks) {
        std::cout << “{” << stock.name << “, ” << std::setw(5) << stock.price << “, ” << std::setw(6) << stock.volume << “}\n”;
    }

    std::nth_element(stocks.begin(), stocks.begin() + stocks.size() * 0.3, stocks.end(),
        [](const Stock& lhs, const Stock& rhs) {
            return lhs.volume > rhs.volume;
        }); // 將最大 30% 總量股票排前面

    std::cout << “\nafter nth_element:\n{ Name, Price, Volume}\n”;
    for (const auto& stock : stocks)
    {
        std::cout << “{” << stock.name << “, ” << std::setw(5) << stock.price << “, ” << std::setw(6) << stock.volume << “}\n”;
    }

    return 0;
}

std::nth_element