___
■ 共通
    コンテナクラスも 参照渡し可能 ( object なので当然 )
     void testFunc( vector< int> &list )
       ...;
     }
    関数ポインタを渡す際は static でない mem func は不可能 
    理由は obj がない状態では 関数のアドレスが決まらないから

    Container の memory を確保するために, new が call される.
    それを選択させるのが, Allocator
    何か処理をさせる場合は, ctor, method 経由で渡すことが大事


___
■ コンテナクラス

  DESC
    他のオブジェクトの集まり( コレクション )のクラス
    List, Set, Dictionary

___
■ コンテナにオブジェクトをいれる

    コンテナにいれる物は オブジェクトか、そのポインタのどちらかになる。
     値のコンテナ
     ポインタのコンテナ


    また、中身をそろえる、そろえないで２種類できる。

    Java のように共通の基底クラス Object から派生したクラスをすべて入れることもできるが
    有効なのは、特定の基底クラスから実装した派生クラスのみをいれること。

  WARNING
    ポインタをコンテナにいれる場合は
    複数のポインタからインスタンスが参照されることになる。

    そのため、delete した後のインスタンスを参照する危険性がある。

    対策として SharedPointer などが使える。
    または注意深く、オブジェクトを管理する。

    REFERENCE  SharedPointer
    



___
■ vector

  SYNTAX
    void resize( size_type _Newsize )

      vector< int> b(7); // constructor の引数として、配列の要素数をとる
      vector< int> b(7, 5) // 5 で初期化


___
■ 追加

  SYNTAX
    iterator push_back( iterator ) 



___
■ 削除

  SYNTAX
    iterator erase( iterator ) 

  DESC
    iterator がさす要素を削除 && 配列を自動で詰めなおす && 次の iterator を返す

    vector< int> a;
    
    a.push_back(1);
    a.push_back(2);

    vector< int>::iterator it = a.begin();

    // 先頭の要素を削除    
    a.erase( it );

    // 先頭から２番目を削除
    it++;
    a.erase( it );






___
■ サイズ

  SYNTAX
    void resize( size_type nr )

  DESC
    要素数を変更する。
      




___
■ 挿入

  SYNTAX
    iterator insert( iterator, const T& ) 
      : iterator がさす "要素の前" に挿入 && 挿入した要素を指す iterator をかえす. 

      [0, 1, 2, 3, 4, 5, 6, 7]
       ^
       |
            itr
      
      itr = v.insert( itr, 8 );
      [8, 0, 1, 2, 3, 4, 5, 6, 7]
       ^
       |


___
■ 参照

  SYNTAX 
    reference       operator [](size_type n);
    const_reference operator [](size_type n) const;
    reference       at(size_type n);
    const_reference at(size_type n) const;

    // コンテナの i 番目の要素を v という別名で参照. 
    int &i = a[i];
    // 実は次のことと同じ. ( 参照を取得するから代入可能.  )
    i[0] = 10;



    コンテナクラスの代入 OK らしい( 要素が正しく operator=() の定義が必要 )

    erase() をしても vector::end() は不変


      
   // WARNING:  itr ++ 扱い
   for ( ; itr != itrend; ) {
     if ( itr->flag ) {
       itr = pnt.erase( itr );
     } else {
       itr ++;
     }
   }

    {
      vector<  vector< int> > foo;
      
      vector< int> bar;
      bar.push_back(1);
      bar.push_back(2);
      bar.push_back(3);

      vector< int> a;
      a.push_back(11);
      a.push_back(12);
      a.push_back(13);
      
      a.push_back(bar);
      a.push_back(a);

      printf(foo[1][2]);  // = 13
    }     



___
■ multimap

  POINT
    lower_bound();
  Desc
    指定した値 [ 以.上 ] の要素が最初に現れる位置を返す, 
    count();
    // x をキーに持つ要素の数を返す。
    size_type count(const Key &x) const;

___
■ map

    キーと値の対応表を表現するときに使う。

  POINT
    検索 O( log N )なので、vector, list と比較すると高速に検索できる。


      連想 container 
      map<  key, val >

    key で sort されて格納( name でも sort )      
    [KEY] = VAL; // xxx.ini 

  POINT
    listXXX.insert( make_pair( oneObj, twoObj ) );

  WARNING
    iterator を移動しながらの 削除はできない

    map< string, int> l;
    l.insert( make_pair("a", 10) );
    l.insert( make_pair("b", 11) );

    for( map< string, int>::iterator i=0; i!=l.end(); i++ ){
      l.erase( i );     // ERROR
    } 


___
■ 挿入

    tbl.insert( make_pair(key,val) ); 
    tbl[ key ] = val;



___
■ 削除 

    // iterator の指す要素を削除して次の要素をさす iterator を返す
    iterator erase( iterataor i );
    size_t erase( key );


    // key を指定して削除
    map< string, int> m;
    unsigned int nr = m.erase("foo");
    nr = 0; ならば消せていない


___
■ 検索 参照

       Tbl::iterator i;
      i = tbl.find( 2 );



    T &map::opeartor []( const Key & )
  DESC 
    キーに対応する要素を参照
    左辺値になる場合に、同じ値を持つ要素がないときは k をキーに持つ右辺値を挿入

    // val に対して, DefaultCtor が起動するらしい. 
    val = tbl[ key ];

    typedef map<  int , string > List;
    List tbl;

    tbl[0] = "aaa";
    tbl[1] = "bbb";
    tbl[0] = "ccc";
  
    List::iterator i = tbl.begin();
    for( ;i != tbl.end(); i++ ){
      printf( i->second.c_str() );
    } 
  
    // "bbb"
    printf( tbl[1].c_str() );

    // ""
    printf( tbl[3].c_str() );



___
■ list

    STL のリストは双方向リスト。

  POINT
    追加、削除は O(1)
    参照は O(N)

    追加、削除は早いので、頻繁に追加、削除をする場合に使う。
    ただしアクセスは配列のように O(1) でアクセスできない。

    



  DESC
    iterator insert( iterator, const T& ) : vector< T> 同様.
    operator [] は不可

___
■ 追加

    list<  int > l;

    l.push_back( 1 );
    l.push_front( 2 );



    rbegin()


    sort( bool func(T &, T &) ); 

___
■ 削除

  SYNTAX
    void pop_back();
    void pop_front();

    iterator erase( iterator );


    リストから削除するときは, イテレータの指す場所から削除する。
    erase() は削除した次の要素を指すイテレータを返す。
    list<  int > l;

    l.push_back( 1 );
    l.push_front( 2 );

    list<  int >::iterator  i = l.begin();

    for ( ; i != l.end(); i++ ) {
      if ( *i == 2 ) {
        l.erase( i );
        break;
      }
    }


  WARNING
    erase しながら イテレートをする時は erase で返す iterator を受け取ること。
    削除すみのリスト要素に対して ++ をすることになるため。
    for ( ; i != l.end();  ) {

      printf( "%d\n", *i );

      if ( *i == 2 ) {
        i = l.erase( i );
      }
      else {
        i++;
      }
    }


    pop_front(), pop_back() は要素を返さずに削除するだけ。
    list<  int > l;

    l.pop_back();
    l.pop_front();


    // 値がほしければ 参照のメソッドをつかってコピーをとる。
    int i = l.front();
    l.pop_front();



___
■ 参照

  SYNTAX
    T &front()
    const T &front() const

    T &back()
    const T &back() const

  DESC
    リスト内の要素の参照をかえす。

    list<  int > l;

    l.push_back( 1 );
    l.push_front( 2 );
    
    // 2
    const int &ci = l.front();

    int &i = l.front();
    i = 3;

    {
      // 3
      const int &ci = l.front();
      // 1
      l.back();
    }    






___
■ ソート

    // a <  b <  c ... //小さい順 
    bool cmp( int &a, int &b ){ return a <  b };
    list< int> li;
    li.sort( cmp );



    pop_front | pop_back ; 要素がなくなる  ( list の中身がかわるよ )
    remove( val ) : val と一致するすべての要素を削除. ( ptr OK  )

    Predicator( Yes/No 関数. ) を利用して, loop する. 
   bool update_and_delete(Object* p) 
   {
     p->update();
     if( p->isDelete() ) {
       delete(p);
       return true;
     }
     return false;
   }

  do {
    // Predicator を渡すことで, list を前後にわける. 
    // [1][1][1]....[0][0]...[0]
    //               . ここを返す. 
    // そして erase する. 
    objs.erase( remove_if( objs.begin(), objs.end(), update_and_delete), objs.end() );

  } while( !objs.empty() ); // リストが空っぽになったら終了

___
■ set

  POINT
    データの重複を許さない集合のこと。
    重複をしないリストをつくるときに便利。
    
    追加, 削除 O(logN)
    検索 O(logN)


    重複をしない単語リストをつくる
    typedef  set<  String >  StringSet;

    StringSet a;

    string word;

    // 単語を登録する
    while ( cin >> word ) {
      a.insert( word );
    }




  
___
■ コンテナへの操作

    #include< algorithm>
  

___
■ std::find


  SYNTAX
    find(
          first,        // 検索開始位置のイテレータ
          end,          // 終了位置のイテレータ
          T &value      // 検索する値
    )

  DESC
    value と同一の値を指す iterator をかえす
    end を指すイテレータを返す。



   int i = 0;

   vector<  int >::iterator itr = std::find( 
        tbl.begin(),
        tbl.end(),     // 終了
        i           // 探す要素
        );


___
■ std::count

  SYNTAX
    find(
          first,        // 検索開始位置のイテレータ
          end,          // 終了位置のイテレータ
          T &value,     // 検索する値
          result
    )

___
■ std::remove

  SYNTAX
    find(
          first,        // 検索開始位置のイテレータ
          end,          // 終了位置のイテレータ
          T &value      // 検索する値
    )
    
  DESC
    指定した範囲で value と一致する値を削除する

    vector<  int > v( 10 );
    std::fill( v.begin(), v.end(), 7 );

    std::remove( v.begin(), v.end(), 7 );
    

  


___
■ std::fill

  SYNTAX
    find(
          first,         // 検索開始位置のイテレータ
          end,           // 終了位置のイテレータ
          const T &value
    )
  
    vector<  int > v( 10 );
    std::fill( v.begin(), v.end(), 7 );


___
■ std::replace

  SYNTAX
    replace(
          first,         // 検索開始位置のイテレータ
          end,           // 終了位置のイテレータ
          const T &src   // 
          const T &dst   // 
    )
  
  DESC
    first から end の範囲で src の値を dst に変換する。


    vector<  int > v( 10 );
    std::fill( v.begin(), v.end(), 7 );

    std::replace( v.begin(), v.end(), 7, 10 );





___
■ std::unique

  SYNTAX
    find(
          first,        // 検索開始位置のイテレータ
          end          // 終了位置のイテレータ
    )
  
  DESC
    first, end までの区間で重複を取り除く。

  WARNING 
    unique を実行するには、コンテナの要素は sort されている必要がある。

    vector<  int > v( 10 );
    std::fill( v.begin(), v.end(), 7 );

    // sort してから
    std::sort( v.begin(), v.end() );

    // 重複をとる
    std::unique( v.begin(), v.end() );


___
■ std::sort

  SYNTAX
    find(
          first,        // 検索開始位置のイテレータ
          end          // 終了位置のイテレータ
    )

  DESC
    first, end までの区間をソートする。
    中身はクイックソート。

  REFERENCE  qsort


    std::random_shuffle( v.begin(), v.end() );

    std::sort( v.begin(), v.end() );

    for( int i=0; i< v.size(); i++ ){
      cout < <  v[i] < <  endl;
    } 


  POINT
    自作のクラスもソートできる。
    この場合は <  演算子のインターフェイスを持つことが条件になる。
    昇順( ちいさい順 )にならべるには、 A <  B ときたら A が小さいときに true を返すようにする
    class vec2 
    {
     public :
      bool operator <  ( const vec2 &rhs ) {
        bool ret = length() <  rhs.length();
        return ret;
      }

      float length() const {
        return x*x + y*y;
      }

      vec2( float _x, float _y ) : x(_x), y(_y){}

      void toString() { 
        printf("%f %f\n", x, y ); 
      }

     private:
      float x, y;
    };

    


     vec2 v0( 1, 2 );
     vec2 v1( 2, 2 );
     vec2 v2( 0, 2 );

     std::vector< vec2> a;
     a.push_back( v0 );
     a.push_back( v1 );
     a.push_back( v2 );

     std::sort( a.begin(), a.end() );

     for( int i=0; i< a.size(); i++ ){
       a[i].toString();
     } 


___
■ std::binary_search

  SYNTAX
    bool binary_search(
                  first,          // 検索開始位置のイテレータ
                  end,            // 終了位置のイテレータ
                  const T &value  // 検索する値
    )

  DESC
    first, end までの区間で binary_search をして、その結果を返す。

  REFERENCE  bsearch

    set<  int > a;

    bool ret = binary_search( a.begin(), a.end(), 1 );




___
■ random_shuffle

    指定した配列をランダムに並びかえる。
    const int N = 1000;
    int i = 0;

    int *a = new int[ N ];

    for( i=0; i< N; i++ ){
      a[i] = 0;
    }  
    
    std::random_shuffle( a, a + N );