6

I know a simple int vector have O(1) random access time, since it is easy to compute the position of the xth element, given all elements have the same size.

Now whats up with a string vector?

Since the string lengths vary, it can't have O(1) random access time, can it? If it can, what is the logic behind it?

Thanks.

Update:

The answers are very clear and concise, thank you all for the help. I accepted Joey's answer because it is simple and easy to understand.

johnny-john
  • 846
  • 2
  • 9
  • 19

5 Answers5

13

The vector does have O(1) access time.

String objects are all the same size (on a given implementation), regardless of the size of the string they represent. Typically the string object contains a pointer to allocated memory which holds the string data.

So, if s is a std::string, then sizeof s is constant and equal to sizeof(std::string), but s.size() depends on the string value. The vector only cares about sizeof(std::string).

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • @FredOverflow: Thanks. I re-read my own answer, and realized that I could be a *lot* more clear what I mean by "the size of the string object" and "the size of the string it represents" :-) – Steve Jessop Sep 20 '10 at 17:08
5

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
4

Because the string object has a fixed size just like any other type. The difference is that string object stores its own string on heap, and it keeps a pointer to the string which is fixed in size.

Khaled Alshaya
  • 94,250
  • 39
  • 176
  • 234
2

The actual string in a std::string is usually just a pointer. The sizeof a string is always the same, even if the length of the string it holds vary.

nos
  • 223,662
  • 58
  • 417
  • 506
  • Erm.. usually it's somewhat larger than a pointer (There's usually a counter for the size of the string and the size of the allocated memory block at least). But still not the size of the string itself. – Billy ONeal Sep 20 '10 at 17:55
  • Yes I meant the actual content of the data, there might be more – nos Sep 20 '10 at 18:34
2

You've gotten a number of answers (e.g., Steve Jessop's and AraK's) that are mostly correct already. I'll add just one minor detail: many current implementations of std::string use what's called a short string optimization (SSO), which means they allocate a small, fixed, amount of space in the string object itself that can be used to store short strings, and only when/if the length exceeds what's allocated in the string object itself does it actually allocate separate space on the heap to store the data.

As far as a vector of strings goes, this make no real difference: each string object has a fixed size regardless of the length of the string itself. The difference is that with SSO that fixed size is larger -- and in many cases the string object does not have block allocated on the heap to hold the actual data.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Are you sure that libstdc++ is among "many current implementations" ? – sellibitze Sep 20 '10 at 17:26
  • @sellibitze: Offhand, I don't remember. I've seen at least one library for g++ that had it and another that didn't, but offhand I don't remember which was which... – Jerry Coffin Sep 20 '10 at 17:30
  • GNU's std::string has size 4 (on my machine). It's just a pointer into an allocated blob, which contains all the metadata and the string data. Kind of the opposite of the short string optimisation. – Steve Jessop Sep 20 '10 at 17:53