美文网首页
LinkedHashMap

LinkedHashMap

作者: help_youself | 来源:发表于2019-04-30 15:20 被阅读0次

linked_hash_map.h

#ifndef LINKED_HASH_MAP_H_
#define LINKED_HASH_MAP_H_
#include <unordered_map>
#include <list>
#include "basic_macro.h"
#include "logging.h"
// This holds a list of pair<Key, Value> items.  This list is what gets
// traversed, and it's iterators from this list that we return from
// begin/end/find.
//
// We also keep a map<Key, list::iterator> for find.  Since std::list is a
// doubly-linked list, the iterators should remain stable.
template <class Key, class Value, class Hash = std::hash<Key>>
class linked_hash_map
{
  private:
    typedef std::list<std::pair<Key, Value>> ListType;
    typedef std::unordered_map<Key, typename ListType::iterator, Hash> MapType;

  public:
    typedef typename ListType::iterator iterator;
    typedef typename ListType::reverse_iterator reverse_iterator;
    typedef typename ListType::const_iterator const_iterator;
    typedef typename ListType::const_reverse_iterator const_reverse_iterator;
    typedef typename MapType::key_type key_type;
    typedef typename ListType::value_type value_type;
    typedef typename ListType::size_type size_type;

    linked_hash_map() = default;
    explicit linked_hash_map(size_type bucket_count) : map_(bucket_count) {}

    linked_hash_map(linked_hash_map &&other) = default;
    linked_hash_map &operator=(linked_hash_map &&other) = default;

    // Returns an iterator to the first (insertion-ordered) element.  Like a map,
    // this can be dereferenced to a pair<Key, Value>.
    iterator begin()
    {
        return list_.begin();
    }
    const_iterator begin() const
    {
        return list_.begin();
    }

    // Returns an iterator beyond the last element.
    iterator end()
    {
        return list_.end();
    }
    const_iterator end() const
    {
        return list_.end();
    }

    // Returns an iterator to the last (insertion-ordered) element.  Like a map,
    // this can be dereferenced to a pair<Key, Value>.
    reverse_iterator rbegin()
    {
        return list_.rbegin();
    }
    const_reverse_iterator rbegin() const
    {
        return list_.rbegin();
    }

    // Returns an iterator beyond the first element.
    reverse_iterator rend()
    {
        return list_.rend();
    }
    const_reverse_iterator rend() const
    {
        return list_.rend();
    }

    // Front and back accessors common to many stl containers.

    // Returns the earliest-inserted element
    const value_type &front() const
    {
        return list_.front();
    }

    // Returns the earliest-inserted element.
    value_type &front()
    {
        return list_.front();
    }

    // Returns the most-recently-inserted element.
    const value_type &back() const
    {
        return list_.back();
    }

    // Returns the most-recently-inserted element.
    value_type &back()
    {
        return list_.back();
    }

    // Clears the map of all values.
    void clear()
    {
        map_.clear();
        list_.clear();
    }

    // Returns true iff the map is empty.
    bool empty() const
    {
        return list_.empty();
    }

    // Removes the first element from the list.
    void pop_front() { erase(begin()); }

    // Erases values with the provided key.  Returns the number of elements
    // erased.  In this implementation, this will be 0 or 1.
    size_type erase(const Key &key)
    {
        typename MapType::iterator found = map_.find(key);
        if (found == map_.end())
            return 0;

        list_.erase(found->second);
        map_.erase(found);

        return 1;
    }

    // Erases the item that 'position' points to. Returns an iterator that points
    // to the item that comes immediately after the deleted item in the list, or
    // end().
    // If the provided iterator is invalid or there is inconsistency between the
    // map and list, a CHECK() error will occur.
    iterator erase(iterator position)
    {
        typename MapType::iterator found = map_.find(position->first);
        if(found->second != position){
            DLOG(FATAL)<<"Inconsisent iterator for map and list, or the iterator is invalid.";
        }

        map_.erase(found);
        return list_.erase(position);
    }

    // Erases all the items in the range [first, last).  Returns an iterator that
    // points to the item that comes immediately after the last deleted item in
    // the list, or end().
    iterator erase(iterator first, iterator last)
    {
        while (first != last && first != end())
        {
            first = erase(first);
        }
        return first;
    }

    // Finds the element with the given key.  Returns an iterator to the
    // value found, or to end() if the value was not found.  Like a map, this
    // iterator points to a pair<Key, Value>.
    iterator find(const Key &key)
    {
        typename MapType::iterator found = map_.find(key);
        if (found == map_.end())
        {
            return end();
        }
        return found->second;
    }

    const_iterator find(const Key &key) const
    {
        typename MapType::const_iterator found = map_.find(key);
        if (found == map_.end())
        {
            return end();
        }
        return found->second;
    }

    // Returns the bounds of a range that includes all the elements in the
    // container with a key that compares equal to x.
    std::pair<iterator, iterator> equal_range(const key_type &key)
    {
        std::pair<typename MapType::iterator, typename MapType::iterator> eq_range =
            map_.equal_range(key);

        return std::make_pair(eq_range.first->second, eq_range.second->second);
    }

    std::pair<const_iterator, const_iterator> equal_range(
        const key_type &key) const
    {
        std::pair<typename MapType::const_iterator,
                  typename MapType::const_iterator>
            eq_range =
                map_.equal_range(key);
        const const_iterator &start_iter = eq_range.first != map_.end() ? eq_range.first->second : end();
        const const_iterator &end_iter = eq_range.second != map_.end() ? eq_range.second->second : end();

        return std::make_pair(start_iter, end_iter);
    }

    // Returns the value mapped to key, or an inserted iterator to that position
    // in the map.
    Value &operator[](const key_type &key)
    {
        return (*((this->insert(std::make_pair(key, Value()))).first)).second;
    }

    // Inserts an element into the map
    std::pair<iterator, bool> insert(const std::pair<Key, Value> &pair)
    {
        // First make sure the map doesn't have a key with this value.  If it does,
        // return a pair with an iterator to it, and false indicating that we
        // didn't insert anything.
        typename MapType::iterator found = map_.find(pair.first);
        if (found != map_.end())
            return std::make_pair(found->second, false);

        // Otherwise, insert into the list first.
        list_.push_back(pair);

        // Obtain an iterator to the newly added element.  We do -- instead of -
        // since list::iterator doesn't implement operator-().
        typename ListType::iterator last = list_.end();
        --last;

        map_.insert(std::make_pair(pair.first, last));

        return std::make_pair(last, true);
    }

    size_type size() const
    {
        return list_.size();
    }

    template <typename... Args>
    std::pair<iterator, bool> emplace(Args &&... args)
    {
        ListType node_donor;
        auto node_pos =
            node_donor.emplace(node_donor.end(), std::forward<Args>(args)...);
        const auto &k = node_pos->first;
        auto ins = map_.insert({k, node_pos});
        if (!ins.second)
            return {ins.first->second, false};
        list_.splice(list_.end(), node_donor, node_pos);
        return {ins.first->second, true};
    }

    void swap(linked_hash_map &other)
    {
        map_.swap(other.map_);
        list_.swap(other.list_);
    }

  private:
    // The map component, used for speedy lookups
    MapType map_;

    // The list component, used for maintaining insertion order
    ListType list_;

    // |map_| contains iterators to |list_|, therefore a default copy constructor
    // or copy assignment operator would result in an inconsistent state.
    DISALLOW_COPY_AND_ASSIGN(linked_hash_map);
};
#endif

[1] 图解LinkedHashMap原理

相关文章

网友评论

      本文标题:LinkedHashMap

      本文链接:https://www.haomeiwen.com/subject/ncdvnqtx.html