I want to create a custom map that that actually uses a fixed set of keys, but should behave like a std::map. Basically I use an array internally and map the keys to indexes, allowing very efficient lookup. I am however struggling to implement iterators that behave like std::map iterators, because I do not have internal std::pairs that I can hand out references to.
Is it possible to implement this as a zero-overhead abstraction while retaining the std::map interface, in particular the iterators?
The best i could come up with as operator* is to return a rvalue std::pair<key_type, mapped_type*>, which basically allows for the same operations, but unfortunately with different usage patterns.
I have also tried std::pair<key_type, boost::referene_wrapper<mapped_type>>, but that still doesn't allow for(auto& elem : map) and often requires elem.second.get() for reasons I do not understand.
I am happy to use boost or lightweight header libraries, if there is anything that helps for the use case.
To illustrate the case, here is a minimal example with a map that contains all letters 'a'-'z'.
using letter = char;
static const letter letter_begin = 'a';
static const letter letter_end = 'z' + 1;
template <typename T>
class letter_map
{
private:
using self = letter_map<T>;
template <typename IT, typename M>
class iterator_base : public std::iterator<std::input_iterator_tag, T>
{
public:
iterator_base(letter index, M& map) : index_(index), data_(map)
{
}
using self_iter = iterator_base<IT, M>;
IT operator*()
{
return IT(index_, &data_[index_]);
}
self_iter& operator++()
{
index_++;
return *this;
}
self_iter operator++(int)
{
self_iter tmp(*this);
operator++();
return tmp;
}
bool operator==(self_iter other) const
{
assert(&data_ == &other.data_);
return index_ == other.index_;
}
bool operator!=(self_iter other) const
{
return !(*this == other);
}
private:
letter index_;
M& data_;
};
public:
using key_type = letter;
using mapped_type = T;
using value_type = std::pair<const key_type, mapped_type*>;
using const_value_type = std::pair<const key_type, const mapped_type*>;
private:
static const size_t data_size = letter_end - letter_begin;
using container_type = std::array<mapped_type, data_size>;
public:
using iterator = iterator_base<value_type, self>;
using const_iterator = iterator_base<const_value_type, const self>;
public:
mapped_type& operator[](letter l)
{
return data_[l - letter_begin];
}
const mapped_type& operator[](letter l) const
{
return data_[l - letter_begin];
}
auto begin()
{
return iterator(letter_begin, *this);
}
auto end()
{
return iterator(letter_end, *this);
}
auto begin() const
{
return const_iterator(letter_begin, *this);
}
auto end() const
{
return const_iterator(letter_end, *this);
}
private:
container_type data_;
};
void print_string_letter_map(const letter_map<std::string>& lm)
{
for (auto elem : lm)
{
std::cout << elem.first << "->" << *(elem.second) << std::endl;
}
}
template<typename T>
class std_letter_map : public std::map<letter, T>
{
public:
std_letter_map()
{
for (letter l = letter_begin; l != letter_end; ++l) {
this->emplace(l, T());
}
}
};
void print_string_std_letter_map(const std_letter_map<std::string>& lm)
{
for (const auto& elem : lm)
{
std::cout << elem.first << "->" << elem.second << std::endl;
}
}
int main()
{
letter_map<std::string> lm;
// usually I would use auto& elem here
for (auto elem : lm) {
auto let = elem.first;
// usually this would be without the *
auto& str = *(elem.second);
str = std::string("foo ") + let;
}
print_string_letter_map(lm);
return 0;
}
