std::partition

需 #include <algorithm>,std::partition 可以根據指定條件將 array 分成兩群。

FwdIt partition(FwdIt first, const FwdIt last, Pr pred);

將傳入的 [first, last) 區間,根據 pred 的條件分成兩群,回傳值是第二群第一個元素的 iterator。符合條件的在 [first, 回傳值),不符條件的在 [回傳值, last)。

那我們可以怎麼使用它呢?

假設現在有一堆股票,我們想要選出股價介於 300 至 500 的股票。

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

std::vector<Stock> 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}
};

可以這樣寫。

auto pos = std::partition(stocks.begin(), stocks.end(), [](const Stock& stock) {
            // 找成交價介於 300 到 500 的股票
            return 300 <= stock.price && stock.price <= 500;
        });

這樣 [stocks.begin(), pos) 就是股價在區間 [300, 500] 的股票了。

完整程式如下:

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

int main()
{
    std::vector<Stock> 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} };

    // before partition
    std::cout << “before partition:\n{商品名, 成交價, 總量}\n”;
    for (const auto& stock : stocks) {
        std::cout << “{” << stock.name << “, ” << stock.price << “, ” << stock.volume << “}\n”;
    }

    std::cout << “\n”;

    std::pair<double, double> partition(300, 500);
    // pos 為第二群第一個元素
    auto pos = std::partition(stocks.begin(), stocks.end(), [&partition](const Stock& stock) {              // 找成交價介於 300 到 500 的股票
            return partition.first <= stock.price && stock.price <= partition.second;
        });

    // after partition
    std::cout << “after partition:\n{商品名, 成交價, 總量}\n”;
    for (auto it = stocks.begin(); it != pos; ++it) {
        std::cout << “{” << it->name << “, ” << it->price << “, ” << it->volume << “}\n”;
    }

    std::cout << “以上商品價格介於 ” << partition.first << ” 到 ” << partition.second << std::endl;

    for (auto it = pos, end = stocks.end(); it != end; ++it) {
        std::cout << “{” << it->name << “, ” << it->price << “, ” << it->volume << “}\n”;
    }

    std::cout << ‘\n’;

    return 0;
}

std::partition

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

std::partial_sort

在寫看盤軟體時,一定會遇到欄位的排序問題。

假設現在想要按照價格由小到大排序,而螢幕只能顯示 40 檔股票,但全部股票有 10,000 檔,那就沒有必要全部排完序,然後只擷取前 40 檔股票顯示,只要最小的 40 檔按順序排完即可。

有沒有這種函式呢?有的。

std::partial_sort 就是這種函式,直接來看 code:

首先 #include <algorithm>。

假設有股票資料結構如下:

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

現在使用者點擊 price 欄,程式需要按 price 由小到大顯示股票,而手機螢幕只夠顯示 5 檔股票,原始資料如下:

std::vector<Stock> 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::partial_sort,前 5 個元素排好就停止,寫法如下:

std::partial_sort(stocks.begin(), stocks.begin() + 5, stocks.end(),
[](const Stock& lhs, const Stock& rhs) {
        return lhs.price < rhs.price;
        }
);

參數表示

1. 排序的範圍是 [stocks.begin(), stocks.end())。

2. 最小 5 檔按順序大小排完即停止 [stocks.begin(), stocks.begin() + 5)。

3. 比較方式是取 Stock 結構的 price 成員變數,即按價格排序。
    [](const Stock& lhs, const Stock& rhs) {
        return lhs.price < rhs.price;
        }

顯示結果:

 

完整程式如下:

#include <algorithm>

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

int main()
{
    std::vector<Stock> 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 partial_sort:\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::partial_sort(stocks.begin(), stocks.begin() + 5, stocks.end(), [](const Stock& lhs, const Stock& rhs) {
        return lhs.price < rhs.price;
    }); // 前 5 個元素排好序就停止

    std::cout << “\nafter partial_sort:\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::cout << ‘\n’;
}

C++ value initialization

假設有一個 K 線資料結構:

struct K {
    unsigned long time;
    double price;
    double volume;
};

因為此資料結構是 Trivially Copyable,所以可以使用 memset 來初始化:

K k;
if (std::is_trivially_copyable<K>::value) {
    memset(&k, 0, sizeof(K));
}

但如果哪一天我們新增了一個商品名稱成員變數,型態是 std::string:

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

突然間此結構就不是 Trivially Copyable,不能用 memset 來初始化了。更糟的是,我們可能會漏修改有使用 memset, memcpy 等函式的地方,導致原本的 code crash。

那有沒有什麼方法解決呢?有的。可以使用 value initialization,也就是使用 () 或是 {} 來初始化物件:

K k{}; // value initialization

這樣 k 就會被正確初始化了。

P.S. 注意!這裡不能使用 () 來初始化,因為會被當成函式宣告。

K k(); 表示宣告一個名稱為 k,沒有參數,回傳值是 K 的函式。

指標也是如法炮製即可:

K* pK = new K;
memset(pK, 0, sizeof(K));

改成

K* pK = new K(); // value initialization

K* pK = new K{}; // value initialization

即可。