#ifndef __GBLIBCPP_MAP__ #define __GBLIBCPP_MAP__ #include #include #include #include #include #include #include #include #include namespace std { template , typename Allocator = std::allocator>> class map { public: using key_type = Key; using mapped_type = T; using value_type = std::pair; using size_type = std::size_t; using allocator_type = Allocator; private: class value_compare : public Compare { protected: constexpr value_compare(Compare c): Compare{c} {} friend class map; public: constexpr bool operator()( const value_type& lhs, const value_type& rhs) const { return Compare::operator()(lhs.first, rhs.first); } constexpr bool operator()( const Key& lhs, const value_type& rhs) const { return Compare::operator()(lhs, rhs.first); } constexpr bool operator()( const value_type& lhs, const Key& rhs) const { return Compare::operator()(lhs.first, rhs); } }; using rbtree_type = impl::rbtree; using node_allocator = typename rbtree_type::node_allocator; private: rbtree_type tree; public: using iterator = typename rbtree_type::iterator; using const_iterator = typename rbtree_type::const_iterator; public: __GBLIBCPP_CONSTEXPR iterator end(void) noexcept { return tree.end(); } __GBLIBCPP_CONSTEXPR const_iterator end(void) const noexcept { return tree.cend(); } __GBLIBCPP_CONSTEXPR const_iterator cend(void) const noexcept { return tree.cend(); } __GBLIBCPP_CONSTEXPR iterator begin(void) noexcept { return tree.begin(); } __GBLIBCPP_CONSTEXPR const_iterator begin(void) const noexcept { return tree.cbegin(); } __GBLIBCPP_CONSTEXPR const_iterator cbegin(void) const noexcept { return tree.cbegin(); } explicit __GBLIBCPP_CONSTEXPR map(const Compare& comp, const Allocator& alloc = Allocator()) : tree(comp, alloc) {} explicit __GBLIBCPP_CONSTEXPR map(const Allocator& alloc) : map(Compare(), alloc) {} __GBLIBCPP_CONSTEXPR map() : map(Compare()) {} template __GBLIBCPP_CONSTEXPR map(InputIter first, InputIter last, const Compare& comp = Compare(), const Allocator& alloc = Allocator()) : map(comp, alloc) { insert(first, last); } template __GBLIBCPP_CONSTEXPR map(InputIter first, InputIter last, const Allocator& alloc = Allocator()) : map(first, last, Compare(), alloc) {} __GBLIBCPP_CONSTEXPR map(const map& other) : tree(other.tree) {} __GBLIBCPP_CONSTEXPR map(const map& other, const Allocator& alloc) : tree(other.tree, alloc) { } __GBLIBCPP_CONSTEXPR map(map&& other) : tree(std::move(other.tree)) {} __GBLIBCPP_CONSTEXPR map(map&& other, const Allocator& alloc) : tree(std::move(other.tree), alloc) {} __GBLIBCPP_CONSTEXPR map(std::initializer_list init, const Compare& comp = Compare(), const Allocator& alloc = Allocator()) : map(comp, alloc) { insert(init.begin(), init.end()); } __GBLIBCPP_CONSTEXPR map(std::initializer_list init, const Allocator& alloc) : map(init, Compare(), alloc) {} __GBLIBCPP_CONSTEXPR ~map() { clear(); } __GBLIBCPP_CONSTEXPR map& operator=(const map& other) = default; __GBLIBCPP_CONSTEXPR map& operator=(map&& other) = default; __GBLIBCPP_CONSTEXPR map& operator=(std::initializer_list ilist) { clear(); insert(ilist.begin(), ilist.end()); return *this; } __GBLIBCPP_CONSTEXPR iterator find(const Key& key) { return tree.find(key); } __GBLIBCPP_CONSTEXPR const_iterator find(const Key& key) const { return tree.find(key); } // if the container does not have an element with // the specified key, it should throw an exception // TODO: exceptions __GBLIBCPP_CONSTEXPR T& at(const Key& key) { return find(key)->second; } // if the container does not have an element with // the specified key, it should throw an exception // TODO: exceptions __GBLIBCPP_CONSTEXPR const T& at(const Key& key) const { return find(key)->second; } __GBLIBCPP_CONSTEXPR std::pair insert(const value_type& value) { return tree.insert(value); } __GBLIBCPP_CONSTEXPR std::pair insert(value_type&& value) { return tree.insert(std::move(value)); } template __GBLIBCPP_CONSTEXPR std::enable_if_t, std::pair> insert(Pair&& p) { return emplace(std::forward(p)); } template __GBLIBCPP_CONSTEXPR void insert(InputIter first, InputIter last) { for ( ; first != last; ++first) insert(*first); } template __GBLIBCPP_CONSTEXPR std::pair emplace(Args&&... args) { return tree.emplace(std::forward(args)...); } template __GBLIBCPP_CONSTEXPR std::pair try_emplace(const Key& key, Args&&... args) { auto iter = find(key); if (iter) return { iter, false }; return emplace( std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(std::forward(args)...)); } template __GBLIBCPP_CONSTEXPR std::pair try_emplace(Key&& key, Args&&... args) { auto iter = find(key); if (iter) return { iter, false }; return emplace( std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::forward_as_tuple(std::forward(args)...)); } __GBLIBCPP_CONSTEXPR T& operator[](const Key& key) { return try_emplace(key).first->second; } __GBLIBCPP_CONSTEXPR T& operator[](Key&& key) { return try_emplace(std::move(key)).first->second; } __GBLIBCPP_CONSTEXPR iterator erase(iterator pos) noexcept { return tree.erase(pos); } __GBLIBCPP_CONSTEXPR iterator erase(const_iterator pos) noexcept { return tree.erase(pos); } __GBLIBCPP_CONSTEXPR iterator erase(const_iterator first, const_iterator last) noexcept { while (first != last) first = erase(first); return first; } __GBLIBCPP_CONSTEXPR size_type erase(const Key& key) { auto iter = find(key); if (!iter) return 0; erase(iter); return 1; } __GBLIBCPP_CONSTEXPR void clear() noexcept { tree.destroy(); } __GBLIBCPP_CONSTEXPR bool empty() const noexcept { return tree.empty(); } __GBLIBCPP_CONSTEXPR size_type size() const noexcept { return tree.size(); } __GBLIBCPP_CONSTEXPR void swap(map& other) { tree.swap(other.tree); } __GBLIBCPP_CONSTEXPR size_type count(const Key& key) const { return find(key) ? 1 : 0; } __GBLIBCPP_CONSTEXPR bool contains(const Key& key) const { return count(key) != 0; } __GBLIBCPP_CONSTEXPR iterator upper_bound(const Key& key) { return tree.upper_bound(key); } __GBLIBCPP_CONSTEXPR const_iterator upper_bound(const Key& key) const { return tree.upper_bound(key); } __GBLIBCPP_CONSTEXPR iterator lower_bound(const Key& key) { return tree.lower_bound(key); } __GBLIBCPP_CONSTEXPR const_iterator lower_bound(const Key& key) const { return tree.lower_bound(key); } }; template void swap(std::map& lhs, std::map& rhs) { lhs.swap(rhs); } template typename std::map::size_type erase_if(std::map& c, Pred pred) { auto iter = c.begin(); typename std::map::size_type count = 0; while (iter != c.end()) { if (pred(*iter)) { iter = c.erase(iter); ++count; } else ++iter; } return count; } template , typename Allocator = std::allocator>> map(std::initializer_list>, Compare = Compare(), Allocator = Allocator()) -> map; template map(std::initializer_list>, Allocator) -> map, Allocator>; } // namespace std #endif