Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Reducing template complexity in C++

Recently, I've been using one of the lesser-used STL features- custom allocators, and I need some serious help in reducing my semantic overhead. Take for example, the definition of an unordered map, which maps filenames to an unordered map of a pair of ints and a shared_ptr to a Token, but using a custom allocator.

typedef std::pair<int, int> token_key_type;
typedef std::unordered_map<
    token_key_type, 
    std::shared_ptr<Token>,
    std::hash<token_key_type>,
    std::equal_to<token_key_type>,
    Allocator<
        std::pair<
            const token_key_type, 
            std::shared_ptr<
                Token
            >
        >
    >
> filename_map_value_type;
std::unordered_map<
    string, 
    filename_map_value_type,
    std::hash<string>,
    std::equal_to<string>,
    Allocator<
        std::pair<
            const string, 
            filename_map_value_type
        >
    >
> tokens;

That's 404 characters of definitions. And then to construct it, I have to pass in the default for every template argument, except the Allocator, which can't be default constructed, AND the bucket count, for which no definition exists, resulting in another 168 characters just to construct the damn thing. Plus, of course, the same again every time I want to insert, because the value type of the first map has to be constructed like that too.

Is there any way that all of this can be avoided without having to write my own unordered_map? It's seriously starting to slow down my productivity.

Edit: Sorry! I meant, in general, for STL containers, not just unordered_map specifically, it's just the worst case. I've also got this problem with regular map, unordered_set, etc, and can't go writing a function to do all of this for all of the possible STL containers I might need invidually.

like image 382
Puppy Avatar asked Dec 04 '10 14:12

Puppy


People also ask

How can we reduce the complexity of N 2?

With regard to reducing the time complexity of O(n²) squared, we can work to reduce to O(n) linear or O(log(n)) in most cases, which would make our algorithm to perform faster. There are some category of problems where it's not possible to reduce in optimal ways, but in our example it's perfectly possible to reduce.

What is the time complexity of set :: insert?

Its time complexity is O(logN) where N is the size of the set. insert(): insert a new element. Its time complexity is O(logN) where N is the size of the set. size(): Returns the size of the set or the number of elements in the set.

Are templates compile time?

A template is visited twice by the compiler. On first pass it's simply checked for correct syntax. It's only actually compiled when it is used (instantiated) in code.


2 Answers

icecrime's solution can also be done with only slightly more ugliness on older compilers via the code below. You also may be able to add factory functions to simplify construction.

template<typename K, typename V> struct unordered_map_type
{
    typedef std::unordered_map<
        K, 
        V,
        std::hash<K>,
        std::equal_to<K>,
        Allocator<
            std::pair<const K, V>
        >
    > type;
};

typedef std::pair<int, int> token_key_type;
typedef unordered_map_type<token_key_type, std::shared_ptr<Token> >::type filename_map_value_type;
like image 185
Dark Falcon Avatar answered Nov 12 '22 02:11

Dark Falcon


Unfortunately, I can't provide a complete and compilable code sample because I don't have a C++0x compiler here. However, I believe C++0x template aliases could be helpful here :

template<class Key, class Value>
using custom_unordered_map = std::unordered_map
    <
        Key,
        Value,
        std::hash<Key>,
        std::equal_to<Value>,
        Allocator<std::pair<const Key, Value>>
    >;

typedef custom_unordered_map<token_key_type, std::shared_ptr<Token>> filename_map_value_type;
typedef custom_unordered_map<std::string, filename_map_value_type> your_typedef_name;

Once again, sorry if this does not compile.

Also note that this was already possible in C++03 using an additional type 'indirection' :

template<class Key, class Value>
struct custom_unordered_map
{
    typedef std::unordered_map
    <
        Key,
        Value,
        std::hash<Key>,
        std::equal_to<Value>,
        Allocator<std::pair<const Key, Value> >
    > type;
};

typedef custom_unordered_map<token_key_type, std::shared_ptr<Token> >::type filename_map_value_type;
typedef custom_unordered_map<std::string, filename_map_value_type>::type your_typedef_name;
like image 6
icecrime Avatar answered Nov 12 '22 02:11

icecrime