Использование std :: unordered_set из std :: unique_ptr [duplicate]

18

Предположим, что у меня есть набор unique_ptr:

std::unordered_set <std::unique_ptr <MyClass>> my_set;

Я не уверен, что это безопасный способ проверить, существует ли данный указатель в наборе. Обычный способ сделать это может состоять в вызове my_set.find () , но что я передаю в качестве параметра?

Все, что у меня снаружи, является необработанным указателем. Поэтому мне нужно создать еще один уникальный_ptr из указателя, передать его find() , а затем release() этого указателя, иначе объект будет разрушен (дважды). Конечно, этот процесс может быть выполнен в функции, поэтому вызывающий может передать необработанный указатель, и я делаю преобразования.

Безопасен ли этот метод? Есть ли лучший способ работать с набором unique_ptr?

    
задан cfa45ca55111016ee9269f0a52e771 25.07.2013 в 08:56
источник
  • Спасибо. Мне не нужно ничего перемещать или копировать, поэтому unique_ptr в порядке. Мне просто нужно, чтобы вызывающий я дал мне необработанный указатель, и мне нужно проверить, существует ли в наборе соответствующий unique_ptr. –  cfa45ca55111016ee9269f0a52e771 25.07.2013 в 09:11
  • unique_ptr явно не то, что вам нужно, поскольку у вас явно есть другие указатели на объект. –  James Kanze 25.07.2013 в 10:43
  • Владелец unique_ptr является единственным владельцем памяти, а все остальные просто удерживают ссылки. Я мог бы использовать shared :: ptr у владельца и weak_ptr везде, но каждый объект ссылается на один shared_ptr. Мне не нужен обмен, просто один владелец –  cfa45ca55111016ee9269f0a52e771 25.07.2013 в 10:45
  • @JamesKanze Я не понимаю, почему std :: unique_ptr должен быть единственным указателем на какой-либо объект. «Уникальный» не поддерживает уникальный адрес, а уникальную собственность. Std :: shared_ptr, который не владеет своим плательщиком, - это гораздо худшее правонарушение. –  Christian Rau 25.07.2013 в 10:47
  • Не дубликат. Связанный вопрос задает set, этот для unordered_set, и это большая разница. –  IllidanS4 03.03.2018 в 12:10

4 ответа

18

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

template<class T>
struct maybe_deleter{
  bool _delete;
  explicit maybe_deleter(bool doit = true) : _delete(doit){}

  void operator()(T* p) const{
    if(_delete) delete p;
  }
};

template<class T>
using set_unique_ptr = std::unique_ptr<T, maybe_deleter<T>>;

template<class T>
set_unique_ptr<T> make_find_ptr(T* raw){
    return set_unique_ptr<T>(raw, maybe_deleter<T>(false));
}

// ...

int* raw = new int(42);
std::unordered_set<set_unique_ptr<int>> myset;
myset.insert(set_unique_ptr<int>(raw));

auto it = myset.find(make_find_ptr(raw));

Пример в реальном времени.

    
ответ дан Xeo 25.07.2013 в 11:14
источник
  • +1 для элегантности –  sehe 25.07.2013 в 11:15
  • У меня возникнет соблазн рассмотреть неявный конструктор, чтобы вместо этого вы могли установить set_unique_ptr <T> (raw, false). Мысли? (Я знаю, что знаю. Неявные преобразования, зло. Но конкретно, какой-нибудь улов для этого конкретного случая использования?) –  sehe 25.07.2013 в 11:20
10

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

Ссылка :

  • N3465 Добавление поиска гетерогенных сравнений в ассоциативные контейнеры для TR2 (Rev 2) [Обращаться с N3573]
  • N2882 id.
  • N3573 Гетерогенные расширения для неупорядоченных контейнеров [Handle with N3465]

Особенно последнее похоже, что оно будет охватывать ваш прецедент.

В настоящее время IMO не очень симпатичный, но работающий альтернативный метод обхода (O (n)):

#include <iterator>
#include <iostream>
#include <algorithm>

#include <unordered_set>
#include <memory>

#include <cassert>

struct MyClass {};

template <typename T>
struct RawEqualTo
{
    RawEqualTo(T const* raw) : raw(raw) {}

    bool operator()(T const* p) const  
        { return raw == p; }
    bool operator()(std::unique_ptr<T> const& up) const  
        { return raw == up.get(); }

  private:
    T const* raw;
};


using namespace std;
int main()
{
    std::unordered_set <std::unique_ptr <MyClass>> my_set;

    my_set.insert(std::unique_ptr<MyClass>(new MyClass));
    my_set.insert(std::unique_ptr<MyClass>(new MyClass));

    auto raw = my_set.begin()->get();

    bool found = end(my_set) != std::find_if(begin(my_set), end(my_set), RawEqualTo<MyClass>(raw));
    assert(found);

    raw = new MyClass;

    found = end(my_set) != std::find_if(begin(my_set), end(my_set), RawEqualTo<MyClass>(raw));
    assert(!found);

    delete raw;
}

Предупреждение Конечно, это тоже очень неэффективно.

    
ответ дан sehe 25.07.2013 в 10:01
источник
  • +1 Для упоминания гетерогенных запросов (и, по крайней мере, предупреждение о том, что std :: find_if использует использование std :: unordered_set ad absurdum). –  Christian Rau 25.07.2013 в 10:27
  • Гетерогенные расширения решают проблему, они делают именно то, что мне нужно :-) Но решение, которое вы предлагаете здесь, действительно слишком неэффективно. Мне нужно O (1) среднее значение unordered_set :: find –  cfa45ca55111016ee9269f0a52e771 25.07.2013 в 10:33
  • @Nawaz Поскольку std :: shared_ptr будет абсолютно неуместным, если память просто не используется. –  Christian Rau 25.07.2013 в 10:40
  • @ChristianRau Но он, очевидно, является общим, так как есть четкие указатели на объекты вне контейнера. –  James Kanze 25.07.2013 в 10:44
  • @ fr33domlover find не следует бросать (если не выбрана функция хэша или функция сравнения). Но наличие двух уникальных_ptr для одного и того же объекта звучит как рецепт катастрофы и кошмар обслуживания, поскольку он нарушает инварианты unique_ptr. –  James Kanze 25.07.2013 в 10:48
Показать остальные комментарии
8

Вы можете использовать std::map<MyClass*, std::unique_ptr<MyClass>> вместо набора. Затем вы можете добавить такие элементы:

 std::unique_ptr<MyClass> instance(new MyClass);
 map.emplace(instance.get(), std::move(instance));
    
ответ дан petersohn 25.07.2013 в 09:04
источник
  • -1. Что не так с std :: set? В этом случае std :: map плохо. Ключ и ценность - это тот же самый объект! –  Nawaz 25.07.2013 в 09:07
  • @Nawaz unique_ptr хранит память, в то время как необработанный указатель используется для find () и всех других методов, которые выполняют поиск по ключу. –  cfa45ca55111016ee9269f0a52e771 25.07.2013 в 09:10
  • @Nawaz Ну, так как бы вы решили «нужно найти unique_ptr, когда у меня есть только проблема с исходным указателем»? Этот ответ решает его, вводя явное отображение. Обратите внимание, что std :: [unrodered_] set - это то, что сейчас получает OP, и спрашивает, как выполнить поиск. –  Angew 25.07.2013 в 09:14
  • @Nawaz std :: unordered_set :: find is O (1); std :: find_if - O (n). Это может изменить ситуацию очень быстро. –  James Kanze 25.07.2013 в 10:51
  • @petersohn Использование метода release () небезопасно, если вам когда-либо приходилось модифицировать код или поддерживать его каким-либо образом. Независимо от исключений. Вы лжете компилятору и всем, кто читает код. –  James Kanze 25.07.2013 в 10:53
Показать остальные комментарии
4

Если целью является постоянное время поиска, я не думаю, что есть решение. std::unordered_set<std::unique_ptr<MyClass>>::find требует std::unique_ptr<MyClass> в качестве аргумента. Вам придется либо изменить контейнер или изменить содержащийся тип.

Одна из возможных может заключаться в замене std::unique_ptr на std::shared_ptr , и измените остальную часть кода так, чтобы все MyClass помещаются в shared_ptr, как только они создаются, и управляются только с помощью общих указателей. Логически, это, вероятно, более согласовано: unique_ptr в значительной степени подразумевает (по его названию, а также его семантику), что там не являются другими указателями на объект. С другой стороны, вы можете не сможет использовать shared_ptr, если, например, MyClass имеет указатели на другие MyClass , которые могут построить цикл.

В противном случае, если вы можете принять доступ O (lg n), а не постоянный доступ (разница вообще не становится заметны до тех пор, пока таблицы не будут достаточно большими), вы можете использовать std::vector<MyClass> , используя std::lower_bound , чтобы сохранить его отсортирован. В отличие от std::unordered_set<>::find , std::lower_bound not требует, чтобы целевое значение имело тот же тип, что и value_type последовательности; все, что вам нужно сделать, это обеспечить что они сопоставимы, например, предоставляя объект Compare вдоль линий:

class MyClassPtrCompare
{
    std::less<MyClass const*> cmp;
public:
    bool operator()( std::unique_ptr<MyClass> const& lhs,
                     std::unique_ptr<MyClass> const& rhs ) const
    {
        return cmp( lhs.get(), rhs.get() );
    }
    bool operator()( MyClass const* lhs,
                     std::unique_ptr<MyClass> const& rhs ) const
    {
        return cmp( lhs, rhs.get() );
    }
    bool operator()( std::unique_ptr<MyClass> const& lhs,
                     MyClass const* rhs ) const
    {
        return cmp( lhs.get(), rhs );
    }
    bool operator()( MyClass const* lhs,
                     MyClass const* rhs ) const
    {
        return cmp( lhs, rhs );
    }
};

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

    
ответ дан James Kanze 25.07.2013 в 10:42
источник
  • +1 Похоже на хороший компромисс. Странно ни один из сторонников find_if вообще этого не понимал (но, ладно, сам не думал об этом). –  Christian Rau 25.07.2013 в 10:46
  • Хорошая идея. В настоящее время я не возражаю против O (lg n), но я планирую поддерживать большое количество объектов и множество запросов, поэтому я предпочитаю использовать средний метод O (1), если это возможно –  cfa45ca55111016ee9269f0a52e771 25.07.2013 в 10:47
  • @ fr33domlover Тем не менее вы можете быть удивлены, насколько хорошо этот отсортированный вектор будет вести себя на практике, я думаю. –  Christian Rau 25.07.2013 в 10:49
  • Хорошее альтернативное решение с использованием std :: vector. Он также использует * меньше памяти *, чем std :: set. Это напоминает мне эту статью: почему вы не должны использовать set (и то, что вы должны использовать вместо этого) –  Nawaz 25.07.2013 в 10:52
  • @ fr33domlover Из опыта: вы можете обнаружить, что O (lg n) отсортированного вектора превосходит O (1) неупорядоченного_set, из-за гораздо лучшей локальности. –  James Kanze 25.07.2013 в 10:55
Показать остальные комментарии