Qualified's blog

By Qualified, history, 4 years ago, In English

I would always do if I wanted to insert 'a' into the beginning of the string. reverse(s.begin(), s.end()); s += 'a'; reverse(s.begin(), s.end()); Is there a built-in function to insert a character in the beginning of a string?

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

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use insert(index,string) to insert string at any position of your string.

Example
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, but do you know the time complexity of each? The built-in method and my method.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +24 Vote: I do not like it

      Both methods are O(n) which is highly not recommended. Try to use deque instead. like:

      deque<char>dq;
      

      A simple code that takes input from a string and then places an F before the string:

      deque<char>dq;
      string s;
      cin>>s;
      for(int i=0;i<s.size();i++)
      dq.push_back(s[i]);
      dq.push_front('F');
      for(int i=0;i<dq.size();i++)
      cout<<dq[i];
      

      I hope this helped!

      Edit: The reason your method is O(n) is that you reverse the whole string which literally takes O(n). The method that the builtin insert takes O(n) is because when you insert a character, you need to shift all other characters in the memory block which takes O(n). But, deque allocates memory for both ends which causes an insertion/deletion time at beginning/ending to be O(1). But take care that deque has a little bit more constant time than string and vector(But it will not be that obvious).

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Thanks! BTW, you can just do for(auto i: dq) { cout << i << " "; }

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

          You are welcome!

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it +24 Vote: I do not like it

          In the same vein, you can even do

          copy(s.begin(),s.end(),back_inserter(dq));
          

          and

          copy(dq.begin(),dq.end(),ostream_iterator<char>(cout));
          

          and avoid writing loops completely.

          Edit: with spaces, it would be

          copy(dq.begin(),dq.end(),ostream_iterator<char>(cout," "));
          
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The simplest thing is to write s = 'a' + s. I'm not sure what is the complexity, but since it is just copying string I believe it cannot be bigger than linear.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    It's O(n)

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I want it to put the character in the beginning of the string and not the end of the string. Thanks tho

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

      This does put it at the begging of the string. Try it.

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

        Oh... That was my bad. I thought that you wrote s = s + 'a'. and not s = 'a' + s; Thanks!

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

      General TIP : Complexity of adding char at the end is O(n) if you are doing s = s + 'a' and O(1) if you are doing s += 'a'.

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

        Really? Do think about allocating space for a new buffer 1 byte more than the existing one and copying all characters of the string into the buffer then storing the character 'a' at the end.