hashed list with O(1) push_back()/push_front()/remove() operations. answers gist.github.com/2216546

hashed_list.h

#include <assert.h>
#include <list>
#include <boost/unordered_map.hpp>
#include <boost/noncopyable.hpp>

template<typename T>
class HashedList : boost::noncopyable
{
  typedef typename std::list<T>::iterator ListIterator;
  typedef typename std::list<T>::reverse_iterator ReverseListIterator;
  typedef typename boost::unordered_multimap<T, ListIterator>::iterator MapIterator;
 public:

  class iterator
  {
   public:
    iterator(const ListIterator& it)
      : it_(it),
        reversed_(false)
    {
    }

    iterator(const ReverseListIterator& rit)
      : rit_(rit),
        reversed_(true)
    {
    }

    iterator& operator++()
    {
      if (!reversed_)
        ++it_;
      else
        ++rit_;
      return *this;
    }

    // iterator operator++(int)

    T operator*()
    {
      if (!reversed_)
        return *it_;
      else
        return *rit_;
    }

    bool operator==(const iterator& rhs) const
    {
      if (reversed_ == rhs.reversed_)
      {
        if (!reversed_)
          return it_ == rhs.it_;
        else
          return rit_ == rhs.rit_;
      }
      else
      {
        return false;
      }
    }

    bool operator!=(const iterator& rhs) const
    {
      return !operator==(rhs);
    }

   private:
    ListIterator it_;
    ReverseListIterator rit_;
    bool reversed_;
  };

  // class const_iterator;

  HashedList()
    : reversed_(false)
  {
  }

  void push_back(const T& x)
  {
    if (!reversed_)
    {
      list_.push_back(x);
      ListIterator last = list_.end();
      --last;
      loc_.insert(make_pair(x, last));
    }
    else
    {
      list_.push_front(x);
      loc_.insert(make_pair(x, list_.begin()));
    }
    sanity_check();
  }

  void push_front(const T& x)
  {
    if (!reversed_)
    {
      list_.push_front(x);
      loc_.insert(make_pair(x, list_.begin()));
    }
    else
    {
      list_.push_back(x);
      ListIterator last = list_.end();
      --last;
      loc_.insert(make_pair(x, last));
    }
    sanity_check();
  }

  void remove(const T& x)
  {
    MapIterator it = loc_.find(x);
    if (it != loc_.end())
    {
      list_.erase(it->second);
      loc_.erase(it);
    }
    sanity_check();
  }

  void reverse()
  {
    reversed_ = !reversed_;
  }

  iterator begin()
  {
    if (!reversed_)
      return iterator(list_.begin());
    else
      return iterator(list_.rbegin());
  }
  // const_iterator begin() const

  iterator end()
  {
    if (!reversed_)
      return iterator(list_.end());
    else
      return iterator(list_.rend());
  }
  // const_iterator end() const

 private:

  void sanity_check()
  {
    assert(list_.size() == loc_.size());
  }

  std::list<T> list_;
  boost::unordered_multimap<T, ListIterator> loc_;
  bool reversed_;
};

main.cc

#include "hashed_list.h"
#include <iostream>
using namespace std;

template<typename T>
void print(HashedList<T>& list)
{
  for (typename HashedList<T>::iterator it = list.begin();
       it != list.end();
       ++it)
  {
    if (it != list.begin())
    {
      cout << ", ";
    }
    cout << *it;
  }
  cout << endl;
}

int main()
{
  {
    HashedList<int> il;
    il.push_back(1);
    il.push_back(2);
    il.push_back(3);
    print(il);
    il.reverse();
    print(il);
    il.remove(1);
    print(il);
    il.remove(3);
    print(il);
    il.push_front(4);
    print(il);
  }
  {
    HashedList<int> il;
    il.push_back(1);
    il.push_back(2);
    il.push_back(1);
    il.push_back(3);
    il.push_back(1);
    print(il);
    il.remove(1);
    print(il);
    il.remove(1);
    print(il);
    il.reverse();
    print(il);
    il.push_front(4);
    print(il);
  }
}

不能用第三方库哦。

那就换成 std::unordered_multimap 呗，一样的东西。

好像是google c++的编码风格.