Структура данных, которая отображает уникальный идентификатор на объект - PullRequest
Новая
       11

Структура данных, которая отображает уникальный идентификатор на объект

2 голосов
/ 10 февраля 2010

Я ищу структуру данных C ++, которая позволила бы мне связать объекты с уникальным числовым значением (ключом), и который будет повторно использовать эти ключи после удаления соответствующего объекта из контейнера. Так что это в основном что-то вроде гибридной структуры карты / очереди. Моя текущая реализация - 

std::map<size_t, TObject>

и я вставляю такие объекты: 

 size_t key = (m_Container.end()--)->first + 1;
 m_Container[key] = some_object;

, который отлично подходит для моих целей (я никогда не выделю больше, чем объекты size_t); все же я все еще задаюсь вопросом, есть ли более специализированный контейнер, предпочтительно уже в stl или boost, или что есть способ использовать другой контейнер для достижения этой цели.

(Конечно, я мог бы вместо того, чтобы брать самый высокий ключ на моей карте и добавлять один, каждый раз проходить по карте и искать первый доступный ключ, но это уменьшило бы сложность с O (1) до O (n) Также было бы неплохо, если бы API был простым 

size_t new_key = m_Container.insert(object);

).

Есть идеи?

Ответы [ 5 ]

1 голос
/ 10 февраля 2010

Я не уверен, что именно вы хотите от своего удостоверения личности. Как оказалось, у каждого объекта уже есть уникальный идентификатор: его адрес! Нет двух разных объектов с одинаковым адресом, и адрес объекта не меняется в течение срока его службы.

std::set<T> обычно хранит свои значения T как члены более крупных узлов, а не как независимые объекты. Тем не менее подобъекты T никогда не перемещаются, и, следовательно, их адреса также являются стабильными уникальными идентификаторами.

1 голос
/ 10 февраля 2010

Создать std::set<key_type> removed_keys; из удаленных ключей. Если removed_keys не пусто, используйте ключ из removed_keys, иначе создайте новый ключ.

1 голос
/ 10 февраля 2010

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

size_t assign_id()
{
    static size_t next_id;
    return next_id++;
}

А если вы хотите хороший API: 

template<class Container>
size_t insert(Container & container, TObject const & obj)
{
     container.insert(obj);
     return assign_id();
}

std::set<TObject> m_Container;
size_t new_key = insert(m_Container, object);
0 голосов
/ 10 февраля 2010

Есть ли причина, по которой вам нужно std::map, чтобы не удалять ключ , значение пара?

Это звучит как попытка преждевременной оптимизации.

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

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

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

0 голосов
/ 10 февраля 2010

Почему бы просто не использовать вектор? 

std::vector<TObject> m_Container;

size_t key = m_Container.size();
m_Container.push_back(some_object);

Конечно, это может быть совершенно бесполезно, если у вас есть другие характеристики использования. Но так как вы описываете только вставку и необходимость ключа (то есть извлечения), трудно дать какой-либо другой четкий ответ. Но из этих двух требований std :: vector <> должно работать просто отлично.

Если у вас есть некоторые другие характеристики использования, такие как: (элементы могут быть удалены), (мы вставляем элементы в большие блоки), (мы вставляем элементы нечасто) и т. Д., Это будут интересные факты, которые могут изменить рекомендации, которые дают люди.

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

Глядя на ваш код выше: 

size_t key = (m_Container.end()--)->first + 1;

Это не делает то, что вы думаете, что делает.
Это тоже эквивалентно: 

size_t key = m_Container.end()->first + 1;
m_Container.end()--;

Оператор декремента post изменяет lvalue. Но результатом выражения является исходное значение. Таким образом, вы применяете оператор -> к значению, возвращаемому функцией end (). Это (вероятно) неопределенное поведение.

См. Стандарт:

Раздел: 5.2.6 Увеличение и уменьшение
Значением выражения postfix ++ является значение его операнда. 

m_Container.end()--  // This sub-expresiion returns m_Container.end()

Альтернатива: 

#include <vector>

template<typename T>
class X
{
    public:
        T const& operator[](std::size_t index) const    {return const_cast<X&>(*this)[index];}
        T&       operator[](std::size_t index)          {return data[index];}
        void        remove(std::size_t index)           {unused.push_back(index);}

        std::size_t insert(T const& value);
    private:
        std::vector<T>                  data;
        std::vector<std::size_t>        unused;
};

template<typename T>
std::size_t X<T>::insert(T const& value)
{
    if (unused.empty())
    {
        data.push_back(value);
        return data.size() - 1;
    }
    std::size_t result  = unused.back();
    unused.pop_back();
    data[result]    = value;
    return result;
}
...