LINUX.ORG.RU

Инстанцирование класса шаблоном с std::map с указателем на этот класс

 ,


0

3

Здравствуйте. Возникла проблема при написании одной из имплементаций Ахо-Корасик.

Вот ссылка сразу на код(пока что чисто полурабочая заготовка):http://pastebin.com/yc0LUDA0

Проблема вот в чём: обратите внимание на BorNode. У него внутри есть unordered_map<char, BorNode*>. Нужно это дело кастомизировать извне с помощью шаблонов. Что значит кастомизировать: мы можем менять тип контейнера - std::map/std::unordered_map, менять дефолтные std::hash, std::less у них и так далее, само собой, char тоже должны уметь менять на произвольный T.

С этим у меня возникла сложность, так как я не смог написать такой универсальный шаблон и проинстанцировать его.

Что я делал раньше: до того, как у меня были BorNode, у меня были просто size_t индексы нод в std::vector. И выглядело всё так:

template<typename T, typename Map, typename ResultCont = std::vector<std::vector<T>>>
class Base_Aho_Corasik{...}

template<typename T, typename Compare = std::less<T>, typename Alloc = std::allocator<std::pair<const T, size_t>>,
         typename ResultCont = std::vector<std::vector<T>>>
using Aho_Corasik = Base_Aho_Corasik<T, std::map<T, size_t, Compare, Alloc>, ResultCont>;

template<typename T, typename Hash = std::hash<T>, typename Pred = std::equal_to<T>,
         typename Alloc = std::allocator<std::pair<const T, size_t>>,
         typename ResultCont = std::vector<std::vector<T>>>
using Aho_Corasik_Hash = Base_Aho_Corasik<T, std::unordered_map<T, size_t, Hash, Pred, Alloc>, ResultCont>;

А как похожую вещь сделать с BorNode* вместо size_t я без понятия. У кого какие идеи? В выборе стандарта ограничений нет, можно использовать Boost.

Ответ на: комментарий от anonymous

не совсем. У вас внутри BorNode по харду записан std::unordered_map, я же хочу через шаблоны регулировать, что там будет использоваться std::map || std::unordered_map || чего-там-ещё-юезр-захочет

zamazan4ik ★★ ()
Ответ на: комментарий от anonymous

только там в Bor надо везде вместо char value_type.

anonymous ()
Ответ на: комментарий от anonymous

я понимаю, но всё равно это не то, что надо. Вообще, то, что я хочу сделать, осуществимо?

zamazan4ik ★★ ()
Последнее исправление: zamazan4ik (всего исправлений: 1)
Ответ на: комментарий от zamazan4ik

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

#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>


template <typename T,
          template <typename, typename> class Map
>
struct node
{
    using map_type = Map<T, node *>;
    map_type map_;
};

template <typename K, typename V>
using unodredr_map = std::unordered_map<K, V>;

template <typename K, typename V>
using black_red_map = std::map<K, V>;

template <typename T,
          template <typename, typename> class Map
>
struct acho_corasic {
    using value_type = T;
    using node_type  = node<T, Map>;
    using map_type   = typename node_type::map_type;
};

int main( )
{
    acho_corasic<int, black_red_map> int_node;
    acho_corasic<char, unodredr_map> char_node;
}

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

Это надо было?

anonymous ()
Ответ на: комментарий от anonymous

unodredr_map

лол. пардон, писал на коленке.

anonymous ()
Ответ на: комментарий от anonymous

Ещё ближе, но нет. Также должно выполняться условие кастомизируемости самого Map - то есть мы должны уметь менять std::hash, std::equal_to, std::allocator для std::unordered_map. Для std::map мы должны уметь менять std::less и std::allocator.

Плюс к этому, последним параметром в AhoCorasik должен быть typename ResultCont = std::vector<std::vector<T>>, который также должен быть кастомизируемым.

Я пока набросал вот это:

template <class T, template <class ...> class Map = std::map, class... Rest>
struct BorNode
{
    Map<T, BorNode*, Rest...> links;
};

zamazan4ik ★★ ()
Ответ на: комментарий от anonymous

осталось к этому прикрутить получение ResultCont как последний переданный аргумент в variadic template. То есть мы не должны весь variadic скормить в map - мы должны отправить в map весь variadic template, кроме последнего параметра.

zamazan4ik ★★ ()

Вы бы вместо того, чтобы показывать потроха того, что у вас не получается, попробовали бы объяснить какой результат и для чего вы хотите получить. Может это все решается гораздо проще, скажем, через специальные классы-trait-ы. Т.е. что-то вроде:

template< typename T >
struct default_aho_corasic_map_traits {
  using type = T;
  using map_type = std::map< T >;
  using result_type = std::vector< std::vector< T > >;
};
template< typename T >
struct default_acho_corasic_hashmap_traits {
  using type = T;
  using map_type = std::unordered_map< T >;
  using result_type = std::vector< std::vector< T > >;
};
...
template< typename TRAITS >
class aho_carasic {
public :
  using type = typename TRAITS::type;
  using map_type = typename TRAITS::map_type;
  using result_type = typename TRAITS::result_type;
...
};

template< typename T >
using aho_carasic_map = aho_carasic< default_aho_carasic_map_traits< T > >;

Ну и пусть себе пользователь затем создает собственные traits-ы (или специализации для ваших traits-ов с нужными ему comparator-ами, allocator-ами и пр.

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

да, кста. с трейтами сильно проще получится.

anonymous ()
Ответ на: комментарий от zamazan4ik

Также должно выполняться условие кастомизируемости самого Map

Так определение типа using black_red_map = std::map<K, V>; и есть кастомизация. сделай другой using с компартором и алокатором.

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

anonymous ()
Ответ на: комментарий от eao197

Спасибо большое. Это ровно то, что требуется в данном случае.

zamazan4ik ★★ ()
Ответ на: комментарий от anonymous

Да, Вы правы. Прошу прощения за невнимательность. Проблема решена. Если кто-то знает ещё более красивые способы, то милости прошу.

zamazan4ik ★★ ()
Ответ на: комментарий от zamazan4ik

Можно принимать не шаблон, а тип, а аргументы пусть подставляет пользователь. Так, например, сделано в std::priority_queue.

vzzo ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.