Нужно ли сортировать вектор <int>, если они были добавлены в вектор по порядку?

Question

Нужно ли сортировать мой вектор, если элементы были последовательно считаны из файла, который уже был отсортирован?Я не хочу нести штраф за производительность, если в этом нет необходимости.Для справки, это то, что я использую для его сборки, и каждый элемент находится в порядке, в котором он читается.

Отредактировано после комментария @dribeas

std::vector<int> split(const std::string &s, char delim) {
    std::vector<int> elems;
    std::stringstream ss(s);
    std::string item;
    while(std::getline(ss, item, delim)) {
        elems.push_back(static_cast<int>(atoi(item.c_str())));
    }
    return elems;
}

Answer 1

Нет, вам не нужно сортировать вектор. push_back добавляет элементы в конец явно.

Обратите внимание, что ваш API принимает elems, а также возвращает его (по ссылке). Что происходит с любым содержимым, которое вектор уже содержит?

Answer 2

Если вы спрашиваете, будет ли std::vector сохранять порядок, в котором вы помещаете на него элементы, тогда да. Это очень большая часть контракта.

Answer 3

При условии, что вектор был пуст , когда вы начали (это не ясно из вашего исходного кода кода), и элементы были добавлены в том порядке, в котором вы хотите, нет, вам не нужно сортировать, потому что push_back помещает элементы в назад (конец) вектора:

Добавляет новый элемент в конце вектора после его текущего последнегоelement.

---

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

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

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

std::vector<int> &split (const std::string &s, char sep, std::vector<int> &vec)
{
    std::stringstream ss (s);
    std::string item;
    while (std::getline (ss, item, sep))
        vec.push_back (static_cast<int> (atoi (item.c_str ())));

    bool sorted = true;
    for (int i = vec.size() - 1; (i > 0) && sorted; i--)
        sorted = (vec[i] >= vec[i-1]);
    if (!sorted) {
        // Sort it here.
    }

    return vec;
}

Это будетбыть относительно быстрым сканированием элементов, чтобы определить, отсортированы они или нет (и только до тех пор, пока не будет найдена first группа не по порядку).

Если не отсортировано, будет выполнена сортировкаих с вашим любимым алгоритмом сортировки (батареи не включены), в противном случае он просто вернется.

---

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

std::vector<int> split (const std::string &s, char delim) {
    std::vector<int> elems;
    std::stringstream ss (s);
    std::string item;
    int lastOne = std::numeric_limits<int>::min ();
    bool isSorted = true;

    while (std::getline(ss, item, delim)) {
        int thisOne = atoi (item.c_str ());
        if (thisOne < lastOne) isSorted = false;
        elems.push_back (static_cast<int> (thisOne));
        lastOne = thisOne;
    }

    if (!isSorted) {
        // Sort it here.
    }

    return elems;
}

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

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