Переопределение QAbstractItemModel :: index и доступ к std :: map

Question

В моей программе я хочу использовать шаблон вида / модели с view = QListView и мою собственную модель, которую я вложил в класс QAbstractListModel. Мой класс данных выглядит как

class Avtomat
{
...
 map<QString, State *> states;
...
};

В моем классе моделей

class AvtomatModel : public QAbstractListModel
{
    ...
    Avtomat a;
    ...
};

Я пытаюсь перегрузить функцию QAbstractItemView :: index, чтобы я мог предоставить интерфейс для редактирования карты данных. Поскольку функция index принимает аргумент int, я решил эту проблему, предоставив следующее

State* Avtomat::pStateFromIndex(int index) const
{
    map<QString, State *>::const_iterator i;
    int count = 0;
    for (i = states.begin(); i != states.end() && count != index; ++i)
        ++count;
    return (*i).second;
}

так в моей индексной функции я делаю вот так

return createIndex(row, column, a.pStateFromIndex(row));

но это кажется довольно уродливым, потому что у меня есть O (n). Можете ли вы помочь мне разработать лучший способ доступа к моей карте, используя int index?

Answer 1

Это фундаментальная проблема моделирования данных. Каков основной способ получения ваших данных? По ключу или по индексу?

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

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

В документации есть хорошая сводка классов контейнеров Qt (вместе с контейнерами std). Раздел о алгоритмическая сложность может быть особенно интересен для вас.

Answer 2

Другой вариант - использовать вектор для хранения данных в парах ключ-значение.Вектор может быть доступен по индексу или по ключу.Недостатком этого является то, что вставка в вектор стоит дороже по сравнению с std :: map.

typedef std::pair<QString, State*> StateP;
typedef std::vector<StateP> States;
States states;

Затем поддерживайте вектор в отсортированном порядке на основе предиката, который сравнивает первый элемент.Вы можете искать элементы по индексу в O (1) или ввести O (log n).

struct StatePCompare {
    bool operator()(StateP const& lhs, StateP const& rhs) const {
        return (lhs.first < rhs.first);
    }
};

void Avtomat::insert(QString key, State* state) 
{
    States::iterator i = std::lower_bound(states.begin(), states.end(), StatePCompare());
    if ((i != states.end() && (i->first == key)) {
        // key already exists, set the element
        i->second = state;
    }
    else {
        states.insert(i, state);
    }
}

State* Avtomat::find(QString key) 
{
    States::iterator i = std::lower_bound(states.begin(), states.end(), StatePCompare());
    if ((i != states.end() && (i->first == key)) {
        return i->second;
    }
    return NULL;
}