STLにおけるmapの使用の詳細

mapの本質
mapは本質的にバランスのとれた二叉木(より正確には赤黒樹)であり、ノードごとにデータを格納し、デフォルトはkeyとvalueがデータpairにパッケージ化され、pairの形でノードに格納される.これにより、pairには任意のデータを格納することができ、pairがサイズを比較しなければならないことを前提とし、もちろん比較関数をカスタマイズすることもできる.mapの3番目のパラメータは、カスタムkeyの比較関数を指定します.
mapの定義

//map   
//       key value   
//        Key         less   less   ——    2   ，   
//                pair     key value     
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;


//less           ()   
//             bool cmp(const T& x, const T& y)         
template <class T> struct less : binary_function <T,T,bool> 
{
  bool operator() (const T& x, const T& y) const {return x<y;}//        
};

mapの特徴

map本質は赤黒樹

である.

各ノードは、1つのデータ

を格納する.

mapのノードは秩序化された

である.
mapの内部データが秩序化されているからこそ、mapの効率的な検索を保証することができ、データが秩序化され、pairは比較可能で、比較関数が必要である.
keyが整数、文字列の場合、比較関数を指定する必要はありませんが、keyが構造体など、独自に定義されたデータ型の場合は、自分で比較関数を作成する必要があります.
カスタムソート関数

#include 
#include 
#include 

using namespace std;
struct DATA {
	int uid;
	string name;
	bool operator()(const DATA& d1, const DATA& d2)
	{
		//     
		return d1.uid > d2.uid;
	}
};

typedef pair<DATA, string> DATA_PAIR;


struct CmpDATA //                
{
	bool operator()(const DATA& d1, const DATA& d2)
	{
		//     
		return d1.uid > d2.uid;
	}
};

int main()
{
	//     ，  map ，          
	map<DATA, string, DATA> mapData;
	//map mapData;

	DATA data1 = {1001, "jim"};
	DATA data2 = {1002, "jack" };
	DATA data3 = {1003, "lucy" };
	DATA data4 = {1004, "james" };

	//    
	mapData.insert(pair<DATA, string>(data1, "China"));
	mapData.insert(pair<DATA, string>(data3, "English"));
	mapData.insert(pair<DATA, string>(data4, "Japan"));
    mapData.insert(pair<DATA, string>(data2, "American"));
	
    //  
	map<DATA, string>::iterator it;
	for (it = mapData.begin();
		it != mapData.end();
		it++)
	{
		printf("uid=%d, name:%s
", it->first.uid, it->first.name.c_str());
	}

    //  
	it = mapData.end();
	it = mapData.find(data2);
	if (it != mapData.end())
	{
		printf("find data2, uid=%d, value=%s
", it->first.uid, it->second.c_str());
	}
	else
	{
		printf("not find data2");
	}
    
    //    
	printf("print data3, value=%s
", mapData[data3].c_str());

	return 0;
}

  ：
uid=1004, name:james
uid=1003, name:lucy
uid=1002, name:jack
uid=1001, name:jim
find data2, uid=1002, value=American
print data3, value=English

関数オブジェクト
定義されたクラスにoperator()オペレータが再ロードされます.オブジェクトは、関数ポインタのように使用できます.

#include 
using namespace std;

class FuncObject
{
public:
	int operator()(int a, int b)
	{
		return a + b;
	}
};

nt main()
{
	FuncObject f;
	int sum = f(10, 20);//    
	printf("sum=%d
", sum);
	return 0;
}

関数オブジェクトは、オブジェクトがステータスを持つことができるため、関数ポインタの代わりに、ポインタよりも柔軟に使用できます.
標準ライブラリは、算術、関係、論理関数オブジェクトクラスのセットを定義します.
例えばless、greater

int main()
{
	less<int> cmp;//    
	printf("result1=%d
", cmp(12,20));

	greater<string> cmpStr;//    
	printf("result2=%d
", cmpStr("C", "B"));

	return 0;
}

  ：
result1=1
result2=1

pairの定義

namespace std {
     template < class T1, class T2 >
     struct pair {
         T1 first;
         T2 second;
         // constructors
                   };
}

       2       first  second

std::make_pair(10, 'D');//   make_pair    pair  
template <class T1,class T2>
 pair<T1,T2> make_pair (T1 x, T2 y)
{
    return ( pair<T1,T2>(x,y) );//  pair  
}

Insert操作
mapのinsertは挿入データを表し、keyがすでに存在する場合は何もせず、keyが存在しない場合はデータを挿入する.

pair<iterator,bool> insert (const value_type& val);

戻り値について:

戻り値はpair

です.

pairのfirstはmapにおいてk値がmapにおける反復器

に等しいことを表す.

pairのsecondはbool値であり、falseはkeyが挿入されていないことを示し、keyがmapに存在していることを示し、trueは

が挿入に成功したことを示している.
以上から,insert操作は,インデックス操作とは異なることが分かる.
下付きの操作で必ずmapが変更されます.例えばmap[k 1]=v 1で、k 1が存在する場合はk 1の値が変更され、k 1が存在しない場合はkeyのキー値ペアが挿入されます.