Есть ли структура C ++, подобная карте, но вместо ключа к значениям я получаю дескриптор значения?

Question

Мне нужна структура вроде Map, но меня не интересует значение ключа, только значение, соответствующее ключу.

На карте мне нужно сделать что-то вроде этого:

map[1] = "value1"
map[2] = "value2"

Это дает мне ответственность не выбирать конфликтующие ключи. Я мог бы решить эту проблему, выполнив:

let handle = randomValue();
map[handle] = "value1"

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

Список кажется хорошим выбором в сначала, но это не так, поскольку, если я удалю один элемент, индексы всех остальных будут переупорядочены.

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

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

Answer 1

IIU C, вам нужен контейнер со следующими характеристиками:

• возможность добавить новый элемент и получить его числовой c дескриптор
• возможность удалить существующий элемент

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

Итак, чтобы удалить element, вы помечаете его как пустой и сохраняете его индекс в пустом списке, а чтобы добавить элемент, вы сначала пытаетесь получить следующий слот из пустого списка и push_back его в конец первичного вектора, если список пуст.

И добавление, и удаление происходят в постоянное время.

Answer 2

Одна возможность: ваша «карта» - это std::list, а ваш «дескриптор» - std::list::iterator, который вы можете преобразовать в указатель (с &*it), когда необходимо передать to Rust.

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

Answer 3

Наборы

Если вас действительно не волнует ключ, вы можете использовать std::set или std::unordered_set:

std::set<MyClass> set{MyClass(42), MyClass(32), MyClass(85)};
...
auto it = set.find(MyClass(32));

Maps

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

std::unordered_map<size_t, MyClass> map;
...
size_t counter=0;
map[counter++] = MyClass(42);
map[counter++] = MyClass(32);
...
auto it = map.find(1); // iterator to MyClass(32)

Примечание: несколько объектов могут иметь один и тот же ключ (коллизия), используя std::multimap и std::unordered_multimap, объекты с одинаковыми key не теряются, но могут быть получены с помощью итераторов. Это делает выбор ha sh менее критичным.

Хеши

C ++ предоставляет несколько функций «ha sh» для типичных типов, которые можно использовать для карт.

Ссылка на std::hash https://en.cppreference.com/w/cpp/utility/hash

Answer 4

Вы можете обернуть std::map в свой собственный класс, который отслеживает последний использованный идентификатор:

#include <map>
#include <string>
#include <iostream>

template < typename T >
class AutoMap
{
public:
  typedef typename std::map<int, T>::iterator iterator;
  typedef typename std::map<int, T>::const_iterator const_iterator;

  int insert(const T& value)
  {
     int key = next++;
     map[key] = value;
     return key;
  }

  const T& operator [] (int key) const
  {
     auto it = map.find(key);
     if (it == map.end()) throw std::invalid_argument("invalid key");
     return it->second;
  }

  T& operator [] (int key)
  {
     auto it = map.find(key);
     if (it == map.end()) throw std::invalid_argument("invalid key");
     return it->second;
  }

  void erase(int key)
  {
      map.erase(key);
  }

  iterator find(int key)
  {
      return map.find(key);
  }

  const_iterator find(int key) const
  {
      return map.find(key);
  }

  iterator begin()
  {
      return map.begin();
  }

  iterator end()
  {
      return map.end();
  }

  const_iterator begin() const
  {
      return map.begin();
  }

  const_iterator end() const
  {
      return map.end();
  }
private:
  std::map<int, T> map;
  int next = 0;
};

int main()
{
    AutoMap<std::string> m;
    std::cout << m.insert("test") << "\n";
    std::cout << m.insert("test2") << "\n";
    std::cout << m[0] << "\n";
    std::cout << m[1] << "\n";
    m.erase(0);
    std::cout << (m.find(0) == m.end()) << "\n";
}