An interval-map data structure
up vote
8
down vote
favorite
This data structure maps values from intervals of some type Key which satisfies LessThanComparable<Key> to values of some type T. I remembered this kind of data structure from an interview question.
My current use case is a distributed vector where I want to keep track which MPI rank owns which parts of some global index space.
I am not sure about the reference_wrappers.
Explanation
I use a std::map<Key, optional<T>> where empty optionals are my sentinel for intervals, i.e. marking their end. So when mapping some interval [0,10) to some value x I do this by inserting
map = {{0, x}, {10, {}}}
When inserting another interval, for example [1,3) to y this is going to be
map = {{0, x}, {1, y}, {3, x}, {10, {}}}
Usage
Here is a link to wandbox running the code
#include "fub/IntervalMap.hpp"
#include <string>
#include <iostream>
void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
}
int main()
{
std::cout << std::boolalpha;
auto map = fub::IntervalMap<int, std::string>{};
map.insert(0, 10, "foo");
print(std::cout, map.std_map());
std::cout << "map.at(0) = " << map.at(0) << 'n';
std::cout << "map[10].has_value() = " << map[10].has_value() << "nn";
map.insert(3, 7, "bar");
print(std::cout, map.std_map());
std::cout << "map.at(5) = " << map.at(5) << "nn";
map.remove(2, 8);
print(std::cout, map.std_map());
std::cout << "map[5].has_value() = " << map[5].has_value() << 'n';
}
Output
{0, foo}
{10, {}}
map.at(0) = foo
map[10].has_value() = false
{0, foo}
{3, bar}
{7, foo}
{10, {}}
map.at(5) = bar
{0, foo}
{2, {}}
{8, foo}
{10, {}}
map[5].has_value() = false
Relevant source code
#ifndef FUB_INTERVALMAP_HPP
#define FUB_INTERVALMAP_HPP
#include <map>
#include <optional>
#include <stdexcept>
namespace fub
{
template <
typename Key,
typename T,
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
> class IntervalMap
{
private:
using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
map_type map_;
public:
// CONSTRUCTORS
IntervalMap()
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&&) = default;
IntervalMap(IntervalMap&& other, const Allocator& alloc)
noexcept(std::is_nothrow_move_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
// ACCESSORS
const map_type&
std_map() const&
noexcept
{ return map_; }
std::optional<std::reference_wrapper<const T>>
operator(const Key& key) const&
noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
const T&
at(const Key& key) const&
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool
empty() const
noexcept
{
return map_.empty();
}
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto first = map_.lower_bound(lower_key);
auto last = map_.upper_bound(upper_key);
if (last != map_.begin()) {
auto prev = std::prev(last);
last = map_.insert(last, std::make_pair(std::move(upper_key), prev->second));
}
if (first == map_.begin() || !has_value(std::prev(first))) {
map_.erase(first, last);
} else {
first = map_.insert(first, std::make_pair(std::move(lower_key), std::optional<T>()));
first->second.reset();
map_.erase(std::next(first), last);
}
erase_if_empty(last);
}
private:
/// brief compares to key values with maps comparator
bool
compare(const Key& lhs, const Key& rhs) const
noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
{ return std::invoke(map_.key_comp(), lhs, rhs); }
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
auto insert_upper_bound(Key&& upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool
has_value(typename map_type::const_iterator iterator) const
noexcept
{ return iterator->second.has_value(); }
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void
erase_if_empty(typename map_type::const_iterator iterator)
noexcept
{
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
}
}
};
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
}
#endif // !INTERVALMAP_HPP
c++ interval hash-map c++17
asked Mar 20 '17 at 21:24
Maikel
560412
add a comment |
up vote
8
down vote
favorite
This data structure maps values from intervals of some type Key which satisfies LessThanComparable<Key> to values of some type T. I remembered this kind of data structure from an interview question.
My current use case is a distributed vector where I want to keep track which MPI rank owns which parts of some global index space.
I am not sure about the reference_wrappers.
Explanation
I use a std::map<Key, optional<T>> where empty optionals are my sentinel for intervals, i.e. marking their end. So when mapping some interval [0,10) to some value x I do this by inserting
map = {{0, x}, {10, {}}}
When inserting another interval, for example [1,3) to y this is going to be
map = {{0, x}, {1, y}, {3, x}, {10, {}}}
Usage
Here is a link to wandbox running the code
#include "fub/IntervalMap.hpp"
#include <string>
#include <iostream>
void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
}
int main()
{
std::cout << std::boolalpha;
auto map = fub::IntervalMap<int, std::string>{};
map.insert(0, 10, "foo");
print(std::cout, map.std_map());
std::cout << "map.at(0) = " << map.at(0) << 'n';
std::cout << "map[10].has_value() = " << map[10].has_value() << "nn";
map.insert(3, 7, "bar");
print(std::cout, map.std_map());
std::cout << "map.at(5) = " << map.at(5) << "nn";
map.remove(2, 8);
print(std::cout, map.std_map());
std::cout << "map[5].has_value() = " << map[5].has_value() << 'n';
}
Output
{0, foo}
{10, {}}
map.at(0) = foo
map[10].has_value() = false
{0, foo}
{3, bar}
{7, foo}
{10, {}}
map.at(5) = bar
{0, foo}
{2, {}}
{8, foo}
{10, {}}
map[5].has_value() = false
Relevant source code
#ifndef FUB_INTERVALMAP_HPP
#define FUB_INTERVALMAP_HPP
#include <map>
#include <optional>
#include <stdexcept>
namespace fub
{
template <
typename Key,
typename T,
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
> class IntervalMap
{
private:
using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
map_type map_;
public:
// CONSTRUCTORS
IntervalMap()
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&&) = default;
IntervalMap(IntervalMap&& other, const Allocator& alloc)
noexcept(std::is_nothrow_move_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
// ACCESSORS
const map_type&
std_map() const&
noexcept
{ return map_; }
std::optional<std::reference_wrapper<const T>>
operator(const Key& key) const&
noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
const T&
at(const Key& key) const&
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool
empty() const
noexcept
{
return map_.empty();
}
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto first = map_.lower_bound(lower_key);
auto last = map_.upper_bound(upper_key);
if (last != map_.begin()) {
auto prev = std::prev(last);
last = map_.insert(last, std::make_pair(std::move(upper_key), prev->second));
}
if (first == map_.begin() || !has_value(std::prev(first))) {
map_.erase(first, last);
} else {
first = map_.insert(first, std::make_pair(std::move(lower_key), std::optional<T>()));
first->second.reset();
map_.erase(std::next(first), last);
}
erase_if_empty(last);
}
private:
/// brief compares to key values with maps comparator
bool
compare(const Key& lhs, const Key& rhs) const
noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
{ return std::invoke(map_.key_comp(), lhs, rhs); }
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
auto insert_upper_bound(Key&& upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool
has_value(typename map_type::const_iterator iterator) const
noexcept
{ return iterator->second.has_value(); }
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void
erase_if_empty(typename map_type::const_iterator iterator)
noexcept
{
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
}
}
};
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
}
#endif // !INTERVALMAP_HPP
c++ interval hash-map c++17
asked Mar 20 '17 at 21:24
Maikel
560412
Did you meanComparableLessThan...?
– CiaPan
Mar 21 '17 at 12:31
Oh yeah. I actually meanLessThanComparable: en.cppreference.com/w/cpp/concept/LessThanComparable. But what really is meant, is thatCompareis a predicate onKey.
– Maikel
Mar 21 '17 at 12:32
add a comment |
up vote
8
down vote
favorite
up vote
8
down vote
favorite
This data structure maps values from intervals of some type Key which satisfies LessThanComparable<Key> to values of some type T. I remembered this kind of data structure from an interview question.
My current use case is a distributed vector where I want to keep track which MPI rank owns which parts of some global index space.
I am not sure about the reference_wrappers.
Explanation
I use a std::map<Key, optional<T>> where empty optionals are my sentinel for intervals, i.e. marking their end. So when mapping some interval [0,10) to some value x I do this by inserting
map = {{0, x}, {10, {}}}
When inserting another interval, for example [1,3) to y this is going to be
map = {{0, x}, {1, y}, {3, x}, {10, {}}}
Usage
Here is a link to wandbox running the code
#include "fub/IntervalMap.hpp"
#include <string>
#include <iostream>
void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
}
int main()
{
std::cout << std::boolalpha;
auto map = fub::IntervalMap<int, std::string>{};
map.insert(0, 10, "foo");
print(std::cout, map.std_map());
std::cout << "map.at(0) = " << map.at(0) << 'n';
std::cout << "map[10].has_value() = " << map[10].has_value() << "nn";
map.insert(3, 7, "bar");
print(std::cout, map.std_map());
std::cout << "map.at(5) = " << map.at(5) << "nn";
map.remove(2, 8);
print(std::cout, map.std_map());
std::cout << "map[5].has_value() = " << map[5].has_value() << 'n';
}
Output
{0, foo}
{10, {}}
map.at(0) = foo
map[10].has_value() = false
{0, foo}
{3, bar}
{7, foo}
{10, {}}
map.at(5) = bar
{0, foo}
{2, {}}
{8, foo}
{10, {}}
map[5].has_value() = false
Relevant source code
#ifndef FUB_INTERVALMAP_HPP
#define FUB_INTERVALMAP_HPP
#include <map>
#include <optional>
#include <stdexcept>
namespace fub
{
template <
typename Key,
typename T,
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
> class IntervalMap
{
private:
using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
map_type map_;
public:
// CONSTRUCTORS
IntervalMap()
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&&) = default;
IntervalMap(IntervalMap&& other, const Allocator& alloc)
noexcept(std::is_nothrow_move_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
// ACCESSORS
const map_type&
std_map() const&
noexcept
{ return map_; }
std::optional<std::reference_wrapper<const T>>
operator(const Key& key) const&
noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
const T&
at(const Key& key) const&
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool
empty() const
noexcept
{
return map_.empty();
}
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto first = map_.lower_bound(lower_key);
auto last = map_.upper_bound(upper_key);
if (last != map_.begin()) {
auto prev = std::prev(last);
last = map_.insert(last, std::make_pair(std::move(upper_key), prev->second));
}
if (first == map_.begin() || !has_value(std::prev(first))) {
map_.erase(first, last);
} else {
first = map_.insert(first, std::make_pair(std::move(lower_key), std::optional<T>()));
first->second.reset();
map_.erase(std::next(first), last);
}
erase_if_empty(last);
}
private:
/// brief compares to key values with maps comparator
bool
compare(const Key& lhs, const Key& rhs) const
noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
{ return std::invoke(map_.key_comp(), lhs, rhs); }
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
auto insert_upper_bound(Key&& upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool
has_value(typename map_type::const_iterator iterator) const
noexcept
{ return iterator->second.has_value(); }
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void
erase_if_empty(typename map_type::const_iterator iterator)
noexcept
{
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
}
}
};
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
}
#endif // !INTERVALMAP_HPP
c++ interval hash-map c++17
asked Mar 20 '17 at 21:24
Maikel
560412
This data structure maps values from intervals of some type Key which satisfies LessThanComparable<Key> to values of some type T. I remembered this kind of data structure from an interview question.
My current use case is a distributed vector where I want to keep track which MPI rank owns which parts of some global index space.
I am not sure about the reference_wrappers.
Explanation
I use a std::map<Key, optional<T>> where empty optionals are my sentinel for intervals, i.e. marking their end. So when mapping some interval [0,10) to some value x I do this by inserting
map = {{0, x}, {10, {}}}
When inserting another interval, for example [1,3) to y this is going to be
map = {{0, x}, {1, y}, {3, x}, {10, {}}}
Usage
Here is a link to wandbox running the code
#include "fub/IntervalMap.hpp"
#include <string>
#include <iostream>
void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
}
int main()
{
std::cout << std::boolalpha;
auto map = fub::IntervalMap<int, std::string>{};
map.insert(0, 10, "foo");
print(std::cout, map.std_map());
std::cout << "map.at(0) = " << map.at(0) << 'n';
std::cout << "map[10].has_value() = " << map[10].has_value() << "nn";
map.insert(3, 7, "bar");
print(std::cout, map.std_map());
std::cout << "map.at(5) = " << map.at(5) << "nn";
map.remove(2, 8);
print(std::cout, map.std_map());
std::cout << "map[5].has_value() = " << map[5].has_value() << 'n';
}
Output
{0, foo}
{10, {}}
map.at(0) = foo
map[10].has_value() = false
{0, foo}
{3, bar}
{7, foo}
{10, {}}
map.at(5) = bar
{0, foo}
{2, {}}
{8, foo}
{10, {}}
map[5].has_value() = false
Relevant source code
#ifndef FUB_INTERVALMAP_HPP
#define FUB_INTERVALMAP_HPP
#include <map>
#include <optional>
#include <stdexcept>
namespace fub
{
template <
typename Key,
typename T,
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
> class IntervalMap
{
private:
using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
map_type map_;
public:
// CONSTRUCTORS
IntervalMap()
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&&) = default;
IntervalMap(IntervalMap&& other, const Allocator& alloc)
noexcept(std::is_nothrow_move_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
// ACCESSORS
const map_type&
std_map() const&
noexcept
{ return map_; }
std::optional<std::reference_wrapper<const T>>
operator(const Key& key) const&
noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
const T&
at(const Key& key) const&
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool
empty() const
noexcept
{
return map_.empty();
}
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto first = map_.lower_bound(lower_key);
auto last = map_.upper_bound(upper_key);
if (last != map_.begin()) {
auto prev = std::prev(last);
last = map_.insert(last, std::make_pair(std::move(upper_key), prev->second));
}
if (first == map_.begin() || !has_value(std::prev(first))) {
map_.erase(first, last);
} else {
first = map_.insert(first, std::make_pair(std::move(lower_key), std::optional<T>()));
first->second.reset();
map_.erase(std::next(first), last);
}
erase_if_empty(last);
}
private:
/// brief compares to key values with maps comparator
bool
compare(const Key& lhs, const Key& rhs) const
noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
{ return std::invoke(map_.key_comp(), lhs, rhs); }
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
auto insert_upper_bound(Key&& upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool
has_value(typename map_type::const_iterator iterator) const
noexcept
{ return iterator->second.has_value(); }
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void
erase_if_empty(typename map_type::const_iterator iterator)
noexcept
{
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
}
}
};
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
}
#endif // !INTERVALMAP_HPP
c++ interval hash-map c++17
c++ interval hash-map c++17
asked Mar 20 '17 at 21:24
Maikel
560412
asked Mar 20 '17 at 21:24
Maikel
560412
edited Mar 27 '17 at 16:00
asked Mar 20 '17 at 21:24
Maikel
560412
asked Mar 20 '17 at 21:24
Maikel
560412
asked Mar 20 '17 at 21:24
Maikel
560412
560412
Did you meanComparableLessThan...?
– CiaPan
Mar 21 '17 at 12:31
Oh yeah. I actually meanLessThanComparable: en.cppreference.com/w/cpp/concept/LessThanComparable. But what really is meant, is thatCompareis a predicate onKey.
– Maikel
Mar 21 '17 at 12:32
add a comment |
Did you meanComparableLessThan...?
– CiaPan
Mar 21 '17 at 12:31
Oh yeah. I actually meanLessThanComparable: en.cppreference.com/w/cpp/concept/LessThanComparable. But what really is meant, is thatCompareis a predicate onKey.
– Maikel
Mar 21 '17 at 12:32
Did you mean
ComparableLessThan...?– CiaPan
Mar 21 '17 at 12:31
Did you mean
ComparableLessThan...?– CiaPan
Mar 21 '17 at 12:31
Oh yeah. I actually mean
LessThanComparable: en.cppreference.com/w/cpp/concept/LessThanComparable. But what really is meant, is that Compare is a predicate on Key.– Maikel
Mar 21 '17 at 12:32
Oh yeah. I actually mean
LessThanComparable: en.cppreference.com/w/cpp/concept/LessThanComparable. But what really is meant, is that Compare is a predicate on Key.– Maikel
Mar 21 '17 at 12:32
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
You seem to have a good grasp of non trivial concepts, but then you produce very over-engineered code.
Please see my refactoring here as well as below.
Also, yes you remembered the interview question, but it seems, not all of it. There is a requirement that adjacent values can not be inserted. If the situation is:
(0,'A')(6, 'B')(42,'A')
it is not allowed to insert (6,41,'A') ... as there are "value clashes" on both sides.
Also the interval size is bound. 0 .. SIZE
Finally. I have made C++ solution where Key and Value, are both (non trivial) classes. Then I have made pure C solution which I like more. It is simpler. Not faster for very large SIZE's but fast enough.
Here is the whole of the refactoring of your solution:
// dbj.org 2018 DEC
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <map>
#include <optional>
#include <stdexcept>
#include <string>
#include <iterator>
using namespace std;
// terminating error
inline void terror( bool rez, const char * msg ) {
if ( rez) return ;
assert(msg);
perror(msg);
exit(EXIT_FAILURE) ;
}
#define ST_(x) #x
#define ST(x) ST_(x)
#define TT(x) std::cout << std::endl << ST(x) << std::endl ; (x)
#define dbj_verify(x) terror(x, "nn" __FILE__ "(" ST(__LINE__) ")ntERROR: " ST(x) " -- evaluated to falsenn")
// this
// https://codereview.stackexchange.com/questions/158341/an-interval-map-data-structure
// refactored and hopefully simplified and improved
namespace fub
{
template <
typename Key,
typename T
/*
DBJ moved this to be public typedefs usabel by template definitions clients
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
*/
> class IntervalMap final /* DBJ added 'final' */
{
// DBJ -- typedef are to be public and thus used by the client code
// this is standard C++ standard convention
public:
// DBJ moved these two from template parameters so that client code can use them
// using Compare = std::less<Key>;
// using Allocator = std::allocator<std::pair<const Key, std::optional<T>>>;
// DBJ removed --> private:
// using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
using map_type = std::map<Key, std::optional<T> >;
map_type map_;
// DBJ 00: this much simplifies methods inside the template
using type = IntervalMap ;
// DBJ 01: using static_assert simplifies the code
// check the type requirements only once at compile time
// no need to mention them in every comment
static_assert(std::is_nothrow_default_constructible_v<map_type>);
static_assert(is_copy_constructible_v <T> ) ;
// DBJ removed --> public:
/*
IntervalMap()
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&& other, const Allocator& alloc)
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
*/
/* DBJ 02: commented out -- reason: this is not necessary
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
IntervalMap(IntervalMap&&) = default;
*/
// ACCESSORS
//DBJ 03: commented out -- reasone: compiler will do the most efficient move/copy elision
// stanbdard C++ is based on value semantics
// no need to return by const reference
// const map_type& std_map() const& noexcept { return map_; }
map_type std_map() const noexcept { return map_; }
// DBJ 04: removed use of reference_wrapper -- reason: see DBJ 03
// std::optional<std::reference_wrapper<const T>>
std::optional<T>
operator(const Key& key) const // DBJ removed --> &
// DBJ removed, see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
//DBJ 05: removed -- reason const & not necessary in standard C++
// const T & at(const Key& key) const&
T at(Key key) const
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool empty() const noexcept { return map_.empty(); }
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto upper_ = map_.find(upper_key);
auto current_ = map_.find(lower_key);
while( (current_ != map_.end()) || (current_ != upper_ ))
{
auto next_ = next(current_);
map_.erase(current_) ;
current_ = next_ ;
}
if(upper_ != map_.end())
map_.erase(upper_);
}
private:
/// brief compares to key values with maps comparator
/// DBJ: the comment above is completely confusing
// obvously jus two keys are compared, between thmeselves
// also and again const references are not an optimization
// bool compare(const Key& lhs, const Key& rhs) const
// as this is standard C++
// also DBJ -- see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
bool compare(Key lhs, Key rhs) const
{
// DBJ removed --> return std::invoke(map_.key_comp(), lhs, rhs);
// we have defined the Compare type in the template prologue
// although it is not clear why?
return lhs < rhs ;
}
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
/// DBJ removed the use of r-refernce -- auto insert_upper_bound(Key&& upper)
auto insert_upper_bound(Key upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool has_value(typename map_type::const_iterator iterator) const noexcept
{
return iterator->second.has_value();
}
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void erase_if_empty(typename map_type::const_iterator iterator) noexcept
{
/*
DBJ commented out
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
*/
if (iterator == map_.end() ) return ;
if ( has_value(iterator) ) return ;
map_.erase(iterator);
}
// DBJ moved these two in here and made them friends
friend bool operator==( const type & lhs, const type & rhs)
{
return lhs.map() == rhs.map();
}
friend bool operator!=( const type & lhs, const type & rhs)
{
return ! ( lhs.map() == rhs.map() );
}
}; // DBJ added comment --> eof IntervalMap
/*
DBJ commented out -- reason -- 1. these are much simple if made as friend's to the IntervalMap
2. they both need not have full implementeation as not_eqauls
is ! equals ... see above
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
*/
} // DBJ added comment -> eof namespace
// void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
// DBH changed to std ostream operator handling the required map type
std::ostream& operator << (std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
return out ;
}
// DBJ added
using fub_interval_map_type = fub::IntervalMap<int, string> ;
std::ostream& operator << (std::ostream& out, const fub_interval_map_type & fub_map)
{
return out << fub_map.std_map();
}
int main()
{
cout << boolalpha;
auto map = fub_interval_map_type{} ;
TT(map.insert(0, 10, "foo"));
cout << map << "map.at(0) = " << map.at(0) << 'n';
cout << "map[10].has_value() = " << map[10].has_value() << "nn";
TT(map.insert(3, 7, "bar"));
cout << map << "map.at(5) = " << map.at(5) << "nn";
TT(map.remove(2, 8));
cout << map << "map[5].has_value() = " << map[5].has_value() << 'n';
}
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
answered yesterday
Chef Gladiator
11
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
It's better to present proposed improvements in the body of your answer, rather than pointing to external sites without explanation. Please incorporate those suggestions into your answer (keep the link as additional information if you feel it helps, but don't make your answer useless without it). Thanks.
– Toby Speight
yesterday
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
You seem to have a good grasp of non trivial concepts, but then you produce very over-engineered code.
Please see my refactoring here as well as below.
Also, yes you remembered the interview question, but it seems, not all of it. There is a requirement that adjacent values can not be inserted. If the situation is:
(0,'A')(6, 'B')(42,'A')
it is not allowed to insert (6,41,'A') ... as there are "value clashes" on both sides.
Also the interval size is bound. 0 .. SIZE
Finally. I have made C++ solution where Key and Value, are both (non trivial) classes. Then I have made pure C solution which I like more. It is simpler. Not faster for very large SIZE's but fast enough.
Here is the whole of the refactoring of your solution:
// dbj.org 2018 DEC
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <map>
#include <optional>
#include <stdexcept>
#include <string>
#include <iterator>
using namespace std;
// terminating error
inline void terror( bool rez, const char * msg ) {
if ( rez) return ;
assert(msg);
perror(msg);
exit(EXIT_FAILURE) ;
}
#define ST_(x) #x
#define ST(x) ST_(x)
#define TT(x) std::cout << std::endl << ST(x) << std::endl ; (x)
#define dbj_verify(x) terror(x, "nn" __FILE__ "(" ST(__LINE__) ")ntERROR: " ST(x) " -- evaluated to falsenn")
// this
// https://codereview.stackexchange.com/questions/158341/an-interval-map-data-structure
// refactored and hopefully simplified and improved
namespace fub
{
template <
typename Key,
typename T
/*
DBJ moved this to be public typedefs usabel by template definitions clients
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
*/
> class IntervalMap final /* DBJ added 'final' */
{
// DBJ -- typedef are to be public and thus used by the client code
// this is standard C++ standard convention
public:
// DBJ moved these two from template parameters so that client code can use them
// using Compare = std::less<Key>;
// using Allocator = std::allocator<std::pair<const Key, std::optional<T>>>;
// DBJ removed --> private:
// using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
using map_type = std::map<Key, std::optional<T> >;
map_type map_;
// DBJ 00: this much simplifies methods inside the template
using type = IntervalMap ;
// DBJ 01: using static_assert simplifies the code
// check the type requirements only once at compile time
// no need to mention them in every comment
static_assert(std::is_nothrow_default_constructible_v<map_type>);
static_assert(is_copy_constructible_v <T> ) ;
// DBJ removed --> public:
/*
IntervalMap()
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&& other, const Allocator& alloc)
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
*/
/* DBJ 02: commented out -- reason: this is not necessary
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
IntervalMap(IntervalMap&&) = default;
*/
// ACCESSORS
//DBJ 03: commented out -- reasone: compiler will do the most efficient move/copy elision
// stanbdard C++ is based on value semantics
// no need to return by const reference
// const map_type& std_map() const& noexcept { return map_; }
map_type std_map() const noexcept { return map_; }
// DBJ 04: removed use of reference_wrapper -- reason: see DBJ 03
// std::optional<std::reference_wrapper<const T>>
std::optional<T>
operator(const Key& key) const // DBJ removed --> &
// DBJ removed, see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
//DBJ 05: removed -- reason const & not necessary in standard C++
// const T & at(const Key& key) const&
T at(Key key) const
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool empty() const noexcept { return map_.empty(); }
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto upper_ = map_.find(upper_key);
auto current_ = map_.find(lower_key);
while( (current_ != map_.end()) || (current_ != upper_ ))
{
auto next_ = next(current_);
map_.erase(current_) ;
current_ = next_ ;
}
if(upper_ != map_.end())
map_.erase(upper_);
}
private:
/// brief compares to key values with maps comparator
/// DBJ: the comment above is completely confusing
// obvously jus two keys are compared, between thmeselves
// also and again const references are not an optimization
// bool compare(const Key& lhs, const Key& rhs) const
// as this is standard C++
// also DBJ -- see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
bool compare(Key lhs, Key rhs) const
{
// DBJ removed --> return std::invoke(map_.key_comp(), lhs, rhs);
// we have defined the Compare type in the template prologue
// although it is not clear why?
return lhs < rhs ;
}
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
/// DBJ removed the use of r-refernce -- auto insert_upper_bound(Key&& upper)
auto insert_upper_bound(Key upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool has_value(typename map_type::const_iterator iterator) const noexcept
{
return iterator->second.has_value();
}
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void erase_if_empty(typename map_type::const_iterator iterator) noexcept
{
/*
DBJ commented out
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
*/
if (iterator == map_.end() ) return ;
if ( has_value(iterator) ) return ;
map_.erase(iterator);
}
// DBJ moved these two in here and made them friends
friend bool operator==( const type & lhs, const type & rhs)
{
return lhs.map() == rhs.map();
}
friend bool operator!=( const type & lhs, const type & rhs)
{
return ! ( lhs.map() == rhs.map() );
}
}; // DBJ added comment --> eof IntervalMap
/*
DBJ commented out -- reason -- 1. these are much simple if made as friend's to the IntervalMap
2. they both need not have full implementeation as not_eqauls
is ! equals ... see above
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
*/
} // DBJ added comment -> eof namespace
// void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
// DBH changed to std ostream operator handling the required map type
std::ostream& operator << (std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
return out ;
}
// DBJ added
using fub_interval_map_type = fub::IntervalMap<int, string> ;
std::ostream& operator << (std::ostream& out, const fub_interval_map_type & fub_map)
{
return out << fub_map.std_map();
}
int main()
{
cout << boolalpha;
auto map = fub_interval_map_type{} ;
TT(map.insert(0, 10, "foo"));
cout << map << "map.at(0) = " << map.at(0) << 'n';
cout << "map[10].has_value() = " << map[10].has_value() << "nn";
TT(map.insert(3, 7, "bar"));
cout << map << "map.at(5) = " << map.at(5) << "nn";
TT(map.remove(2, 8));
cout << map << "map[5].has_value() = " << map[5].has_value() << 'n';
}
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
answered yesterday
Chef Gladiator
11
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
It's better to present proposed improvements in the body of your answer, rather than pointing to external sites without explanation. Please incorporate those suggestions into your answer (keep the link as additional information if you feel it helps, but don't make your answer useless without it). Thanks.
– Toby Speight
yesterday
add a comment |
up vote
0
down vote
You seem to have a good grasp of non trivial concepts, but then you produce very over-engineered code.
Please see my refactoring here as well as below.
Also, yes you remembered the interview question, but it seems, not all of it. There is a requirement that adjacent values can not be inserted. If the situation is:
(0,'A')(6, 'B')(42,'A')
it is not allowed to insert (6,41,'A') ... as there are "value clashes" on both sides.
Also the interval size is bound. 0 .. SIZE
Finally. I have made C++ solution where Key and Value, are both (non trivial) classes. Then I have made pure C solution which I like more. It is simpler. Not faster for very large SIZE's but fast enough.
Here is the whole of the refactoring of your solution:
// dbj.org 2018 DEC
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <map>
#include <optional>
#include <stdexcept>
#include <string>
#include <iterator>
using namespace std;
// terminating error
inline void terror( bool rez, const char * msg ) {
if ( rez) return ;
assert(msg);
perror(msg);
exit(EXIT_FAILURE) ;
}
#define ST_(x) #x
#define ST(x) ST_(x)
#define TT(x) std::cout << std::endl << ST(x) << std::endl ; (x)
#define dbj_verify(x) terror(x, "nn" __FILE__ "(" ST(__LINE__) ")ntERROR: " ST(x) " -- evaluated to falsenn")
// this
// https://codereview.stackexchange.com/questions/158341/an-interval-map-data-structure
// refactored and hopefully simplified and improved
namespace fub
{
template <
typename Key,
typename T
/*
DBJ moved this to be public typedefs usabel by template definitions clients
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
*/
> class IntervalMap final /* DBJ added 'final' */
{
// DBJ -- typedef are to be public and thus used by the client code
// this is standard C++ standard convention
public:
// DBJ moved these two from template parameters so that client code can use them
// using Compare = std::less<Key>;
// using Allocator = std::allocator<std::pair<const Key, std::optional<T>>>;
// DBJ removed --> private:
// using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
using map_type = std::map<Key, std::optional<T> >;
map_type map_;
// DBJ 00: this much simplifies methods inside the template
using type = IntervalMap ;
// DBJ 01: using static_assert simplifies the code
// check the type requirements only once at compile time
// no need to mention them in every comment
static_assert(std::is_nothrow_default_constructible_v<map_type>);
static_assert(is_copy_constructible_v <T> ) ;
// DBJ removed --> public:
/*
IntervalMap()
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&& other, const Allocator& alloc)
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
*/
/* DBJ 02: commented out -- reason: this is not necessary
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
IntervalMap(IntervalMap&&) = default;
*/
// ACCESSORS
//DBJ 03: commented out -- reasone: compiler will do the most efficient move/copy elision
// stanbdard C++ is based on value semantics
// no need to return by const reference
// const map_type& std_map() const& noexcept { return map_; }
map_type std_map() const noexcept { return map_; }
// DBJ 04: removed use of reference_wrapper -- reason: see DBJ 03
// std::optional<std::reference_wrapper<const T>>
std::optional<T>
operator(const Key& key) const // DBJ removed --> &
// DBJ removed, see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
//DBJ 05: removed -- reason const & not necessary in standard C++
// const T & at(const Key& key) const&
T at(Key key) const
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool empty() const noexcept { return map_.empty(); }
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto upper_ = map_.find(upper_key);
auto current_ = map_.find(lower_key);
while( (current_ != map_.end()) || (current_ != upper_ ))
{
auto next_ = next(current_);
map_.erase(current_) ;
current_ = next_ ;
}
if(upper_ != map_.end())
map_.erase(upper_);
}
private:
/// brief compares to key values with maps comparator
/// DBJ: the comment above is completely confusing
// obvously jus two keys are compared, between thmeselves
// also and again const references are not an optimization
// bool compare(const Key& lhs, const Key& rhs) const
// as this is standard C++
// also DBJ -- see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
bool compare(Key lhs, Key rhs) const
{
// DBJ removed --> return std::invoke(map_.key_comp(), lhs, rhs);
// we have defined the Compare type in the template prologue
// although it is not clear why?
return lhs < rhs ;
}
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
/// DBJ removed the use of r-refernce -- auto insert_upper_bound(Key&& upper)
auto insert_upper_bound(Key upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool has_value(typename map_type::const_iterator iterator) const noexcept
{
return iterator->second.has_value();
}
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void erase_if_empty(typename map_type::const_iterator iterator) noexcept
{
/*
DBJ commented out
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
*/
if (iterator == map_.end() ) return ;
if ( has_value(iterator) ) return ;
map_.erase(iterator);
}
// DBJ moved these two in here and made them friends
friend bool operator==( const type & lhs, const type & rhs)
{
return lhs.map() == rhs.map();
}
friend bool operator!=( const type & lhs, const type & rhs)
{
return ! ( lhs.map() == rhs.map() );
}
}; // DBJ added comment --> eof IntervalMap
/*
DBJ commented out -- reason -- 1. these are much simple if made as friend's to the IntervalMap
2. they both need not have full implementeation as not_eqauls
is ! equals ... see above
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
*/
} // DBJ added comment -> eof namespace
// void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
// DBH changed to std ostream operator handling the required map type
std::ostream& operator << (std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
return out ;
}
// DBJ added
using fub_interval_map_type = fub::IntervalMap<int, string> ;
std::ostream& operator << (std::ostream& out, const fub_interval_map_type & fub_map)
{
return out << fub_map.std_map();
}
int main()
{
cout << boolalpha;
auto map = fub_interval_map_type{} ;
TT(map.insert(0, 10, "foo"));
cout << map << "map.at(0) = " << map.at(0) << 'n';
cout << "map[10].has_value() = " << map[10].has_value() << "nn";
TT(map.insert(3, 7, "bar"));
cout << map << "map.at(5) = " << map.at(5) << "nn";
TT(map.remove(2, 8));
cout << map << "map[5].has_value() = " << map[5].has_value() << 'n';
}
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
answered yesterday
Chef Gladiator
11
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
It's better to present proposed improvements in the body of your answer, rather than pointing to external sites without explanation. Please incorporate those suggestions into your answer (keep the link as additional information if you feel it helps, but don't make your answer useless without it). Thanks.
– Toby Speight
yesterday
add a comment |
up vote
0
down vote
up vote
0
down vote
You seem to have a good grasp of non trivial concepts, but then you produce very over-engineered code.
Please see my refactoring here as well as below.
Also, yes you remembered the interview question, but it seems, not all of it. There is a requirement that adjacent values can not be inserted. If the situation is:
(0,'A')(6, 'B')(42,'A')
it is not allowed to insert (6,41,'A') ... as there are "value clashes" on both sides.
Also the interval size is bound. 0 .. SIZE
Finally. I have made C++ solution where Key and Value, are both (non trivial) classes. Then I have made pure C solution which I like more. It is simpler. Not faster for very large SIZE's but fast enough.
Here is the whole of the refactoring of your solution:
// dbj.org 2018 DEC
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <map>
#include <optional>
#include <stdexcept>
#include <string>
#include <iterator>
using namespace std;
// terminating error
inline void terror( bool rez, const char * msg ) {
if ( rez) return ;
assert(msg);
perror(msg);
exit(EXIT_FAILURE) ;
}
#define ST_(x) #x
#define ST(x) ST_(x)
#define TT(x) std::cout << std::endl << ST(x) << std::endl ; (x)
#define dbj_verify(x) terror(x, "nn" __FILE__ "(" ST(__LINE__) ")ntERROR: " ST(x) " -- evaluated to falsenn")
// this
// https://codereview.stackexchange.com/questions/158341/an-interval-map-data-structure
// refactored and hopefully simplified and improved
namespace fub
{
template <
typename Key,
typename T
/*
DBJ moved this to be public typedefs usabel by template definitions clients
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
*/
> class IntervalMap final /* DBJ added 'final' */
{
// DBJ -- typedef are to be public and thus used by the client code
// this is standard C++ standard convention
public:
// DBJ moved these two from template parameters so that client code can use them
// using Compare = std::less<Key>;
// using Allocator = std::allocator<std::pair<const Key, std::optional<T>>>;
// DBJ removed --> private:
// using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
using map_type = std::map<Key, std::optional<T> >;
map_type map_;
// DBJ 00: this much simplifies methods inside the template
using type = IntervalMap ;
// DBJ 01: using static_assert simplifies the code
// check the type requirements only once at compile time
// no need to mention them in every comment
static_assert(std::is_nothrow_default_constructible_v<map_type>);
static_assert(is_copy_constructible_v <T> ) ;
// DBJ removed --> public:
/*
IntervalMap()
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&& other, const Allocator& alloc)
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
*/
/* DBJ 02: commented out -- reason: this is not necessary
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
IntervalMap(IntervalMap&&) = default;
*/
// ACCESSORS
//DBJ 03: commented out -- reasone: compiler will do the most efficient move/copy elision
// stanbdard C++ is based on value semantics
// no need to return by const reference
// const map_type& std_map() const& noexcept { return map_; }
map_type std_map() const noexcept { return map_; }
// DBJ 04: removed use of reference_wrapper -- reason: see DBJ 03
// std::optional<std::reference_wrapper<const T>>
std::optional<T>
operator(const Key& key) const // DBJ removed --> &
// DBJ removed, see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
//DBJ 05: removed -- reason const & not necessary in standard C++
// const T & at(const Key& key) const&
T at(Key key) const
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool empty() const noexcept { return map_.empty(); }
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto upper_ = map_.find(upper_key);
auto current_ = map_.find(lower_key);
while( (current_ != map_.end()) || (current_ != upper_ ))
{
auto next_ = next(current_);
map_.erase(current_) ;
current_ = next_ ;
}
if(upper_ != map_.end())
map_.erase(upper_);
}
private:
/// brief compares to key values with maps comparator
/// DBJ: the comment above is completely confusing
// obvously jus two keys are compared, between thmeselves
// also and again const references are not an optimization
// bool compare(const Key& lhs, const Key& rhs) const
// as this is standard C++
// also DBJ -- see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
bool compare(Key lhs, Key rhs) const
{
// DBJ removed --> return std::invoke(map_.key_comp(), lhs, rhs);
// we have defined the Compare type in the template prologue
// although it is not clear why?
return lhs < rhs ;
}
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
/// DBJ removed the use of r-refernce -- auto insert_upper_bound(Key&& upper)
auto insert_upper_bound(Key upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool has_value(typename map_type::const_iterator iterator) const noexcept
{
return iterator->second.has_value();
}
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void erase_if_empty(typename map_type::const_iterator iterator) noexcept
{
/*
DBJ commented out
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
*/
if (iterator == map_.end() ) return ;
if ( has_value(iterator) ) return ;
map_.erase(iterator);
}
// DBJ moved these two in here and made them friends
friend bool operator==( const type & lhs, const type & rhs)
{
return lhs.map() == rhs.map();
}
friend bool operator!=( const type & lhs, const type & rhs)
{
return ! ( lhs.map() == rhs.map() );
}
}; // DBJ added comment --> eof IntervalMap
/*
DBJ commented out -- reason -- 1. these are much simple if made as friend's to the IntervalMap
2. they both need not have full implementeation as not_eqauls
is ! equals ... see above
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
*/
} // DBJ added comment -> eof namespace
// void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
// DBH changed to std ostream operator handling the required map type
std::ostream& operator << (std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
return out ;
}
// DBJ added
using fub_interval_map_type = fub::IntervalMap<int, string> ;
std::ostream& operator << (std::ostream& out, const fub_interval_map_type & fub_map)
{
return out << fub_map.std_map();
}
int main()
{
cout << boolalpha;
auto map = fub_interval_map_type{} ;
TT(map.insert(0, 10, "foo"));
cout << map << "map.at(0) = " << map.at(0) << 'n';
cout << "map[10].has_value() = " << map[10].has_value() << "nn";
TT(map.insert(3, 7, "bar"));
cout << map << "map.at(5) = " << map.at(5) << "nn";
TT(map.remove(2, 8));
cout << map << "map[5].has_value() = " << map[5].has_value() << 'n';
}
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
answered yesterday
Chef Gladiator
11
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
You seem to have a good grasp of non trivial concepts, but then you produce very over-engineered code.
Please see my refactoring here as well as below.
Also, yes you remembered the interview question, but it seems, not all of it. There is a requirement that adjacent values can not be inserted. If the situation is:
(0,'A')(6, 'B')(42,'A')
it is not allowed to insert (6,41,'A') ... as there are "value clashes" on both sides.
Also the interval size is bound. 0 .. SIZE
Finally. I have made C++ solution where Key and Value, are both (non trivial) classes. Then I have made pure C solution which I like more. It is simpler. Not faster for very large SIZE's but fast enough.
Here is the whole of the refactoring of your solution:
// dbj.org 2018 DEC
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <map>
#include <optional>
#include <stdexcept>
#include <string>
#include <iterator>
using namespace std;
// terminating error
inline void terror( bool rez, const char * msg ) {
if ( rez) return ;
assert(msg);
perror(msg);
exit(EXIT_FAILURE) ;
}
#define ST_(x) #x
#define ST(x) ST_(x)
#define TT(x) std::cout << std::endl << ST(x) << std::endl ; (x)
#define dbj_verify(x) terror(x, "nn" __FILE__ "(" ST(__LINE__) ")ntERROR: " ST(x) " -- evaluated to falsenn")
// this
// https://codereview.stackexchange.com/questions/158341/an-interval-map-data-structure
// refactored and hopefully simplified and improved
namespace fub
{
template <
typename Key,
typename T
/*
DBJ moved this to be public typedefs usabel by template definitions clients
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, std::optional<T>>>
*/
> class IntervalMap final /* DBJ added 'final' */
{
// DBJ -- typedef are to be public and thus used by the client code
// this is standard C++ standard convention
public:
// DBJ moved these two from template parameters so that client code can use them
// using Compare = std::less<Key>;
// using Allocator = std::allocator<std::pair<const Key, std::optional<T>>>;
// DBJ removed --> private:
// using map_type = std::map<Key, std::optional<T>, Compare, Allocator>;
using map_type = std::map<Key, std::optional<T> >;
map_type map_;
// DBJ 00: this much simplifies methods inside the template
using type = IntervalMap ;
// DBJ 01: using static_assert simplifies the code
// check the type requirements only once at compile time
// no need to mention them in every comment
static_assert(std::is_nothrow_default_constructible_v<map_type>);
static_assert(is_copy_constructible_v <T> ) ;
// DBJ removed --> public:
/*
IntervalMap()
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: IntervalMap{Compare()}
{}
explicit
IntervalMap(const Compare& comp, const Allocator& alloc = Allocator())
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{comp, alloc}
{}
IntervalMap(const IntervalMap&) = default;
IntervalMap(const IntervalMap& other, const Allocator& alloc)
: map_{other.map_, alloc}
{}
IntervalMap(IntervalMap&& other, const Allocator& alloc)
// DBJ removed. See DBJ 01 -- noexcept(std::is_nothrow_default_constructible_v<map_type>)
: map_{std::move(other.map_), alloc}
{}
*/
/* DBJ 02: commented out -- reason: this is not necessary
~IntervalMap() = default;
IntervalMap& operator=(const IntervalMap&) = default;
IntervalMap& operator=(IntervalMap&&) = default;
IntervalMap(IntervalMap&&) = default;
*/
// ACCESSORS
//DBJ 03: commented out -- reasone: compiler will do the most efficient move/copy elision
// stanbdard C++ is based on value semantics
// no need to return by const reference
// const map_type& std_map() const& noexcept { return map_; }
map_type std_map() const noexcept { return map_; }
// DBJ 04: removed use of reference_wrapper -- reason: see DBJ 03
// std::optional<std::reference_wrapper<const T>>
std::optional<T>
operator(const Key& key) const // DBJ removed --> &
// DBJ removed, see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(const Key&, const Key&)>)
{
auto ub = map_.upper_bound(key);
if (ub == map_.begin()) {
return {};
}
return (--ub)->second;
}
//DBJ 05: removed -- reason const & not necessary in standard C++
// const T & at(const Key& key) const&
T at(Key key) const
{
auto ub = this->operator(key);
if (!ub.has_value()) {
throw std::out_of_range {
"IntervalMap::at: index is out of bounds."
};
}
return *ub;
}
// CAPACITY
bool empty() const noexcept { return map_.empty(); }
// MODIFIERS
/// brief assigns a `value` to a given interval [lower, upper).
/// note `T` needs to be `CopyConstructible` for `insert_upper_bound`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
insert(Key lower, Key upper, T value)
{
if (!compare(lower, upper)) {
return;
}
auto last = insert_upper_bound(std::move(upper));
auto first = map_.lower_bound(lower);
map_.erase(first, last);
map_.insert(last, std::make_pair(std::move(lower), std::move(value)));
}
/// brief removes all values in the given interval [lower, upper).
/// note this requires that `T` is `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
void
remove(Key lower_key, Key upper_key)
{
if (!compare(lower_key, upper_key)) {
return;
}
auto upper_ = map_.find(upper_key);
auto current_ = map_.find(lower_key);
while( (current_ != map_.end()) || (current_ != upper_ ))
{
auto next_ = next(current_);
map_.erase(current_) ;
current_ = next_ ;
}
if(upper_ != map_.end())
map_.erase(upper_);
}
private:
/// brief compares to key values with maps comparator
/// DBJ: the comment above is completely confusing
// obvously jus two keys are compared, between thmeselves
// also and again const references are not an optimization
// bool compare(const Key& lhs, const Key& rhs) const
// as this is standard C++
// also DBJ -- see DBJ 01 -- noexcept(std::is_nothrow_callable_v<Compare(Key, Key)>)
bool compare(Key lhs, Key rhs) const
{
// DBJ removed --> return std::invoke(map_.key_comp(), lhs, rhs);
// we have defined the Compare type in the template prologue
// although it is not clear why?
return lhs < rhs ;
}
/// brief inserts an upper bound such that super sets are valid
/// note this is a helper function for `insert()`
/// note `T` needs to be `CopyConstructible`
/// DBJ: no need to emphasize this in every comment, see DBJ 01
/// DBJ removed the use of r-refernce -- auto insert_upper_bound(Key&& upper)
auto insert_upper_bound(Key upper)
{
auto last = map_.upper_bound(upper);
if (last == map_.begin()) {
return map_.insert(last, std::make_pair(std::move(upper), std::optional<T>{}));
}
auto&& value_before = std::prev(last)->second;
return map_.insert(last, std::make_pair(std::move(upper), value_before));
}
/// brief tests if there is a value at the given position.
/// note iterator has to be deferencable
bool has_value(typename map_type::const_iterator iterator) const noexcept
{
return iterator->second.has_value();
}
/// brief erases the iterator if it points to an empty optional.
/// note if the optional is empty the iterator is a pure upper bound.
/// note this function is a helper function for `remove()`
void erase_if_empty(typename map_type::const_iterator iterator) noexcept
{
/*
DBJ commented out
if (iterator != map_.end() && !has_value(iterator)) {
map_.erase(iterator);
*/
if (iterator == map_.end() ) return ;
if ( has_value(iterator) ) return ;
map_.erase(iterator);
}
// DBJ moved these two in here and made them friends
friend bool operator==( const type & lhs, const type & rhs)
{
return lhs.map() == rhs.map();
}
friend bool operator!=( const type & lhs, const type & rhs)
{
return ! ( lhs.map() == rhs.map() );
}
}; // DBJ added comment --> eof IntervalMap
/*
DBJ commented out -- reason -- 1. these are much simple if made as friend's to the IntervalMap
2. they both need not have full implementeation as not_eqauls
is ! equals ... see above
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator==(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() == rhs.map();
}
template <typename Key, typename T, typename Comp, typename Allocator>
bool operator!=(
const IntervalMap<Key, T, Comp, Allocator>& lhs,
const IntervalMap<Key, T, Comp, Allocator>& rhs)
{
return lhs.map() != rhs.map();
}
*/
} // DBJ added comment -> eof namespace
// void print(std::ostream& out, const std::map<int, std::optional<std::string>>& map)
// DBH changed to std ostream operator handling the required map type
std::ostream& operator << (std::ostream& out, const std::map<int, std::optional<std::string>>& map)
{
for (auto&& [key, mapped] : map)
{
out << '{' << key << ", ";
if (mapped.has_value()) {
out << *mapped;
} else {
out << "{}";
}
out << "}n";
}
out << 'n';
return out ;
}
// DBJ added
using fub_interval_map_type = fub::IntervalMap<int, string> ;
std::ostream& operator << (std::ostream& out, const fub_interval_map_type & fub_map)
{
return out << fub_map.std_map();
}
int main()
{
cout << boolalpha;
auto map = fub_interval_map_type{} ;
TT(map.insert(0, 10, "foo"));
cout << map << "map.at(0) = " << map.at(0) << 'n';
cout << "map[10].has_value() = " << map[10].has_value() << "nn";
TT(map.insert(3, 7, "bar"));
cout << map << "map.at(5) = " << map.at(5) << "nn";
TT(map.remove(2, 8));
cout << map << "map[5].has_value() = " << map[5].has_value() << 'n';
}
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
answered yesterday
Chef Gladiator
11
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
edited yesterday
Sᴀᴍ Onᴇᴌᴀ
7,98561750
7,98561750
answered yesterday
Chef Gladiator
11
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
Chef Gladiator
11
answered yesterday
Chef Gladiator
11
11
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Chef Gladiator is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
It's better to present proposed improvements in the body of your answer, rather than pointing to external sites without explanation. Please incorporate those suggestions into your answer (keep the link as additional information if you feel it helps, but don't make your answer useless without it). Thanks.
– Toby Speight
yesterday
add a comment |
1
It's better to present proposed improvements in the body of your answer, rather than pointing to external sites without explanation. Please incorporate those suggestions into your answer (keep the link as additional information if you feel it helps, but don't make your answer useless without it). Thanks.
– Toby Speight
yesterday
1
1
It's better to present proposed improvements in the body of your answer, rather than pointing to external sites without explanation. Please incorporate those suggestions into your answer (keep the link as additional information if you feel it helps, but don't make your answer useless without it). Thanks.
– Toby Speight
yesterday
It's better to present proposed improvements in the body of your answer, rather than pointing to external sites without explanation. Please incorporate those suggestions into your answer (keep the link as additional information if you feel it helps, but don't make your answer useless without it). Thanks.
– Toby Speight
yesterday
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f158341%2fan-interval-map-data-structure%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Did you mean
ComparableLessThan...?– CiaPan
Mar 21 '17 at 12:31
Oh yeah. I actually mean
LessThanComparable: en.cppreference.com/w/cpp/concept/LessThanComparable. But what really is meant, is thatCompareis a predicate onKey.– Maikel
Mar 21 '17 at 12:32