C++:字符串向量的随机访问时间如何工作？

Question

我知道一个简单的int向量具有O(1)随机访问时间,因为在给定所有元素具有相同大小的情况下,很容易计算第x个元素的位置.

现在最新的字符串向量？

由于字符串长度不同,它不能有O(1)随机访问时间,可以吗？如果可以的话,背后的逻辑是什么？

谢谢.

更新:

答案非常简洁明了,谢谢大家的帮助.我接受了乔伊的回答,因为它简单易懂.

Answer 1

该向量确实具有O(1)访问时间.

无论字符串对象的大小如何,它们都具有相同的大小(在给定的实现上).通常,字符串对象包含指向已分配内存的指针,该内存保存字符串数据.

所以,如果s是a std::string,则sizeof s是常量且等于sizeof(std::string),但s.size()取决于字符串值.载体只关心sizeof(std::string).

Answer 2

The string references are stored in one location. The strings may be stored anywhere in memory. So, you still get O(1) random access time.

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


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