Лучший алгоритм, чтобы проверить, отсортирован ли вектор

Question

Как лучше всего проверить, отсортирован ли std::vector? Есть ли что-то быстрее, чем проверка цикла v[i]<=v[i+1]? Это быстрее / чище с итераторами? Или на самом деле лучше просто каждый раз вызывать sort (хотя случай "v уже отсортирован" довольно распространен)?

Можно смело предположить, что вектор содержит только POD, обычно float с, а иногда double с и int с.

Размер вектора нетривиален (обычно несколько тысяч элементов), но не является экстремальным (не размером в гигабайт).

• в некоторых случаях мы сортируем вектор сразу после этого, однако в других случаях мы этого не делаем (это случай ошибки нашего алгоритма).
• мы уже используем флаг "IsSorted", когда это возможно.

Answer 1

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

Answer 2

Как уже отмечалось, предикатом для определения отсортированного состояния является O (n). Но из твоего упоминания о сортированном флаге я удивляюсь, не хочешь ли ты что-то вроде этого:

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

class ObjList {
public:
    ObjList() {};
    ~ObjList() {};

    bool isMember(const Item *);
    void add(const Item *, bool sort = false);

private:

    unsigned int last_sorted_d;

    bool sorted_d;
    unsigned int count_d;
    Item *store_d;
};

isMember () использует двоичный поиск по отсортированному диапазону элементов, а затем линейный поиск элементов после отсортированного диапазона. Вставка может инициировать сортировку элементов или нет, по выбору программиста. Например, если вы знаете, что будете добавлять тысячи элементов в узкий цикл, не сортируйте до окончательной вставки.

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

Answer 3

Для проверки отсортированного вы должны проверить каждый элемент. Так что v [i] <= v [i + 1] - самая быстрая проверка. </p>