### ivan100sic's blog

By ivan100sic, history, 3 months ago, ,

I've never seen anyone use this in competitive programming (or anywhere really) but it might be useful:

In C++ you can use the basic_string class template instead of vector for "simple" types [1]. It works just like vector but also allows you to use a few convenient member functions and operators just like with strings, most notably operator+ and operator+=. See the following code:

#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
basic_string<int> a;

cin >> n;
for (int i=0; i<n; i++) {
int x;
cin >> x;
a += x;
}

a += a;
a = a.substr(n/2, n);

cout << (a + a).find({1, 2, 1}) << '\n';
}


[1] Although I'm not 100% sure, "simple" is any primitive type, std::pair of simple types, etc. Do not use this with vectors, strings, sets, maps and similar types. And for this reason please don't typedef vector as basic_string.

•
• +255
•

 » 3 months ago, # |   +30 Maybe it is not used because of the simple type thing, but anyways thank you for this! Very useful stuff!
 » 3 months ago, # |   +29 Thanks for sharing! Now I can write some C++ code more concise like Python.
 » 3 months ago, # | ← Rev. 2 →   +17 I like this idea also. Used basic_string for some codes when intense vector concatenation or splitting was needed.Also, there is a difference when initializing basic_string and vector. You can write vector a(5); vector a(5, 0); for creating a vector with five zeros, but basic_string a(5); won't compile, only basic_string a(5, 0); will work.
•  » » 3 months ago, # ^ |   +21 Thanks for the tips! Forcing the programmer to provide the value with which the array will be initialized seems like an advantage to me.
 » 3 months ago, # |   +13 And why exactly can't you use vector or basic_string as underlying type?
•  » » 3 months ago, # ^ |   0 This code crashes on my computer and also on Codeforces: #include using namespace std; int main() { basic_string a; a += "hello"; } This also crashes: #include using namespace std; int main() { basic_string> a; } This works fine on my computer and prints what you'd expect but crashes on Codeforces: #include using namespace std; int main() { basic_string> a; cout << a.size() << '\n'; vector b; b = {1, 2, 3}; a += b; cout << a.size() << '\n'; cout << a[0][1] << '\n'; } If anyone has any idea what's going on here please share it with us. It's easy to get the stack trace but for me it's useless because I find it really difficult to understand STL code.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +11 Observations like "This works fine on my computer and prints what you'd expect but crashes on Codeforces" are fairly common once your code contains undefined behavior, and that's precisely where we are with your example.The specification for basic_string states that if you use basic_string, charT must be a non-array POD ("plain old data") type.My best guess for the crashes: The actual implementation of basic_string does some ugly low-level stuff it can do with plain old data types, such as copying whole pieces of memory when resizing the structure. This may break stuff as soon as you use a basic_string with some type T that has non-trivial copy constructors, move constructors and/or destructors -- the basic_string implementation won't call them.One particular thing that's going on inside most basic_string implementations (and that may or may not lead to these crashes, and also ugly compilation errors if you try to do basic_string) is the "short string optimization" -- if your string is short, it is stored directly in the instance (instead of allocating it on the heap and storing the pointer). Hacks that make this work with POD types have a good chance to break if you plug in something unexpected.Edit: formatting, Codeforces ate the s when I didn't put them in as code.
•  » » » » 3 months ago, # ^ |   0 I also suspected this.That's why I warned people not to use basic_string with non-POD data types. However the fact that the program did not crash with T = vector was a bit surprising to me.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +1 // Comment with some useless investigations Spoiler#include #include using namespace std; int main() { basic_string> a; } To be honest I don't understand why it can be compiled because on my computer there is such code in basic_string.h (and segfault happens deeply in stl because of the element of union, I checked) Spoiler union { _CharT _M_local_buf[_S_local_capacity + 1]; size_type _M_allocated_capacity; }; where _CharT is map in this particular caseBTW there will be compilation error with Visual C++ SpoilerInvocation failed [COMPILATION_ERROR]Can't compile file:program.cppc:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\xstring(506) : error C2621: member 'std::_String_val<_Elem,_Alloc>::_Bxty::_Buf' of union 'std::_String_val<_Elem,_Alloc>::_Bxty' has copy constructor with [ _Elem=std::map, _Alloc=std::allocator> ] c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\xstring(509) : see reference to class template instantiation 'std::_String_val<_Elem,_Alloc>::_Bxty' being compiled with [ _Elem=std::map, _Alloc=std::allocator> ] c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\xstring(522) : see reference to class template instantiation 'std::_String_val<_Elem,_Alloc>' being compiled with [ _Elem=std::map, _Alloc=std::allocator> ] program.cpp(6) : see reference to class template instantiation 'std::basic_string<_Elem>' being compiled with [ _Elem=std::map ]