插入字符串的效率

我正在嘗試爲非常大的整數編寫這個自定義的添加類，比long long長。我正在研究的一種方法是將整數保留爲字符串，然後將字符轉換爲其int分量，然後添加每個「列」。我正在考慮的另一種方法是將字符串拆分爲多個字符串，每個字符串都是長整型的大小，然後使用字符串流將其轉換爲長整型並重新組合。插入字符串的效率

不管我碰到一個事實，即除了在反向最容易做允許承載過的數字。這是我想知道的字符串插入方法的效率。看起來，因爲一個字符串是一個字符數組，所有的字符都必須被移入一個字符。所以它會有所不同，但它看起來效率是O（n）其中n是字符串中的字符數。

這是正確的，還是這只是一個天真的解釋？

編輯：我現在回答我的問題，但我想知道的相關主題，其效率更高，將字符串轉換成流，然後解壓到一個int。或者做10^n * char1 + 10^n-1 * char2 ...等等？

來源

2012-01-09 emschorsch

請勿將其保存爲有效顯示的格式，並保持格式的高效操作。您只想在顯示它時將其轉換爲字符串。 – dreamlax 2012-01-09 07:39:13

不要重新發明輪子。已經有一些庫爲你實現大整數，效率更高，並且已經過測試！ – amit 2012-01-09 07:39:57

雅我下載了gmp庫，我只是不知道如何讓它工作。此外，我認爲這樣做會幫助我瞭解更多關於位和效率等內容。如果你們認爲不然，我會很樂意接受任何其他建議。 – emschorsch 2012-01-09 07:44:29

據我所知，你是對的。字符串的C++實現將在O（n）時間內執行插入操作。它將字符串視爲字符數組。

對於您的數值實現，爲什麼不將數字存儲爲整數數組並將其轉換爲僅用於輸出的字符串？

來源

2012-01-09 07:40:28 nmjohn

我不確定，對不起。 – nmjohn 2012-01-09 08:00:23

對於std::string的所有實際實現可能是正確的。在這種情況下，您可能希望將數字反向存儲（儘管在其他方面可能很笨拙），或者使用類似std::deque<char>的東西。更好的是，使用std::deque<unsigned long long>，這將減少涉及的操作次數。

當然，對於真正的使用你通常要使用現有的庫，而不是自己動手。

來源

2012-01-09 07:40:01

那麼出列列表只是標準庫的實現嗎？ – emschorsch 2012-01-09 07:47:24

@emschorsch：沒有。 deque爲隨機訪問元素和在任一端插入/刪除提供了持續的複雜性（一個列表在任何地方都會有不斷的複雜度插入/刪除，但是線性複雜度隨機訪問元素）。 – 2012-01-09 08:08:22

插入字符串的效率

回答

相關問題