Есть ли отсортированный контейнер в STL?

Я имею в виду следующее: у меня есть std::vector<Foo>, где Foo - это пользовательский класс. У меня также есть какой-то компаратор, который будет сравнивать поля класса Foo.

Теперь, где-то в моем коде я делаю:

std::sort( myvec.begin(), myvec.end(), comparator );

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

Теперь я хочу вставить элемент класса Foo в этот вектор. Если бы я мог, я хотел бы просто написать:

 mysortedvector.push_back( Foo() );

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

Вместо этого прямо сейчас я должен написать:

myvec.push_back( Foo() );
std::sort( myvec.begin(), myvec.end(), comparator );

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

Теперь, из-за характера моей программы, я не могу использовать std::map<> как у меня нет пар ключ/значение, просто простой вектор.

Если я использую stl::list, мне снова нужно вызывать sort после каждой вставки.

Ответы

Ответ 1

Да, std::set, std::multiset, std::map, и std::multimap все отсортированы используя std::less в качестве операции сравнения по умолчанию. Основная используемая структура данных обычно представляет собой сбалансированное двоичное дерево поиска, такое как красно-черное дерево. Поэтому, если вы добавите элемент в эти структуры данных и затем перейдете по содержащимся элементам, результат будет в отсортированном порядке. Сложность добавления N элементов в структуру данных будет O (N log N) или такая же, как сортировка вектора из N элементов с использованием любой общей сложности O (log N).

В вашем конкретном сценарии, поскольку у вас нет пар ключ/значение, std::set или std::multiset, вероятно, лучший выбор.

Ответ 2

Я хотел бы подробнее остановиться на ответе Джейсона. Я согласен с Джейсоном, что std::set или std::multiset - лучший выбор для вашего конкретного сценария. Я хотел бы привести пример, чтобы помочь вам еще больше сузить выбор.

Предположим, у вас есть следующий класс Foo:

class Foo {
public:
    Foo(int v1, int v2) : val1(v1), val2(v2) {};
    bool operator<(const Foo &foo) const { return val2 < foo.val2; }
    int val1;
    int val2;
};

Здесь Foo перегружает оператор <. Таким образом, вам не нужно указывать явную функцию сравнения. В результате вы можете просто использовать std::multiset вместо std::vector следующим образом. Вам просто нужно заменить push_back() на insert():

int main()
{
    std::multiset<Foo> ms;
    ms.insert(Foo(1, 6));
    ms.insert(Foo(2, 5));
    ms.insert(Foo(3, 4));
    ms.insert(Foo(1, 4));

    for (auto const &foo : ms)
        std::cout << foo.val1 << " " << foo.val2 << std::endl;

    return 0;
}

Выход:

3 4
2 4
1 5
1 6

Как видите, контейнер отсортирован по члену val2 класса Foo на основе оператора <. Однако, если вы используете std::set вместо std::multiset, вы получите другой вывод:

int main()
{
    std::set<Foo> s;
    s.insert(Foo(1, 6));
    s.insert(Foo(1, 5));
    s.insert(Foo(3, 4));
    s.insert(Foo(2, 4));

    for (auto const &foo : s)
        std::cout << foo.val1 << " " << foo.val2 << std::endl;

    return 0;
}

Выход:

3 4
1 5
1 6

Здесь второй объект Foo где val2 равен 4, отсутствует, потому что std::set допускает только уникальные записи. Если данные уникальны определяются на основе предоставленного < оператора. В этом примере оператор < сравнивает члены val2 друг с другом. Следовательно, два объекта Foo равны, если их члены val2 имеют одинаковое значение.

Таким образом, ваш выбор зависит от того, хотите ли вы хранить объекты Foo которые могут быть равными, в зависимости от оператора <.

Код на Ideone

Ответ 3

Я не думаю, что функциональность существует в STL, std::vector может сортировать только раздел, nth_element, stable_partition, partial_sort, stable_sort и сортировка.

Однако вы можете создать обертку для std::vector

#include <vector>

template <class T>
class VectorSortWrapper
{
public:
    std::vector<T> m_VectorSorted;

    void InsertSortedAscending(T item)
    {
        for(int i = 0; i < m_VectorSorted.size(); i++)
        {
            if( item.GetOrderValue() <= m_VectorSorted[i].GetOrderValue() )
            {
                m_VectorSorted.insert(m_VectorSorted.begin() + i, item);
                break;
            }       
        }
    }

    void InsertSortedDecending(T item)
    {
        for(int i = 0; i < m_VectorSorted.size(); i++)
        {
            if( item.GetOrderValue() >= m_VectorSorted[i].GetOrderValue() )
            {
                m_VectorSorted.insert(m_VectorSorted.begin() + i, item);
                break;
            }       
        }
    }

};