I need to insert a character into a string of letters that are in alphabetical order, and this character has to be placed where it belongs alphabetically.
For example I have the string string myString("afgjz"); and the input code
cout << "Input your character" << endl; char ch; cin >> ch; but how can I make it so that after inputting the char(say b) it is then added to the string on the proper position resulting in the string becoming "abfgjz".
You can use std::lower_bound to find the position to insert.
myString.insert(std::lower_bound(myString.begin(), myString.end(), ch), ch); A more generic solution would be having a function like
namespace sorted { template<class Container, class T> void insert(Container & object, T const & value) { using std::begin; using std::end; object.insert(std::lower_bound(begin(object), end(object), value), value); } } And then use
sorted::insert(myString, ch); Class std::string has the following insert method (apart from other its insert methods):
iterator insert(const_iterator p, charT c); So all what you need is to find the position where the new character has to be inserted. If the string has already the same character then there are two approaches: either the new character is inserted before the existent character in the string and in this case you should use standard algorithm std::lower_bound or the new character is inserted after the existent character in the string and in this case you should use standard algorithm std::upper_bound.
Here is a demonstrative program that shows how this can be done using standard algorithm std::upper_bound. You may substitute it for std::lower_bound if you like. Though in my opinion it is better to insert the new character after existent one because in some situation you can avoid moving characters after the target position that to insert the new character.
#include <iostream> #include <algorithm> #include <string> int main() { std::string myString( "afgjz" ); char c = 'b'; myString.insert( std::upper_bound( myString.begin(), myString.end(), c ), c ); std::cout << myString << std::endl; return 0; } The program output is
abfgjz 
std::string::insert()intarray of size 26. Then you can add a letter in O(1), by increasing the counter. Converting this array to astringcosts then O(n) time.