27

What is the fundamental difference, if any, between a C++ std::vector and std::basic_string?

8
  • 1
    Check the docs, they have different interfaces. If you specified the actual problem you are solving then the answers could have also been more specific. Commented Dec 29, 2010 at 19:12
  • 1
    @Gene: They do have different interfaces, but both implement everything necessary to be an STL sequence container. Commented Dec 29, 2010 at 19:17
  • 1
    @Gene: I'm not solving any particular problem, I'm just curious why I should choose one or the other for various purposes: I'm not counting the existence of some additional string like methods as fundamental. I don't really count performance as fundamental either. However validity of iterators several replies mention definitely is. And I have a vague suspicion the data type for a string must have a "Zero like" value to put on the end of data() method (got from a traits thingy).
    – Yttrill
    Commented Dec 29, 2010 at 20:06
  • 4
    FYI: string originally wasn't an STL container. Against the advice of Pete Becker, the whole rest of the committee decided to make it one. This made it like vector, and removed the possibility of many optimisations. In retrospect I think Pete Becker was actually right.
    – Yttrill
    Commented Dec 29, 2010 at 20:10
  • @Yttrill Was this intended as a discussion only question? It seems that some of these answers are pretty through, is there a reason that none of them have been accepted? Commented Feb 22, 2016 at 16:05

7 Answers 7

23
  • basic_string doesn't call constructors and destructors of its elements. vector does.

  • swapping basic_string invalidates iterators (enabling small string optimization), swapping vectors doesn't.

  • basic_string memory may not be allocated continuously in C++03. vector is always continuous. This difference is removed in C++0x [string.require]:

    The char-like objects in a basic_string object shall be stored contiguously

  • basic_string has interface for string operations. vector doesn't.

  • basic_string may use copy on write strategy (in pre C++11). vector can't.

Relevant quotes for non-believers:

[basic.string]:

The class template basic_string conforms to the requirements for a Sequence Container (23.2.3), for a Reversible Container (23.2), and for an Allocator-aware container (Table 99), except that basic_string does not construct or destroy its elements using allocator_traits::construct and allocator_- traits::destroy and that swap() for basic_string invalidates iterators. The iterators supported by basic_string are random access iterators (24.2.7).

5
  • As far as I can tell, that quote isn't from 'the standard' but from the C++0x draft. That's fine and worth mentioning, but you need to qualify it with "In C++0x...".
    – GManNickG
    Commented Dec 29, 2010 at 19:55
  • @GMan: Hmm, seems like you're right. But only the formulation is different, C++98 still says that it only allocates and deallocates the elements. This change is just a clarification. Commented Dec 29, 2010 at 20:39
  • So is there a consensus on this? Individual ctor/dtor/mov/assign ops are likely to be more expensive than bitblits, so there's good reason to desire string elements be PODs, but is it required? Couldn't the POD and non-POD cases be split with specialisations based on a trait? Or at least common cases eg char? Couldn't this be done for vector too?
    – Yttrill
    Commented Dec 29, 2010 at 20:51
  • @BillyONeal Incidentally, there's only one command for default allocation of elements that basic_string provides, and that's resize, which, "initializes new characters to CharT()". An example for the non-believers: ideone.com/UjQzrM Commented Feb 18, 2016 at 17:43
  • 1
    @Johnathan Mee: Your use of basic_string is nonconforming, so you get undefined behavior; which happens to be not calling copy ctors in this case. basic_string is only valid for types with a char_traits<T>, and char_traits<T>::copy, for example, is not required to call constructors. (All of the required-to-be-provided char_traits specializations can conformingly implement char_traits<T>::copy as a call to memcpy, since that's valid for char/wchar_t/char16_t/char32_t) Commented Feb 18, 2016 at 20:54
13

basic_string gives compiler and standard library implementations, a few freedoms over vector:

  1. The "small string optimization" is valid on strings, which allows implementations to store the actual string, rather than a pointer to the string, in the string object when the string is short. Something along the lines of:

    class string
    {
        size_t length;
        union
        {
            char * usedWhenStringIsLong;
            char usedWhenStringIsShort[sizeof(char*)];
        };
    };
    
  2. In C++03, the underlying array need not be contiguous. Implementing basic_string in terms of something like a "rope" would be possible under the current standard. (Though nobody does this because that would make the members std::basic_string::c_str() and std::basic_string::data() too expensive to implement.)
    C++11 now bans this behavior though.

  3. In C++03, basic_string allows the compiler/library vendor to use copy-on-write for the data (which can save on copies), which is not allowed for std::vector. In practice, this used to be a lot more common, but it's less common nowadays because of the impact it has upon multithreading. Either way though, your code cannot rely on whether or not std::basic_string is implemented using COW.
    C++11 again now bans this behavior.

There are a few helper methods tacked on to basic_string as well, but most are simple and of course could easily be implemented on top of vector.

2
  • I don't like to think of (1) as a reason for picking or using std::string it is an unintended side affect of the standard wording that has been tightened in the new standard. (2) was a good reason for using std::string as it made returning strings from methods very efficient (practically no cost) unfortunately that is being removed because of requirements for parallelism (though from reading the paper that recommends this; it looks like rope will take up that mantel of COW eventually (we will have to wait and see if this works out). Commented Dec 29, 2010 at 21:43
  • @Martin: This is true. OTOH move semantics gets rid of LOTS of the cases where COW implementations sped things up :) Commented Dec 29, 2010 at 21:46
6

The key difference is that std::vector should keep its data in continuous memory, when std::basic_string could not to. As a result:

std::vector<char> v( 'a', 3 );
char* x = &v[0]; // valid

std::basic_string<char> s( "aaa" );
char* x2 = &s[0];     // doesn't point to continuous buffer
//For example, the behavior of 
std::cout << *(x2+1);
//is undefined.
const char* x3 = s.c_str(); // valid

On practice this difference is not so important.

10
  • Err.. that code example is perfectly valid. Now if you modified x2 using pointer arithmetic it's possible that it wouldn't be valid (depending on your compiler), but I'm unaware of any compiler who does this. Commented Dec 29, 2010 at 19:18
  • I'm not aware of such compiler too, but you shouldn't count on that x2 points to the continuous buffer, because C++ Standard doesn't give any guarantees. Commented Dec 29, 2010 at 19:21
  • 2
    Neither of them are valid actually. Neither object has any size and so the first element is actually one past the end and you can't dereference that element. Only the c_str() one is well defined. Commented Dec 29, 2010 at 19:21
  • @Kirill: My point is that your example doesn't demonstrate the continuous buffer aspect. If someone interprets x2 as a pointer to a single character (rather than a pointer to a null terminated C string) then the code is perfectly valid. For example, someone could do std::cout << *x2 and everything would be fine, but std::cout << *(x2 + 1) would be invalid. @Noah: Lol -- good point. Commented Dec 29, 2010 at 19:22
  • 1
    @Noah, updated the example. The point wasn't about initialization of these containers so I've skipped it. Commented Dec 29, 2010 at 19:25
4

TLDR: strings are optimized to only contain character primitives, vectors can contain primitives or objects

The preeminent difference between vector and string is that vector can correctly contain objects, string works only on primitives. So vector provides these methods that would be useless for a string working with primitives:

  1. vector::emplace
  2. vector::emplace_back
  3. vector::~vector

Even extending string will not allow it to correctly handle objects, because it lacks a destructor. This should not be viewed as a drawback, it allows significant optimization over vector in that string can:

  1. Do short string optimization, potentially avoiding heap allocation, with little to no increased storage overhead
  2. Use char_traits, one of string's template arguments, to define how operations should be implemented on the contained primitives (of which only char, wchar_t, char16_t, and char32_t are implemented: http://en.cppreference.com/w/cpp/string/char_traits)

Particularly relevant are char_traits::copy, char_traits::move, and char_traits::assign obviously implying that direct assignment, rather than construction or destruction will be used which is again, preferable for primitives. All this specialization has the additional drawbacks to string that:

  1. Only char, wchar_t, char16_t, or char32_t primitives types will be used. Obviously, primitives of sizes up to 32-bit, could use their equivalently sized char_type: https://stackoverflow.com/a/35555016/2642059, but for primitives such as long long a new specialization of char_traits would need to be written, and the idea of specializing char_traits::eof and char_traits::not_eof instead of just using vector<long long> doesn't seem like the best use of time.
  2. Because of short string optimization, iterators are invalidated by all the operations that would invalidate a vector iterator, but string iterators are additionally invalidated by string::swap and string::operator=

Additional differences in the interfaces of vector and string:

  1. There is no mutable string::data: Why Doesn't std::string.data() provide a mutable char*?
  2. string provides functionality for working with words unavailable in vector: string::c_str, string::length, string::append, string::operator+=, string::compare, string::replace, string::substr, string::copy, string::find, string::rfind, string::find_first_of, string::find_first_not_of, string::flind_last_of, string::find_last_not_of, string::operator+, string::operator>>, string::operator<<, string::stoi, string::stol, string::stoll, string::stoul, string::stoull, string::stof, string::stod, string::stold, stirng::to_string, string::to_wstring
  3. Finally everywhere vector accepts arguments of another vector, string accepts a string or a char*

Note this answer is written against C++11, so strings are required to be allocated contiguously.

0

A vector is a data structure which simulates an array. Deep inside it is actually a (dynamic) Array.

The basic_string class represents a Sequence of characters. It contains all the usual operations of a Sequence, and, additionally, it contains standard string operations such as search and concatenation.

You can use vector to keep whatever data type you want std::vector<int> or <float> or even std::vector< std::vector<T> > but a basic_string can only be used for representing "text".

6
  • I'm sure I could find a way to make a basic_string full of doubles or something equally evil and have it actually "work". Commented Dec 29, 2010 at 19:15
  • Well, most implementations implement basic_string in terms of something like vector. And any type for which a char_traits class is defined will work with std::basic_string, even if you made up a char_traits<double> (as written in @Noah's comment) Commented Dec 29, 2010 at 19:16
  • @Billy - not true. Some of the same techniques may very well be used in both but I've NEVER seen a basic_string implemented in terms of vector. In fact, one very common implementation, that distributed with MSVC++, is VERY different since they use the small string optimization (anything small enough to fit in a pointer is just stuck in the pointer to buffer rather than allocating one). Commented Dec 29, 2010 at 19:17
  • @Noah: If you read my comment again, it says "Something like vector", not "vector" -- those two words are important. (What I meant was it's usually some form of dynamic array) Commented Dec 29, 2010 at 19:19
  • Not wishing to answer my own question yet .. but what about the new string types such as UTF-8 string things? These would be less array like, would they not? How do they fit in with basic_string?
    – Yttrill
    Commented Dec 29, 2010 at 20:19
0

The basic_string provides many string-specific comparison options. You are right in that the underlying memory management interface is very similar, but string contains many additional members, like c_str(), that would make no sense for a vector.

3
  • I don't think there's any such thing as a vector using small string optimization. Haven't gone out looking for one but I'm fairly sure it's not out there. It wouldn't be as useful. Truth is that the two things are just plain different. They have different purposes and so are often implemented VERY differently though a naive approach may be similar in both. Commented Dec 29, 2010 at 19:20
  • @Noah: Hence why I said "interface".
    – Puppy
    Commented Dec 29, 2010 at 19:26
  • Which comparisons are string specific? Given the element data type is variable in both cases, things like lexicographical comparison make as much sense for vectors as strings. Of course a case insensitive comparison would be string specific, but then string wouldn't be polymorphic.
    – Yttrill
    Commented Dec 29, 2010 at 20:22
0

One difference between std::string and std::vector is that programs may construct a string from a null-terminated string, whereas with vectors they cannot.

std::string a = "hello";          // okay
std::vector<char> b = "goodbye";  // compiler error

This often makes strings easier to work with.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.