Пользовательские распределители как альтернатива вектору умных указателей?

Ответ 1

Если вы можете рассматривать thing как тип значения, сделайте это. Это упрощает вещи, вам не нужен умный указатель для обхода проблемы аннулирования указателя/ссылки. Последний может быть решен по-разному:

• Если новые thing экземпляры вставляются через push_front и push_back во время выполнения программы, используйте std::deque вместо std::vector. Тогда никакие указатели или ссылки на элементы в этом контейнере не будут признаны недействительными (хотя итераторы недействительны - спасибо @odyss-jii за указание на это). Если вы боитесь, что вы сильно полагаетесь на выигрыш в производительности от полностью непрерывного макета памяти std::vector: создайте тест и профиль.
• Если новые экземпляры thing вставляются в середину контейнера во время выполнения программы, попробуйте использовать std::list. Никакие указатели/итераторы/ссылки недействительны при вставке или удалении элементов контейнера. Итерация по std::list намного медленнее, чем std::vector, но убедитесь, что это актуальная проблема в вашем сценарии, прежде чем беспокоиться об этом.

Ответ 2

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

Сказав это, вот моя рекомендация:

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

Таким образом, ваш потребитель будет хранить идентификатор и извлекать указатель на данные из "хранилища" по запросу. Это также дает вам контроль над всеми "выборками", так что вы можете отслеживать их, применять меры безопасности и т.д.

void consumer::foo() {
    thing *t = m_thing_store.get(m_thing_id);
    if (t) {
        // do something with t
    }
}

Или более продвинутая альтернатива, чтобы помочь с синхронизацией в многопоточном сценарии:

void consumer::foo() {
    reference<thing> t = m_thing_store.get(m_thing_id);
    if (!t.empty()) {
        // do something with t
    }
}

Где reference будет каким-то потокобезопасным RAII "слабый указатель".

Есть несколько способов реализации этого. Вы можете использовать хеш-таблицу с открытой адресацией и использовать идентификатор в качестве ключа; это даст вам примерно O (1) время доступа, если вы правильно его уравновесите.

Другая альтернатива (O (1) в лучшем случае, O (N) в худшем случае) - использовать "опорную" структуру с 32-битным идентификатором и 32-битным индексом (такой же размер, как у 64-битного указателя) - индекс служит своего рода кешем. Когда вы выбираете, вы сначала пробуете индекс, если элемент в индексе имеет ожидаемый идентификатор, который вы сделали. В противном случае вы получаете "промах кэша" и выполняете линейное сканирование магазина, чтобы найти элемент на основе идентификатора, а затем сохраняете последнее известное значение индекса в вашей ссылке.

Ответ 3

[Общий указатель] кажется мне худшим подходом, потому что "вещь" не должна владеть "потребителем", и с помощью общих указателей я бы создал общее владение.

И что? Может быть, код немного менее самодокументируется, но он решит все ваши проблемы. (И, между прочим, вы путаете вещи, используя слово "потребитель", которое в традиционной парадигме производитель/потребитель получит право собственности.)

Кроме того, возвращение необработанного указателя в вашем текущем коде уже совершенно неоднозначно в отношении владения. В целом, я бы сказал, что это хорошая практика - избегать необработанных указателей, если вы можете (например, вам не нужно вызывать delete.) Я бы возвратил ссылку, если вы используете unique_ptr

std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing& get_thing_for_consumer() {
    // some thing-selection logic
    return *i_am_the_owner_of_things[5]; // 5 is just an example
}

Ответ 4

ИМО лучшим подходом будет создать новый контейнер, который будет вести себя безопасным способом.

Плюсы:

• изменение будет сделано на отдельном уровне абстракции
• изменения в старом коде будут минимальными (просто замените std::vector новым контейнером).
• это будет "чистый код" способ сделать это

Минусы:

• может показаться, что работы еще немного

Другой ответ предлагает использовать std::list который будет выполнять эту работу, но с большим количеством выделения и более медленным произвольным доступом. Так что IMO лучше составить собственный контейнер из пары std::vector s.

Так что это может начать выглядеть более или менее так (минимальный пример):

template<typename T>
class cluster_vector
{
public:
    static const constexpr cluster_size = 16;

    cluster_vector() {
       clusters.reserve(1024);
       add_cluster();
    }

    ...

    size_t size() const {
       if (clusters.empty()) return 0;
       return (clusters.size() - 1) * cluster_size + clusters.back().size();
    }

    T& operator[](size_t index) {
        thowIfIndexToBig(index);
        return clusters[index / cluster_size][index % cluster_size];
    }

    void push_back(T&& x) {
        if_last_is_full_add_cluster();
        clusters.back().push_back(std::forward<T>(x));
    }

private:
    void thowIfIndexToBig(size_t index) const {
        if (index >= size()) {
            throw std::out_of_range("cluster_vector out of range");
        }
    }

    void add_cluster() {
       clusters.push_back({});
       clusters.back().reserve(cluster_size);
    }

    void if_last_is_full_add_cluster() {
       if (clusters.back().size() == cluster_size) {
           add_cluster();
       }
    }

private:
    std::vector<std::vector<T>> clusters;
}

Таким образом, вы предоставите контейнер, который не будет перераспределять предметы. Он не измеряет то, что делает Т.