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

Question

Я пытался написать программу, вставляющую элементы в вектор, сортируя их в алфавитном порядке. Элемент перед вставкой сравнивается с другим до тех пор, пока он не станет больше, чем уже вставленный элемент. После этого предполагалось добавить сравниваемый элемент с помощью .insert(). Я хочу реализовать это без использования алгоритмов сортировки.

std::string name;
std::vector<std::string> students;
std::vector<std::string>::iterator beg = students.begin();
  while (std::cin>>name){
        for (std::vector<std::string>::iterator e = students.end() ; beg !=e ; ) {
            if (!name.compare(*beg))
            {
                students.insert(beg, name);
                break;
            }
            else
                beg++;      
         }
    }

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

Answer 1

Это сравнение

if (!name.compare(*beg))

не имеет смысла. Проверяется только то, что две строки равны.

Рассмотрим, например, следующий фрагмент кода

std::string s1 = "one";
std::string s2 = "one";
std::cout << !s1.compare( s2 ) << '\n';

Его вывод 1. Это означает, что два объекта равны.

Более того, цикл for может заканчиваться без нахождения позиции, в которую можно вставить строку, например, когда изначально вектор пуст.

И это утверждение

std::vector<std::string>::iterator beg = students.begin();

должен быть внутри внешнего цикла while. То есть итератор должен заново инициализироваться в каждой итерации цикла.

Вот демонстрационная программа, которая показывает, как можно реализовать внутренний цикл.

#include <iostream>
#include <string>
#include <vector>
#include <iterator>

void insert( std::vector<std::string> &v, const std::string &s )
{
    auto it = std::begin( v );

    while (  it != std::end( v ) && not( s < *it ) ) ++it;

    v.insert( it, s );
}

int main() 
{
    std::string names[] = { "One", "Two", "Three" };
    std::vector<std::string> v;

    for ( const auto &s : names )
    {
        insert( v, s );
    }


    for ( const auto &s : v ) std::cout << s << ' ';
    std::cout << '\n';

    return 0;
}

Выход программы

One Three Two

То есть строки вставляются в порядке возрастания.

Относительно вашего фрагмента кода циклы могут выглядеть как

while ( std::cin >> name )
{
    auto it = std::begin( students ); // or students.begin()

    while (  it != std::end( students ) && not( name < *it ) ) ++it;

    students.insert( it, name );
}

Также вместо внутреннего whileВ цикле вы можете использовать стандартный алгоритм std::find_if. Например

#include <iostream>
#include <string>
#include <functional>
#include <vector>
#include <iterator>
#include <algorithm>

//...

while ( std::cin >> name )
{
    using namespace std::placeholders;
    auto it = std::find_if( std::begin( students ), std::end( students ), 
                            std::bind( std::greater_equal<>(), _1, name ) );

    students.insert( it, name );
}

Answer 2

Для пустого вектора begin и end одинаковы, следовательно, вы никогда ничего не вставляете.

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

std::string name;
std::vector<std::string> students;
while (std::cin>>name){
    students.push_back(name);
}
std::sort(students.begin(),students.end());

В качестве альтернативы, замените последнюю строку вашей любимой процедурой сортировки.