Блог пользователя Qualified

Inserting a character in the beginning of a string

Автор Qualified, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Example
→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    It's O(n)

    → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить