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

Question

Как видно из заголовка, я ищу связанный массив (например, карту) с линейным потреблением памяти (например, std :: vector), где ключи автоматически c генерируются для новых записей. N <128. </p>

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

Код псевдонима:

/// Registers a callback and returns an associated id to it.
int register_callback(std::function callback);

/// Returns true if callback was unregistered for given id.
bool unregister_callback(int id);

Поскольку это должно использоваться во встроенных устройствах с ограничением памяти, я не буду использовать карту в качестве контейнера ( см. здесь: http://jsteemann.github.io/blog/2016/06/14/how-much-memory-does-an-stl-container-use/, карта использует в ~ 5 раз больше памяти, чем вектор).

У меня есть некоторые идеи, как реализовать это самостоятельно, но мне интересно, существует ли какое-либо имя / концепция для этого уже?

Это было бы моей идеей:

template<typename T>
class custom_map { // Totally unsure with naming
    // coll_ is sorted.
    std::vector<std::pair<uint8_t, T>> coll_;
public:
  uint8_t add(T) {
    // Find unused id by iterating over coll_,
    // If ((prev id + 1) != (next id)), free id found. 
    // Insert into coll new pair and sort.
  }

  bool remove(uint8_t id) {
    // Remove element in coll with associated id 
    // Binary search would be faster but only for bigger sizes, so linear search?
  }

  // Iterator concept begin/end... to iterate over collection.
};

Answer 1

Возможно, вы слишком усложняете проблему, вы можете просто использовать индекс в векторе в качестве ключа:

#include <vector>
#include <cstdint>
#include <functional>
#include <iostream>

template<typename T>
class custom_map {
  std::vector<T> coll_;
public:
  size_t add(const T& t) {
    for (auto it = coll_.begin(); it != coll_.end(); ++it)
    {
      if (!(*it))
      {
        *it = t;
        return it - coll_.begin();
      }
    }
    coll_.push_back(t);
    return coll_.size() - 1;
  }

  bool remove(size_t id) {
    if (id >= coll_.size() || !coll_[id]) {
      return false;
    }
    coll_[id] = {};
    // remove empty elements from the end of the list
    if (id == coll_.size()-1) {
      auto toRemove = std::count_if(coll_.rbegin(), coll_.rend(), [](const T& t) { return !t; });
      coll_.resize(coll_.size() - toRemove);
    }
    return true;
  }
};

int main()
{
  custom_map<std::function<void()>> map;
  auto i = map.add([](){std::cout << "1\n"; });
  map.remove(i);
}

Это будет работать только с типами, которые по умолчанию инициализированы значением, которое можно преобразовать в false (например, std::function), для других типов вы можете просто обернуть тип в std::optional, например (карта на самом деле будет работать и с int, но 0, будучи пустым значением, может быть не тем, что вы хотите):

int main()
{
  custom_map<std::optional<int>> map;
  auto i = map.add(10);
  map.remove(i);
}

Answer 2

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

template<typename T>
class custom_map { // Totally unsure with naming

std::vector<T*> coll_;
public:
uint8_t add(T*obj) {
    // Find unused id by iterating over coll_,
    for (int i = 0; i < coll_.size(); ++i) {
        if (coll_[i] == nullptr) {
            coll_[i] = obj;
            return i;
        }
    }
    coll_.push_back(obj);
    return coll_.size() - 1;
}

bool remove(uint8_t id) {
    coll_[id] = nullptr;
}

 // Iterator concept begin/end... to iterate over collection.
};