Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Qualified's blog

Inserting a character in the beginning of a string

By Qualified, history, 6 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

Comments Comments (14)
| Write comment?
»
6 years ago, hide # |
 
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
→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    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.

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
      ← 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).

      → Reply
»
6 years ago, hide # |
 
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.

→ Reply