# Partitioned Multikey Map

Below is the code for what I've called a partitioned_multitype_map. This has two major facets:

• Allowing a lookup based on keys of multiple lengths and of multiple types. For example:

typedef partitioned_multitype_map<int32_t, std::string, int64_t, double> map_t;

would allow keys of any length 1 to a (specified) maximum, where each member in the key is one of the template types.

• The second facet is that it partitions keys based on length, giving easy access to all key/value pairs of a given key length.

I'm looking for any comments or criticisms, but particularly, there is quite a bit of code duplication lying around. Simply because of the complexity of the types, I'm having some trouble trying to reduce it, so anything that's directed to that effect would be great.

/*! \file partitioned_multitype_map.hpp
*  \brief Implementation of a compile time checked multi-key multi-value store.
*
*  A partitioned_multitype_map defines a multi-key multi-value store. The types
*  that the keys can store  are specified at compile time via variadic template
*  parameters Args...
*  There are a few concepts that must be adhered to:
*    1) Each type that is to be part of a key must be Hashable.
*    2) Each type that is to be part of a key must be equality comparable
*       (using ==).
*    3) At least one of the types must be DefaultConstructable.
*    4) Each type must be either CopyConstructible or MoveConstructable.
*
*  Currently, the values must correspond to the types that are stored as keys;
*  that is keys and values are composed of the same set of types.
*
*  The map is partitioned on key length to make it easy to get all keys (and
*  (associated values) of a given length.
*
*  The current API is -slightly- awkward as we have to store the inserted
*  key iterator to be able to insert a value into that spot. Variadic templates
*  makes creating a nice API for this more difficult.
*
*  Finally, note that this container isn't parameterized on an Allocator,
*  and hence will use std::allocator for all allocations.
*
*/

#ifndef PARTITIONED_MULTI_TYPE_MAP_HPP_
#define PARTITIONED_MULTI_TYPE_MAP_HPP_

#include <algorithm>
#include <cstdint>
#include <functional>
#include <numeric>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

#include <boost/functional/hash.hpp>
#include <boost/variant.hpp>
#include <boost/optional.hpp>

namespace multi_container
{

template <typename... Args>
class partitioned_multitype_map
{
public:

using variant_type = boost::variant<Args...>;
using key_type     = std::vector<variant_type>;
using mapped_type  = std::vector<variant_type>;

private:

// Internal struct that is used to hash keys that the
// underlying map will hold.
struct hasher_
{
std::size_t operator()(const key_type& k) const
{
return boost::hash_range(k.begin(), k.end());
}
};

// Internal struct to be used for equality comparison of keys.
// Keys compare equal if they are the same size and each of the
// elements within the keys compares equal (order is significant).
struct equality_compare_
{
bool operator()(const key_type& k1, const key_type& k2) const
{
if(k1.size() != k2.size())
return false;
return std::equal(std::begin(k1), std::end(k1), std::begin(k2));

}
};

using hashmap_type   = std::unordered_map<key_type, mapped_type,
hasher_, equality_compare_>;
using partition_type = std::pair<std::uint8_t, hashmap_type>;
using storage_type   = std::vector<partition_type>;

storage_type container;

public:

// The maximum number of keys we're allowing. There isn't really a technical limitation
// to this limit, but hashing starts to become quite expensive. Could be removed
// at a later date with almost no impact on the rest of the code however, as it
// is only used in static_assert currently.
constexpr static std::uint8_t max_key_size =
std::numeric_limits<std::uint8_t>::max();

using size_type            = typename hashmap_type::size_type;
using difference_type      = typename hashmap_type::difference_type;
using hasher               = hasher_;
using key_equal            = equality_compare_;
using inner_iterator       = typename hashmap_type::iterator;
using const_inner_iterator = typename hashmap_type::const_iterator;

partitioned_multitype_map() = default;
~partitioned_multitype_map() = default;

/*! \brief Emplaces the key defined in args into the container, default constructing
*         the value that it maps to.
*
*  \param args : The key (comprising of 1 or more elements) to be inserted.
*  \return A pair where the first element is the iterator where the key was
*          inserted, and a boolean specifying if the key was inserted or not.
*          If the key already exists, it returns an iterator to the key and false.
*/
template <typename... Keys>
auto emplace_key(Keys&&... args) -> decltype(container[0].second.emplace(args...))
{
static_assert(sizeof...(args) < max_key_size, "Too many keys specified");

key_type key {std::forward<Keys>(args)...};
const std::uint8_t k_size = static_cast<std::uint8_t>(key.size());
auto it = std::find_if(container.begin(), container.end(),
[=](const partition_type& p) { return p.first == k_size; });

if(it == container.end()) {
hashmap_type inner;
inner.emplace(std::move(key), mapped_type());
container.emplace_back(
std::make_pair(k_size, std::move(inner)));
auto where = container.back().second.begin();
return std::make_pair(where, true);
} else {
hashmap_type& inner = it->second;
auto found = inner.find(key);
if(found != inner.end()) {
return std::make_pair(found, false);
}
return inner.emplace(std::move(key), mapped_type());
}
}

/*! \brief Sets the key pointed at by where to the values contained in args.
*         This assumes that the iterator passed in is a valid iterator (for
*         example, one returned by emplace_key). Behaviour is undefined if
*         the iterator does not point into the container.
*
*  \param where: An iterator pointing at the key to set the value of.
*  \param args: The value(s) (comprising 1 or more) to be mapped to the key
*               pointed to by where.
*/
template <typename... Values>
void insert_value(inner_iterator where, Values&&... args)
{
mapped_type v {std::forward<Values>(args)...};
where->second = std::move(v);
}

/*! \brief Checks the container for the existence of a given key.
*
*  \param args: The key to search for.
*  \returns true if the given key exists in the container, false otherwise.
*/
template <typename... Keys>
bool contains_key(Keys&&... args)
{
static_assert(sizeof...(args) < max_key_size, "Too many keys specified");

key_type key {std::forward<Keys>(args)...};
const std::uint8_t k_size = key.size();

auto it = std::find_if(container.begin(), container.end(),
[=](const partition_type& p) { return p.first == k_size; });
if(it == container.end()) {
return false;
}
hashmap_type& inner = it->second;
return inner.find(key) != inner.end();
}

/*! \brief Returns a copy of the value corresponding to the given key.
*
*  \param args: The key to search for.
*  \returns A optional copy of the value corresponding to the given key.
*           This is the value if found, or a default-constructed value if not.
*  Note that this returns a boost::optional<> instead of a pair of iterators.
*  This is primarily because the keys are thought of as a "single" entity
*  instead of a container in their own right.
*/
template <typename... Keys>
boost::optional<mapped_type> get_value(Keys&&... args) const
{
static_assert(sizeof...(args) < max_key_size, "Too many keys specified");

key_type key {std::forward<Keys>(args)...};
const std::uint8_t k_size = key.size();

auto it = std::find_if(container.begin(), container.end(),
[=](const partition_type& p) { return p.first == k_size; });
if(it == container.end()) {
return boost::optional<mapped_type>();
}
hashmap_type& inner = it->second;
auto found = inner.find(key);
if(found == inner.end()) {
return boost::optional<mapped_type>();
}
return boost::optional<mapped_type>(found->second);
}

/*! \brief Returns a reference to the value corresponding to the given key.
*
*  \param args: The key to search for.
*  \returns An optional reference to the value corresponding to the given key.
*           This is the value if found, or a default-constructed value if not.
*/
template <typename... Keys>
boost::optional<mapped_type&> get_value(Keys&&... args)
{
static_assert(sizeof...(args) < max_key_size, "Too many keys specified");

key_type key {std::forward<Keys>(args)...};
const std::uint8_t k_size = key.size();

auto it = std::find_if(container.begin(), container.end(),
[=](const partition_type& p) { return p.first == k_size; });
if(it == container.end()) {
return boost::optional<mapped_type&>();
}
hashmap_type& inner = it->second;
auto found = inner.find(key);
if(found == inner.end()) {
return boost::optional<mapped_type&>();
}
return boost::optional<mapped_type&>(found->second);
}

/*! \brief Returns a const reference to the value corresponding to the given key.
*
*  \param args: The key to search for.
*  \returns An optional reference to the value corresponding to the given key.
*           This is the value if found, or a default-constructed value if not.
*/
template <typename... Keys>
const boost::optional<mapped_type&> get_value(Keys&&... args) const
{
static_assert(sizeof...(args) < max_key_size, "Too many keys specified");

key_type key {std::forward<Keys>(args)...};
const std::uint8_t k_size = key.size();

auto it = std::find_if(container.begin(), container.end(),
[=](const partition_type& p) { return p.first == k_size; });
if(it == container.end()) {
return boost::optional<mapped_type&>();
}
hashmap_type& inner = it->second;
auto found = inner.find(key);
if(found == inner.end()) {
return boost::optional<mapped_type&>();
}
return boost::optional<mapped_type&>(found->second);
}

bool empty() const
{
return container.empty();
}

size_type size() const
{
size_type sum = 0;
for(const auto& p : container) {
sum += p.second.size();
}
return sum;
}

void clear()
{
container.clear();
}

/*! \brief Returns the number of keys in the container that have a given length.
*
*  \param length The length of the keys to search for.
*  \return The number of keys of the specified length, or 0 if no keys of
*          the given length exist.
*/
std::size_t num_keys(std::uint8_t length)
{
auto it = std::find_if(container.begin(), container.end(),
[=](const partition_type& p) { return p.first == length; });
if(it != container.end()) {
return it->second.size();
}
return 0;
}

/*! \brief Returns a pair of iterators to the beginning/end of the map
*         containing keys of a given length.
*
*  \param length The length of the keys to search for.
*  \return A pair of const iterators pointing to the beginning and end
*          of the map.
*/
std::pair<const_inner_iterator, const_inner_iterator>
all_values_length(std::uint8_t length) const
{
auto it = std::find_if(container.begin(), container.end(),
[=](const partition_type& p) { return p.first == length; });
if(it != container.end()) {
return std::make_pair(it->second.begin(), it->second.end());
}
return std::make_pair(const_inner_iterator(), const_inner_iterator());
}

}; // end class partitioned_multitype_map

} // end namespace multi_container


• You already know what type everything is supposed to be, in which case you should have several different collections, one for each type, and retrieve objects from the applicable collection. (You could even put them all in the same class, where you have http_response.get_uri("location") and http_response.get_int("status-code") or some such thing, if you really have to.)
• @Yuushi having a type_A OR type_B is the same thing as having a type_A_or_B. Seriously, just don't do it. (Hint: if you have to use a type cast (except for primitives) to access the desired properties of the retrieved objects, you are doing it wrong. Type casts are inherently evil.) – AJMansfield Feb 5 '14 at 0:44
• You don't have to use type casts to access anything. boost::variant gives you a safe way to use the underlying type using a static_vistor (which in itself can be generic), or to find out what it is using which(). – Yuushi Feb 5 '14 at 0:58
• @Yuushi then you should just be using a map containing these boost::variants. Put the complexity where it belongs, in the type container. – AJMansfield Feb 5 '14 at 21:47