Какую структуру данных лучше выбрать?

Исполнение на ideone

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
  std::vector<std::string> Vec = {
    "Мама",
    "Мама мыла раму",
    "Мама мыла"
  };
  std::sort(Vec.begin(),Vec.end(),[](const std::string& a, const std::string& b) {
    return a.size()<b.size();       
  });
  for(const auto &i:Vec) std::cout << i << std::endl;
  return 0;
}

Вывод:

Мама
Мама мыла
Мама мыла раму

Проще всего взять vector<string>. Для сортировки по длине используйте std::sort с компаратором.

vector<string> v;
// ...
sort(v.begin(), v.end(), 
     [](const string& l, const string& r) { return (l.length() < r.length()); });

Как я понимаю, то это задание на составление самостоятельно абстрактной структуры данных и ее сортировки.

В противном случае вы могли бы использовать контейнер std::multiset, в котором элементы сами бы упорядочивались по возрастанию длин предложений без всякой сортировки. Например,

#include <iostream>
#include <string>
#include <set>
int main()
{
    auto compare = [](const std::string &a, const std::string &b)
    {
        return a.length() < b.length();
    };
    std::multiset< std::string, decltype(compare)> sentences(compare);
    for (const std::string & s : { "123", "12", "12345", "1234", "1" })
    {
        sentences.insert(s);
    }
    for (const auto &s : sentences) std::cout << s << std::endl;
}

Вывод программы на консоль

1
12
123
1234
12345

Если вам надо разбить строку на предложения, то это можно сделать примерно следующим образом

#include <iostream>
#include <string>
#include <set>
int main()
{
    auto compare = [](const std::string &a, const std::string &b)
    {
        return a.length() < b.length();
    };
    std::multiset< std::string, decltype(compare)> sentences(compare);
    std::string text("I'm learning C++... How to write the program? I did it!");
    for (std::string::size_type pos = 0; pos != text.size(); )
    {
        auto last_pos = text.find_first_of(".?!", pos);
        if (last_pos == std::string::npos)
        {
            sentences.insert(text.substr(pos));
            pos = text.size();
        }
        else
        {
            while (last_pos < text.size() && text[last_pos] == '.') ++last_pos;
            sentences.insert(text.substr(pos, last_pos - pos + 1));
            while (++last_pos < text.size() &&
                (text[last_pos] == ' ' || text[last_pos] == '\t'));
            pos = last_pos;
        }
    }
    for (const auto &s : sentences) std::cout << s << std::endl;
}

Вывод программы на консоль:

I did it!
I'm learning C++...
How to write the program?

Использовать для такой задачи контейнер std::vector не эффективно, так как он будет постоянно перераспределять память при добавлении нового элемента, а затем еще потребуется сортировка.

Если говорить о собственноручно написании структуры данных для хранения предложений, то постройте односвязный список. В него также добавляйте новые элементы в порядке возрастания ключей.