Is the small string optimization undesirable?

Question

In the following code we can demonstrate a bug related to small/big strings when they are held in a vector (this is because small strings may not get allocated on the heap).

One can argue that this is not a bug in the standard library but the programmer's fault, for taking a reference to something that could disappear in the process of reallocation. But as a programmer I'm not supposed to know the internal implementation of a data structure

#include<iostream>
#include<vector>


int main()
{
    std::vector<std::string> v;
    v.push_back("123456789abcdefg"); //bug if less than 16 characters
    const char* first = v[0].c_str();
    for (auto s : { "hi","guys" })
        v.push_back(s);

    std::cout << first << std::endl;

    std::cin.get();

}

You may not need to know the implementation details of a component you are using, but you definitely do need to know the contract. — BoBTFish, Mar 26 '19 at 07:48
Which C++ runtime? Because they have different implementations! — Matthieu Brucher, Mar 26 '19 at 07:48
Related: [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) — P.W, Mar 26 '19 at 07:52
Possible duplicate of [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) — skratchi.at, Mar 26 '19 at 07:58
I see an error in the above code. I don't see any bug in the STL. The validity of `first` after insertion into the `vector` is unknown as clearly stated by the standard. If you can't know the state of `first` using it is UB. Thus this is a bad program. — Martin York, Mar 26 '19 at 08:03
I edited the post to hopefully make it less polarizing. It's a good question, but the tone of it was a bit off-putting. Please roll back if you feel I changed too much. — StoryTeller - Unslander Monica, Mar 26 '19 at 08:45
@StoryTeller thanks, I'm not a good English writer (not my native language) — Soulimane Mammar, Mar 26 '19 at 08:49

score 10 · Accepted Answer · answered Mar 26 '19 at 07:49

10

but as a programmer I'm not supposed to know the internal implementation of a data structure

You are meant to know the iterator invalidation rules of the data structures in the standard library that you use. They are part of the public contract of every container, and make it easy enough to deduce when an iterator/reference/pointer to something in a standard library container may be used without risk of undefined behavior.

It's no different than any other interface in any other language that hands out handles to something. The handle is only going to be valid as long as certain conditions are met.

And it's not as though C++ doesn't give you the tools to safeguard your code. You can create containers of smart pointers if you need certain more elaborate ownership semantics, and different containers have different iterator invalidation rules (paid for by run-time or memory complexity).

answered Mar 26 '19 at 07:49

StoryTeller - Unslander Monica

165,132
21
377
458

1

It is not really about the iterator invalidation rule, even so it is related to it. The OP is writing `const char* first = v[0].c_str()`, so no iterator is stored. If the vector would be defined as `std::vector> v` and the OP would write `const char* first = v[0]->c_str()` then the code would be fine. – t.niese Mar 26 '19 at 08:00
2

@t.niese - But it is. The rules invalidate any handle to the `std::shared_ptr`, but it has no bearing on the pointee because that's the design goal of the shared pointer. The pointer breaks the connection. A `std::string` is not designed that way. And besides, the iterator invalidation rules are nothing more than a formal attempt to codify what you describe intuitively. – StoryTeller - Unslander Monica Mar 26 '19 at 08:05
For me when the iterator invalidation rule says: "Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence" it's kind of telling me about the internal working of the data structure and in theory I'm not supposed to even know that reallocation is taking place – Soulimane Mammar Mar 26 '19 at 08:19
4

@SoulimaneMammar - By what theory? And you should also note, that you don't know if and when a relocation is taking place. The reference is invalid the moment you use certain operations, that's it. The fact you can divine something about the implementation doesn't mean you can't program to the contract alone. – StoryTeller - Unslander Monica Mar 26 '19 at 08:24
@StoryTeller I agree with you. Perhaps the rule would be more precise if it was written as "Insertion of any kind invalidates all the references, pointers, and iterators referring to the elements in the sequence" without referring to "Relocation" – Soulimane Mammar Mar 26 '19 at 08:44
@SoulimaneMammar - Perhaps. But C++ tries to walk the fine balance between being a language of abstraction and a low level, fit for system programming, language. It's hard to get it perfect. – StoryTeller - Unslander Monica Mar 26 '19 at 08:49
1

I also believe that `std::vector` is the only container where reallocation is explicitly mentioned. So there's that at least. – StoryTeller - Unslander Monica Mar 26 '19 at 08:50

Is the small string optimization undesirable?

1 Answers1