Пользовательские распределители как альтернатива вектору умных указателей? - PullRequest
14 голосов
/ 27 мая 2019

Этот вопрос касается владения указателями, их использования, умных указателей, векторов и распределителей.

Я немного растерялся, думая об архитектуре кода. Кроме того, если на этот вопрос уже есть где-то ответ, 1. извините, но я пока не нашел удовлетворительного ответа, и 2. пожалуйста, укажите мне на него.

Моя проблема заключается в следующем:

У меня есть несколько «вещей», хранящихся в векторе, и несколько «потребителей» этих «вещей». Итак, моя первая попытка была такой:

std::vector<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
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing = get_thing_for_consumer();
    }

    thing* m_thing;
};

В моем приложении это было бы безопасно, потому что "вещи" переживают "потребителей" в любом случае. Однако во время выполнения может быть добавлено больше «вещей», и это может стать проблемой, потому что, если std::vector<thing> i_am_the_owner_of_things; будет перераспределен, все указатели thing* m_thing станут недействительными.

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

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].get(); // 5 is just an example
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing = get_thing_for_consumer();
    }

    thing* m_thing;
};

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

Пример:
первоначально:
v = ☐☐☐☐☐☐☐☐☐☐
больше элементов:
v = ☐☐☐☐☐☐☐☐☐☐ ? ☐☐☐☐☐☐☐☐☐☐
и снова:
v = ☐☐☐☐☐☐☐☐☐☐ ? ☐☐☐☐☐☐☐☐☐☐ ? ☐☐☐☐☐☐☐☐☐☐

Используя такой распределитель, мне даже не пришлось бы использовать std::unique_ptr «вещей», потому что во время перераспределения std::vector адреса памяти уже существующих элементов не изменились бы.

В качестве альтернативы я могу думать только о том, чтобы ссылаться на «вещь» в «потребителе» через std::shared_ptr<thing> m_thing, в отличие от текущего thing* m_thing, но это кажется мне наихудшим подходом, потому что «вещь» должна Я не являюсь владельцем "потребителя", и с помощью общих указателей я бы создал общее владение.

Итак, подход распределителя хорош? И если так, как это можно сделать? Должен ли я сам применять распределитель или он существует?

Ответы [ 4 ]

12 голосов
/ 27 мая 2019

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

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

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

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

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

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

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- указатель бита) - индекс служит своего рода кешем. Когда вы выбираете, вы сначала пробуете индекс, если элемент в индексе имеет ожидаемый идентификатор, который вы сделали. В противном случае вы получаете «промах кэша» и выполняете линейное сканирование магазина, чтобы найти элемент на основе идентификатора, а затем сохраняете последнее известное значение индекса в вашей ссылке.

0 голосов
/ 27 мая 2019

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

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

Кроме того, возвращение необработанного указателя в вашем текущем коде уже совершенно неоднозначно относительно владения. В общем, я бы сказал, что хорошей практикой является избегать необработанных указателей, если вы можете (например, вам не нужно звонить 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
}
0 голосов
/ 27 мая 2019

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

Плюсы:

  • изменение будет сделано на отдельном уровне абстракции
  • изменения старого кода будут минимальными (просто замените 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;
}

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

...