Mapコンテナ学習

データ構造
Mapはマッピングされており、すべての要素がpairで秩序正しく、実値(value)とキーワード(key)を持っている.MapはRB-treeの下位メカニズムで、実はバランス二叉検索ツリーである.
map内の要素の組織秩序性を保護するため、C++はユーザーがmap要素のkey値を勝手に変更することを許さず、valueを変更するしかない.
pairの定義:

template 
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first; //  public
    T2 second;

    pair() : first(T1()), second(T2()) {}
    pair(const T1 &a, const T2 &b) : first(a), second(b) {}
};

メンバー定義

//        
template , class Alloc = alloc>
class map
{
  public:
    // typedefs:

     typedef Key key_type;                  //     
     typedef T data_type;                   //   ，    
    typedef T mapped_type;                 //
    typedef pair value_type; //     （  /  ）
    typedef Compare key_compare;           //        

  private:
    // map  （  pair）        TB-tree     .
    //   RB-tree ，  key    ，    data    。
    typedef rb_tree, key_compare, Alloc>
        rep_type;
    rep_type t; //            

コンストラクタ

  map() : t(Compare()) {}  
  explicit map(const Compare& comp) : t(comp) {}  //explicit            
  
  //STL
  template   
  map(InputIterator first, InputIterator last) : t(Compare())  
  template   
  map(InputIterator first, InputIterator last, const Compare& comp)  : t(comp)
  
  //C++
  map(const value_type* first, const value_type* last)  : t(Compare())
  map(const value_type* first, const value_type* last, const Compare& comp)  : t(comp)

  map(const_iterator first, const_iterator last)  : t(Compare())  
  map(const_iterator first, const_iterator last, const Compare& comp)  : t(comp)
  

  //      
  map(const map& x) : t(x.t) {}  
  map& operator=(const map& x)  

インタフェース

    key_compare key_comp() const { return t.key_comp(); }
    value_compare value_comp() const { return value_compare(t.key_comp()); }

順方向反復:

 iterator begin()

 const_iterator begin() const

 iterator end()

 const_iteratorend() const

逆反復:

   reverse_iterator rbegin()

   const_reverse_iterator rbegin() const

   reverse_iterator rend()

   const_reverse_iterator rend() const

数:

   size_type size() const

   size_type max_size() const

 

    //  []，      

T &operator[](const key_type &k)

Swap:

    voidswap(map &x){ t.swap(x.t);}

挿入/削除

   //    

    pair insert(const value_type &x) { return t.insert_unique(x); }

    iterator insert(iterator position, const value_type &x)
    
 

    //    

    template 

    voidinsert(InputIterator first, InputIterator last)

 

    voidinsert(const value_type *first, const value_type *last)

    voidinsert(const_iterator first, const_iterator last)

 

    voiderase(iterator position)

    size_type erase(const key_type &x) { return t.erase(x); }

    voiderase(iterator first, iterator last){ t.erase(first, last);}

 

    void clear() { t.clear(); }

操作
検索:

   iterator find(const key_type &x) { return t.find(x); }

   const_iterator find(const key_type &x) const { return t.find(x); }

統計キー値xの個数:

size_type count(const key_type &x) const { return t.count(x); } 

区間を求めます://[x,x)区間

const_iteratorlower_bound(const key_type &x)

const_iteratorupper_bound(const key_type &x)

const_iteratorequal_range(const key_type &x)

比較:

   friendbooloperator==__STL_NULL_TMPL_ARGS(const map &,const map&);

   friendbooloperator<__stl_null_tmpl_args map=""/>