Эффективная структура данных для хранения структурных переменных с возможностью сортировки

Question

У меня есть структура

struct dbdetails
{
    int id;
    string val;
};

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

Answer 1

Вам нужен собственный функтор для сравнения ваших попыток. Это должно сделать трюк:

#include <algorithm>
#include <vector>
// try is a keyword. renamed
struct sorthelper : public std::binary_function<try_, try_, bool>
{
    inline bool operator()(const try_& left, const try_& right)
    {   return left.id < right.id;  }
};

...
std::vector<try_> v;
// fill vector 
std::sort(v.begin(), v.end(), sorthelper());
...

Пожалуйста, не стесняйтесь спрашивать, есть ли у вас дополнительные вопросы. У вас есть книга Страуструпа?

Редактировать: Предложение Маттео:

struct try_
{
    int id;
    string val;
    bool operator<(const try_& other) const
        {return id < other.id;}

}; // no s here plz.

...
std::vector<try_> v;
// fill vector 
std::sort(v.begin(), v.end());
...

Answer 2

Вы можете использовать std::map. Они отсортированы по ключу, поэтому вы можете сделать:

std::map<int, std::string> myStuff;

Это карта с int в качестве ключа и std::string в качестве значения. Перебирая карту, вы обнаружите, что она автоматически сортируется по ключу.

Обратите внимание, что вам больше не понадобится ваш struct с этим решением. Если вам абсолютно необходимы данные в struct (возможно, для взаимодействия с некоторой внешней библиотекой), вы всегда можете скопировать данные из map в struct по мере необходимости.

Answer 3

Все заказанные контейнеры (std::set, std::map, std::multiset, std::multimap), ну, заказаны.Неупорядоченные контейнеры (std::list, std::vector, std::deque) можно заказать, предоставив функцию сравнения с использованием std::sort (vector, deque) или предоставив этот компаратор для метода-члена (list).

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

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

Answer 4

Это зависит от того, какие требования у вас есть к вашему контейнеру данных.Может оказаться полезным набор (в Stl Set - это отсортированный ассоциативный контейнер для хранения объектов типа Key).Или даже набор Hash, или отсортированный массив.

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

Answer 5

Вы можете иметь vector из struct и затем сортировать их как:

std::sort(vectStruct.begin(), vectStruct.end(), &vectStructSort);

bool vectStructSort(Try const& lhs, Try const& rhs) { // try is keyword.
    return lhs.id < rhs.id;
}

Answer 6

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