конструкторы std::unordered_set

Я смотрел на конструкторы unordered_set. Разве нельзя создать unordered_set с настраиваемым экземпляром распределителя БЕЗ установки количества хэш-сегментов? Я действительно не хотел бы возиться с деталями реализации, потому что мне нужен собственный распределитель, а тип не дает определений для значения по умолчанию. MSDN дает только три перегрузки для конструктора, ни одна из которых не очень полезна.

Редактировать: Святое дерьмо. Моя реализация STL std::hash не будет специализироваться на строках с пользовательским типом распределителя — она может выполнять только явные определения типов std::string и std::wstring. Я имею в виду, я могу понять, что не хочу пытаться хешировать случайные строки символов, но только потому, что у него есть собственный распределитель? Это вызывает у меня отвращение.

tokens(std::unordered_set<string>().bucket_count(), std::hash<string>(), std::equal_to<string>(), stl_wrapper::hash_set<string>::allocator_type(this))
template<typename Char, typename CharTraits, typename Allocator> class std::hash<std::basic_string<Char, CharTraits, Allocator>>
    : public std::unary_function<std::basic_string<Char, CharTraits, Allocator>, std::size_t> {
public:
    size_t operator()(const std::basic_string<Char, CharTraits, Allocator>& ref) const {
        return std::hash<std::basic_string<Char, CharTraits>>()(std::basic_string<Char, CharTraits>(ref.begin(), ref.end()));
    }
};

Решает проблемы, но избыточные конструкции и копирование? Фуууууу.


c++ unordered-set
person Puppy    schedule 01.12.2010    source источник
comment
Что касается вашего редактирования: да, боюсь. std::hash немного не хватает, в частности, я думаю, что стандарт должен предоставлять функцию для хеширования последовательности байтов, чтобы упростить специализацию для UDT (включая вашу строку с настраиваемым распределителем). Но поскольку ваша альтернативно выделенная строка не связана ни с одной из обязательных hash специализаций, вы ДОЛЖНЫ без помощи в поле зрения. Насколько я знаю, вам просто нужно выбрать свой собственный алгоритм хеширования, а затем либо написать специализацию, либо указать хеш для своего контейнера.   -  person Steve Jessop    schedule 01.12.2010
comment
@Стив: Не совсем. Конструкторы basic_string могут принимать любой итератор, так что на самом деле было не очень сложно расширить его, чтобы он не зависел от распределителя, но это требует избыточной копии, что делает меня RAEG.   -  person Puppy    schedule 01.12.2010
comment
@DeadMG: да, в зависимости от того, почему вы используете собственный распределитель. Если вы хотите, чтобы все выделения в вашей программе проходили через ваш распределитель, то это не просто избыточная копия, это полный провал.   -  person Steve Jessop    schedule 01.12.2010
comment
@DeadMG: на самом деле, возможно, я просто не сделал домашнее задание. Есть std::collate<charT>::hash, так что, возможно, вы можете сделать namespace std { template <> struct hash<basic_string<char,char_traits<char>,MyAlloc>> { typedef size_t result_type; typedef basic_string<char,char_traits<char>,MyAlloc> argument_type; result_type operator()(const argument_type &str) { return collate<char>::hash(str.begin(), str.end()); }};}. Это немного многословно, чтобы передать вызов...   -  person Steve Jessop    schedule 01.12.2010
comment
@Steve: Что заставляет тебя так говорить? Прямо сейчас все неуправляемые выделения из каждого объекта-владельца проходят там, но глобальная ловушка распределения не может знать объект-владелец.   -  person Puppy    schedule 01.12.2010
comment
@DeadMG: Я говорю, что это полный провал, потому что если вы действительно хотите, чтобы все выделение строк проходило через ваш распределитель, то избыточная копия в string вместо этого будет выделяться из std::allocator<char>.   -  person Steve Jessop    schedule 01.12.2010
comment
@Steve: Это совершенно верно, но это значение r, и память будет немедленно освобождена, поэтому, когда хеш-метод возвращается, общая используемая память не изменилась, и поэтому мне все равно. Будем надеяться, что оптимизатор моего любимого компилятора справится с этим.   -  person Puppy    schedule 01.12.2010

Ответы (2)


arrow_upward
2
arrow_downward

Это странно, но вы правы. Я полагаю, мысль заключалась в том, что поддерживать все возможные комбинации параметров со значениями по умолчанию — это излишество.

На мой взгляд, лучший способ справиться с этим — создать пустой unordered_set со всеми настройками по умолчанию, получить от него количество сегментов по умолчанию с помощью unordered_set::bucket_count, а затем использовать его в качестве входных данных при создании экземпляра контейнера, который вам действительно нужен.

unordered_set<int> temp;
size_t buckets = temp.bucket_count;
unordered_set<string> actual(buckets, Hash(), Pred(), 
    YourAllocator(param1 /*, etc */));
person Steve Townsend    schedule 01.12.2010
comment
Я не могу этого сделать, если мой пользовательский распределитель не может быть создан по умолчанию. - person Puppy; 01.12.2010
comment
@Steve: Поскольку YourAllocator() является ошибкой компиляции, поскольку конструктора по умолчанию нет. - person Puppy; 01.12.2010
comment
Верно, но дело в том, что вы передаете нужный распределитель во втором вызове, а для других параметров установлены значения по умолчанию. Извините за сумбурность, я что-то упускаю. Разве вы не можете просто добавить конструктор YourAllocator в качестве параметра 4? - person Steve Townsend; 01.12.2010
comment
@Steve: Извините, я неправильно выразился, что имел в виду. Вы не можете сконструировать исходную временную переменную по умолчанию, потому что она пытается сконструировать по умолчанию распределитель, чего не может сделать. - person Puppy; 01.12.2010
comment
@DeadMG - да, но цель первого вызова - только определить количество сегментов реализации по умолчанию. Затем контейнер выбрасывается. Распределитель по умолчанию там в порядке. - person Steve Townsend; 01.12.2010
comment
@Steve: Ты абсолютно прав. Я не рассматривал возможность создания unordered_set другого типа. Теперь мне просто нужно убедить мою реализацию хеширования в том, что она хэширует одинаково, независимо от того, как я решил выделить указанную строку. - person Puppy; 01.12.2010
comment
Надеюсь получится, удачи. В любом случае, все еще больно делать это, чтобы получить количество сегментов по умолчанию. - person Steve Townsend; 01.12.2010

arrow_upward
0
arrow_downward

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

Стив дал суть метода, если вы не хотите, то позвольте мне предложить вспомогательную функцию :)

template <typename T>
size_t number_buckets()
{
  std::unordered_set<T> useless;
  return useless.bucket_count();
}

И с этим, маленький (простой) помощник:

template <typename T, typename Hash, typename Pred, typename Allocator>
std::unordered_set<T,Hash,Pred,Allocator>
  make_unordered_set(Hash const& hash, Pred const& pred, Allocator const& alloc)
{
  static size_t const nbBuckets = number_buckets<T>();
  return std::unordered_set<T,Hash,Pred,Allocator>(nbBuckets, hash, pred, alloc);
}

Очень хорошо работает с auto:

auto set = make_unordered_set<std::string>(Hash(), Pred(), Allocator(1,2,3));

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

person Matthieu M.    schedule 01.12.2010
comment
Нет, нет смысла контролировать оба, так как один контролирует, сколько памяти выделено или нет, и детали реализации рассматриваемого алгоритма, а другой просто измеряет его. Эти двое вовсе не обязательно связаны между собой. - person Puppy; 01.12.2010