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
.
Maybe it is not used because of the simple type thing, but anyways thank you for this! Very useful stuff!
Thanks for sharing! Now I can write some C++ code more concise like Python.
I like this idea also. Used
basic_string<int>
for some codes when intense vector concatenation or splitting was needed.Also, there is a difference when initializing
basic_string
andvector
. You can writefor creating a vector with five zeros, but
won't compile, only
will work.
Thanks for the tips! Forcing the programmer to provide the value with which the array will be initialized seems like an advantage to me.
And why exactly can't you use vector or basic_string as underlying type?
This code crashes on my computer and also on Codeforces:
This also crashes:
This works fine on my computer and prints what you'd expect but crashes on Codeforces:
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.
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>
, 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<T>
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<MyCustomClass>
) 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
<T>
s when I didn't put them in as code.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 withT = vector<int>
was a bit surprising to me.// Comment with some useless investigations
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)
where _CharT is
map<int, int>
in this particular caseBTW there will be compilation error with Visual C++
Invocation failed [COMPILATION_ERROR]
Can't compile file:
program.cpp
c:\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