構造函數/函數重載簽名查找時間複雜度？

Question

我正在閱讀std::string類C++，並注意到有相當多的不同構造函數可用，給我們提供了一系列初始化特性。這讓我想知道編譯器如何選擇給定參數時選擇哪個構造函數，或者在重載的情況下，編譯器如何將函數簽名與給定的一組參數相匹配。

如果我們在僞代碼中聲明瞭以下功能：

function f1(int numberHere) { 
    //....do something 
} 

function f1(int numberHere, string stringHere) { 
    //....do something 
} 

我決定叫f1(4)，顯然有兩個選項可供選擇，但如果有10000選項/簽名？它會按比例延長嗎？如果是這樣，需要更長的時間？編譯器是否有一些偷偷摸摸的O(n)方法來索引超載，這樣它就可以在程序運行時調用正確的O(1)時間，或者不管有多少重載，但是它會在O(1)中編譯，但是由於開啓，運行完成的結果需要更長的時間飛行簽名匹配？

這個問題甚至可以得到有效的回答嗎？

謝謝！

Answer 1

匹配函數簽名實際上沒有任何其他搜索或查找問題不同。有三種基本的方法可以實現它，這取決於您要存儲的可用功能特徵的數據結構：

1. 使用未排序的列表或數組並獲得O（n）時間複雜度。
2. 使用排序數組或樹狀結構並獲得O（log（n））。 （您可以按照第一個參數的類型，然後第二個等等進行排序，假設每個類型都有一個分配給它的整數ID。）
3. 使用哈希映射並獲得O（1）。

但我懷疑時間complxity在這種情況下有任何實際的相關性。它描述了大值n的算法的漸近行爲。即使對於n = 100，未排序的數組搜索可能比散列圖查找更快，因爲它具有較少的開銷。

從可用性的角度來看，設計一個具有10甚至100重載函數的API是一個非常糟糕的主意。