ivan100sic's blog

[C++] basic_string
By ivan100sic, history, 6 years ago, In English

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.

  • Vote: I like it
  • +255
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Maybe it is not used because of the simple type thing, but anyways thank you for this! Very useful stuff!

→ Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Thanks for sharing! Now I can write some C++ code more concise like Python.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

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 and vector. You can write

vector<int> a(5);
vector<int> a(5, 0);

for creating a vector with five zeros, but

basic_string<int> a(5);

won't compile, only

basic_string<int> a(5, 0);

will work.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Thanks for the tips! Forcing the programmer to provide the value with which the array will be initialized seems like an advantage to me.

    → Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

And why exactly can't you use vector or basic_string as underlying type?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This code crashes on my computer and also on Codeforces:

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

int main() {
	basic_string<string> a;
	a += "hello";
}

    This also crashes:

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

int main() {
	basic_string<map<int, int>> a;
}

    This works fine on my computer and prints what you'd expect but crashes on Codeforces:

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

int main() {
	basic_string<vector<int>> a;
	cout << a.size() << '\n';
	vector<int> 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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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<int> was a bit surprising to me.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      // Comment with some useless investigations

      Spoiler

      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

      BTW there will be compilation error with Visual C++

      Spoiler
      → Reply