Insert a String To a Sorted String list without using native c++ functions

Question

I have to insert a string inside an already sorted list of strings, what is the best way to achieve this to find the exact position to insert without having to sort all the list and not adding the string upfront. I just need to find the position to insert.

I do have a function which Compares 2 strings compare(first-string ,second-string) this function gives me true if first string has to be placed ahead of second string false in other way around. It is expected to use this function.

The List used in my scenario is not a c++ std::list but a customized class which handles some functions of a list.

Answer 1

If you arrived at a parking place where each spot was named with a letter of the alphabet in order from A to Z.

And then I tell you that you can park at letter P.

How would you find that spot ?

Answer 2

Shouldn't you be able to loop through your list, and do a comparison for each item, where you grade each string on how close they are too each other. Say you got a list of strings like this: ["aa", "ab", "bc", "cc"] and you wanted to insert "bb". How similar is "bb" to "aa", answer is 0. Next iteration. How similar is "bb" to "ab": 1. Now we got an increase by one. Mark down the position and continue to loop. How similiar is "bb" to "bc": 1. Next loop. How similar is "bb" to cc: 0. So when we got a decrease we now know that the position of where "bb" should be placed has been passed. Which means that we can go back and search more thoroughly.

Here is a fully working function:

    void InsertAZ(list<string>& strings, string&& str) {
        std::list<string>::iterator it;
        it = strings.begin();
        for (auto s : strings) {
            if ((s > str) == 1) {
                strings.insert(it, str);
                break;
            }
            ++it;
        }
    }

    int main()
    {
        list<string> strings = { "aaa", "aab", "aac", "aba", "abb", "abc", "aca", "acb", "acc", "baa", "bab", "bac", "bba", "bbb", "bbc", "bca", "bcb", "bcc", "caa", "cab", "cac", "cba", "cbb", "cbc", "cca", "ccb", "ccc" };

        InsertAZ(strings, "bab");

        cin.get();
    }