the_mandrill the_mandrill - 2 months ago 6
C++ Question

How to add use a pointer to member value as a template parameter by type (not value)

My situation:

I frequently need to have a vector of structures where one field can be thought of as a Key or ID, and rather than store it expensively in a map (memory usage is very important in this app) I want to store it in a flat vector but present a map-like interface for finding elements by key.

My first solution to this problem:

template <class T, class Key, class KeyFn>
class TKeyedVector : public std::vector<T>
{
public:

const_iterator find(const Key& key) const {return std::find_if(begin(), end(), [&](const T& entry) {return keyFn(entry)==key; }); }

KeyFn keyFn;
};

struct KeyedDataEntry
{
std::string key;
int value;

struct KeyExtractor {
const std::string& operator()(const KeyedDataEntry& e) const {return e.key; };
};
};

using KeyedDataArray = TKeyedVector<KeyedDataEntry, std::string, KeyedDataEntry::KeyExtractor>;


Now this all works, but I would like to be able to remove the need for the
KeyExtractor
type by using the pointer to the member variable embedded into the type:

template <class T, class Key, Key T::* keyFn>
class TKeyedVector : public std::vector<T>
{
public:
const_iterator find(const Key& key) const {return std::find_if(begin(), end(), [&](const T& entry) {return keyFn(entry)==key; }); }
};

using KeyedDataArray = TKeyedVector<KeyedDataEntry, std::string, &KeyedDataEntry::key>;


However I can't get this to work. I've been looking at the implementation of
std::mem_fn
for clues, but I can't work out how to do it. The error I get with is something like:

warning C4353: nonstandard extension used: constant 0 as function expression. Use '__noop' function intrinsic instead


Any clues?

EDIT: sample version at http://ideone.com/Qu6TEy

Answer

Here is the start of a working solution. You don't need a special extractor object.

Note that I have encapsulated the vector. In time, you'll regret not doing this.

#include <vector>
#include <string>

template <class T, class Key, const Key& (T::*Extractor)() const>
class TKeyedVector
{
    using storage = std::vector<T>;
    using const_iterator = typename storage::const_iterator;
public:

    decltype(auto) begin() const
    {
        return storage_.begin();
    }

    decltype(auto) end() const
    {
        return storage_.end();
    }

    const_iterator find(const Key& key) const
    {
        return std::find_if(begin(),
                            end(),
                            [&](const T& entry)
        {
            return entry.*Extractor() == key;
        });
    }

    storage storage_;
};

struct KeyedDataEntry
{
    std::string       key;
    int               value;

    const std::string& get_key() const { return key; }

};

int main()
{
    TKeyedVector<KeyedDataEntry, std::string, &KeyedDataEntry::get_key> mymap;

}

But there is a problem with this idea of yours.

In order for this structure to be a map, the keys must be immutable. This argues for only returning immutable objects. This then argues immediately for simply using an unordered_set or set.

If you're going to return references to mutable objects in the underlying vector, then you may as well simply use std::find_if with a predicate to find them.

Comments