C++：字符串向量的隨機存取時間是如何工作的？

我知道一個簡單的int向量有O（1）個隨機存取時間，因爲它很容易計算第x個元素的位置，因爲所有元素都具有相同的大小。C++：字符串向量的隨機存取時間是如何工作的？

現在怎麼了字符串向量？

由於字符串長度不同，它不能有O（1）隨機存取時間，可以嗎？如果可以，它背後的邏輯是什麼？

謝謝。

更新：

的答案是非常明確和簡潔的，謝謝大家的幫助。我接受了喬伊的回答，因爲它簡單易懂。

來源

2010-09-20 johnny-john

一個字符串及其內容不是一回事。對象的大小始終保持不變。 – GManNickG 2010-09-20 16:37:19

該矢量具有O（1）訪問時間。

無論字符串對象的大小如何，字符串對象的大小都是相同的（在給定的實現上）。通常，字符串對象包含一個指向分配內存的指針，該內存包含字符串數據

所以，如果s是std::string，然後sizeof s是恆定的，等於sizeof(std::string)，但s.size()依賴於字符串值。載體只關心sizeof(std::string)。

來源

2010-09-20 16:35:14

+1我喜歡'size'和'sizeof'之間的區別！ – fredoverflow 2010-09-20 17:01:43

@FredOverflow：謝謝。我重新閱讀我自己的答案，並意識到我可以更清楚地說明「字符串對象的大小」和「它所代表的字符串的大小」.-) – 2010-09-20 17:08:25

因爲字符串對象具有與其他任何類型一樣的固定大小。不同之處在於字符串對象在堆中存儲自己的字符串，並且它保持指向固定大小的字符串的指針。

來源

2010-09-20 16:35:03 AraK

對於小字符串優化，它可能也直接存儲在字符串實例中。 – 2010-09-20 16:45:00

std :: string中的實際字符串通常只是一個指針。字符串的大小總是相同的，即使它保存的字符串的長度不同。

來源

2010-09-20 16:35:44 nos

Erm ..通常它比指針大一些（通常情況下，字符串的大小和分配的內存塊的大小至少有一個計數器）。但仍然不是字符串本身的大小。 – 2010-09-20 17:55:00

是的，我的意思是數據的實際內容，可能還有更多 – nos 2010-09-20 18:34:32

你已經得到了很多答案（例如Steve Jessop和Arak的），這些答案已經基本正確。我將僅添加一個小細節：std::string的許多當前實現使用所謂的短字符串優化（SSO），這意味着它們會在字符串對象本身中分配一個小的，固定的空間量，以用於存儲短字符串，並且只有當/如果長度超過了字符串對象本身分配的長度，它實際上是在堆上分配單獨的空間來存儲數據。

就字符串矢量而言，這並沒有真正的區別：每個字符串對象都有固定的大小，而不管字符串本身的長度。與SSO不同的是，固定大小更大 - 在很多情況下，字符串對象而不是在堆上分配了用於保存實際數據的塊。

來源

2010-09-20 16:43:00

你確定libstdC++是「當前許多實現」之一嗎？ – sellibitze 2010-09-20 17:26:08

@sellibitze：手，我不記得了。我已經看到至少有一個g ++的庫有它，另一個沒有，但是我不記得哪個是哪個... – 2010-09-20 17:30:45

GNU的std :: string的大小爲4（在我的機器上）。它只是一個指向分配blob的指針，其中包含所有元數據和字符串數據。種類相反的短字符串優化。 – 2010-09-20 17:53:30

字符串引用存儲在一個位置。字符串可以存儲在內存中的任何位置。所以，你仍然得到O（1）隨機存取時間。

--------------------------- 
| 4000 | 4200 | 5000 | 6300 | <- data 
--------------------------- 
[1000] [1004] [1008] [1012] <- address 


[4000] [4200] [5000]  [6300]  <- starting address 
"string1" "string2" "string3" "string4" <- string

來源

2010-09-20 16:48:24

非常好的視覺表現！ – 2010-09-20 16:51:04

C++：字符串向量的隨機存取時間是如何工作的？

回答

相關問題