2.7. Analysis of String Operators¶
Prior to C++11 the string class was not required to store its character elements contiguously. Now string acts much like the vector class, except for some string optimizations and other minor differences.
C++11 strings use contiguous storage locations in an underlying (typically larger) array just like vectors do. Due to this, the character elements in strings can be accessed and traversed with the help of iterators, and they can also be accessed randomly using indexes.
Like vectors, strings have a dynamic size meaning that whenever a new character is inserted or deleted, their size changes automatically. Just like vectors, new elements can be inserted into or deleted from any part of a string, and automatic reallocation for other existing items in the string is applied.
Indexing and assigning a new character to an index position
that already exists both take
Now that we have seen how performance can be measured concretely you can look at Table 3 to see the Big-O efficiency of all the basic string operations and you will see a striking resemblance to vectors because the implementations are so similar.
Operation |
Big-O Efficiency |
|---|---|
index [] |
O(1) |
index assignment = |
O(1) |
push_back() |
typically O(1) |
pop_back() |
O(1) |
erase(i) |
O(n) |
insert(i, item) |
O(n) |
find(srt, stp, item) |
O(log n) or O(n) |
reserve() |
O(n) |
begin() |
O(1) |
end() |
O(1) |
size() O(1) |
|
Just like vectors, the push_back() operation is