Valuelist Application Practice 2: Implement Multi-key MAP

Valuelist Application Practice 2: Implement Multi-key MAP

1.1 demand

In the application, you need to implement a multi-key MAP table, you want to reach the following use:

// key value is three int types, depending on the situation, the quantity and types should be changed, the saved value is String

Map multiKeymap;

MultiKeyMap mymap;

// Insert multiple values

MyMap.Add (1, 1, 2, "112");

MyMap.Add (1, 1, 3, "113");

MyMap.Add (1, 2, 1, "121");

MyMap.Add (1, 2, 2, "122");

MyMap.Add (1, 3, 1, "131");

// Find a value:

String value = mymap.find (1, 1, 2);

/ / You can find multiple matching values ​​based on the part key value

Map resultMAP;

MyMap.Find (1, 2, resultmap);

The final resultMAP should include <1, "121"> and <2, "122"> two values.

Here is the key problem is that the number of key values ​​is changed. The back is only a comparative algorithm based on the partial value. With the experience of Valuelist, the first feel is to implement it with Valuelist.

1.2 implementation technology

1.2.1 First implementing Valuelist's key value MAP

Move out the definition of the existing Valuelist:

Class null_type {};

Template Class Valuelist

{

PUBLIC:

TYPEDEF T1 First_Value_Type;

TypedEf T2 SECOND_VALUE_TYPE;

T1 m_VAL1;

T2 m_VAL2;

Valuelist (Const T1 & Val1, Const T2 & Val2): M_VAL1 (VAL1), M_VAL2 (VAL2) {}

}

Because we need to clear the type of valuelist to construct a map, you need to define macros, which makes it easy for users to define, as follows:

#define type_vlist_1 (t) Valuelist

#define type_vlist_2 (t1, t2) Valuelist

#define type_vlist_3 (t1, t2, t3) Valuelist

...

It is also defined to generate the convenience function of the Valuelist, where the REFHOLDER is used.

Template

Inline Valuelist MakevaluelIST (Const T1 & Val1, Const T2 & VAL2)

{

Return Valuelist (VAL1, VAL2);

}

Similarly define the macro to generate Valuelist:

#define vlist_1 (x) makevaluelist (x, null_type ()))

#define VLIST_2 (x1, x2) makevaluelist (x1, vlist_1 (x2))

#define VLIST_3 (X1, X2, X3) Makevaluelist (x1, Vlist_2 (x2, x3))

...

Because Valuellist is used as a key value, we need to define a comparison algorithm between Valuelist. As the internal sorting of Map, we implements the following comparison function:

Template

Bool Operator <(Const VauleList & Key1, Const VauleList & Key2) {

// First, the first element is compared, if they don't wait, then the final comparison result is the same as the size of the two elements.

IF (key1.m_val1! = key2.m_val1) Return Key1.m_VAL1

// If the current element is equal, recursive comparison next element

Return Key1.m_val2

}

Because Valuelist is compared in null_type, the above template function will eventually perform NULL_TYPE comparison, so we need the following comparison function:

BOOL Operator <(null_type, null_type)

{

// The two NULL_TYPE should be equal, so there is no condition to return false

Return False;

}

With the above definition, we can realize the MAP of any number of key values, see the example below:

Typedef std :: map > multikeymap;

MultiKeyMap mymap;

MYMAP [VLIST_3 (1, 1, 1)] = "111";

MYMAP [VLIST_3 (1, 1, 2)] = "112";

MYMAP [VLIST_3 (1, 2, 1)] = "121";

MYMAP [VLIST_3 (1, 2, 2)] = "122";

MYMAP [VLIST_3 (1, 3, 1)] = "131;

/ / The above directly uses VLIST_3 to define the key value, only in this example, because this macro generates Valuelist, the type of constant constant is int, and the return type of VLIST_3 is Valuelist >>, just the type of Key, the type of Key. More general methods see the following description.

Std :: cout << mymap [VLIST_3 (1, 2, 2)] << std :: end1;

1.2.2 Consider the search support for partial value

Map already has Lower_Bound, Upper_Bound, Equal_Range and other methods to support the range of queries, it can be used directly. There is a problem here, and the lookups of these methods are completed by the size comparative algorithm defined by the third template parameter parameter of MAP. And the input parameters are std :: map :: key_type is the first template parameter, according to these two points, we need:

1. Generate a full std :: map :: key_type type according to the input part key value. Requires us to support the default constructor to replace the key value that the user is not entered, how can we distinguish when we compare? One key value is an external input or default constructed? Using the default function of each type is unable to do, the only way is that each Key value needs to have an identification to indicate that its value is an external incoming It is also a default, which is simple to make a layer of packages for each Key value.

2. We need to modify the definition of the previous key value comparison function, support the comparison of the different number of key values. We need to clarify the key values ​​that are not entered in the outside and other keys, who is more small? According to the needs of users, It should be no size, that is, if the user does not enter any key value, it is equal to any internal key value.

Consider the implementation of the above two points:

Template Class Valuelist

{

PUBLIC:

... // That's the original definition

// Add a default constructor

Valuelist () {};

}

Packaging class for each Key value:

Template

Struct KeyHolder

{

Typedef t value_type;

const bool m_avail; // Used to indicate if m_val is a value of external incoming, defined as const, can only be set when it is created, and other time no T m_val;

Holder (): m_avail (false) {}

Explicit KeyHolder (Const T & V): M_VAL (V), M_avail (True) {}

Template Bool Operator <(Const Keyholder & rhs) Const

{

RETURN M_AVAIL && rHS.M_AVAIL && M_VAL

}

Template Bool Operator! = (const keyholder & rhs) Const

{

RETURN (* this)

}

}

Define a convenient function:

Template

Holder bykey (Const T & T)

{

Return Holder (T);

}

Of course, the type of Valuelist that makes a plurality of Key has quietly changed, and we define the following macro:

#define type_kvlist_1 (t) Valuelist , NULL_TYPE>

#define type_kvlist_2 (t1, t2) Valuelist , TYPE_VLIST_1 (T2)>

#define type_kvlist_3 (T1, T2, T3) Valuelist , TYPE_VLIST_2 (T2, T3)>

...

Finally, according to the above implementation, define a macro that generates qualified Valuelist:

#define kvlist_1 (n) VLIST_1 (bykey (n))

#define kvlist_2 (N1, N2) VLIST_2 (bykey (n1), bykey (n2))

#define kvlist_3 (N1, N2, N3) VLIST_3 (bykey (n1), bykey (n2), bykey (N3))

...

Then modify the comparison algorithm:

Template

Bool Operator <(Const Valuelist , T2> & Key1, Const Valuelist , T2> & Key2)

{

// KeyHolder The specific comparison movement has met our requirements.

IF (key1.m_val1! = key2.m_val1) Return Key1.m_VAL1

Return Key1.m_val2

}

The previous example needs to be redefined:

Typedef MultiKeymap mymap;

MultiKeyMap mymap;

MYMAP [kVLIST_3 (1, 1, 1)] = "111";

...

In the previous section, the usage of KVLIST_3 is the correct pure coincidence. We need more ways to generate a specified type key value, and must also support some only to enter some key values, and a relatively stupid method is to define The following functions:

Template

Vlist Key (Const T1 & V1)

{

Return Makevaluelist (ByHolder (V1), Vlist :: Second_Value_Type ());}

Template

Vlist Key (Const T1 & V1, Const T2 & V2)

{

Return makevaluelist (byholder (v1), key (v2));

}

Template

Vlist Key (Const T1 & V1, Const T2 & V2, Const T3 & V3)

{

Return makevaluelist (byholder (v1), key (v2, v3));

}

...

With the above definition, the correct usage is as follows:

Typedef MultiKeymap mymap;

MyMap mymap;

MyMap [Key (1, 1)] = "111";

MyMap [key (1, 1, 2)] = "112";

MyMap [key (1, 2, 1)] = "121";

MyMap [Key (1, 2, 2)] = "122";

MyMap [Key (1, 2, 3)] = "123";

MyMap [Key (1, 3, 1)] = "131";

// The following implementation part lookup features:

Mymap :: item = mymap.lower_bound (key (1, 2));

MyMap :: item_bound (key (1, 2));

/ / Output Find value:

For (mymap :: iterator it = mymap.begin (); it! = mymap.end (); IT)

Std :: cout << IT-> second << endl;

The result of the above results should be:

121

122

123

So far, we have fully implemented Map that supports multi-key values. Of course, we need to repeat the defined functions with repeated kvlist_xxx, type_kvlist_xxx, Template <...> key (...), we can define one-time definition to support 10 macros and template functions of 10 or more parameters, I believe it is enough, if it is not enough, please do it yourself.

1.2.3 Further optimization

In the above implementation, the generation process of the Key value is more troublesome, it is inconvenient to use. Because it is necessary to know the key value type in MAP, there are two ways to solve this problem, one is to inherit or The adaptation method defines its own MAP class, add a function that generates the key value, because inside the map class knows the key value type of Map; another way, we define the conversion between any two Valuelist types. This method is best made. The following detailed description:

1. Realize the conversion between any Valuelist

First we must implement implicit conversion between Valuelist, implicit conversion has two forms, one is implemented through the constructor of the target type, one is a translation operator that defines a user-defined type of user-converted type. This needs to know the target type, and we have to solve the situation that does not know the type of target type, so it can only be used by the former, constructor: Template

Class Valuelist

{

PUBLIC:

// Each key value is a keyholder type, simply uses the keyholder constructor to complete the type conversion. Then recursively call other Key constructs, NULL_TYPE copy constructs default support, no matter

Template

Valuelist (Const Valuelist & RHS): m_val1 (rhs.m_val1), m_val2 (rhs.m_val2) {}

// Consider that if it passes the length of the Valuelist, the recursive call will eventually use a null_type to construct a Valuelist because we must define the following constructor. If the incoming Valuelist length, you will use one Valuelist to construct NULL_TYPE situation and compile will report an error. We think this is reasonable, it is likely to be written by wrong code.

VALUELIST (NULL_TYPE) {}

}

Implement the constructor of KeyHolder:

Template

Struct KeyHolder

{

...

// The two types must be automatically converted, otherwise report error during compilation

Template

KeyHolder (const keyholder & rhs): m_avail (rhs.m_avail), m_val (rhs.m_val) {}

}

Finally, we can completely abandon the kvlist_xxx macro. You only need to use a vlist_xxx macro at any time. All the types of conversions must be internally.

1.2.4 Example of current code and use

Class null_type {};

Template Class Valuelist

{

PUBLIC:

TYPEDEF T1 First_Value_Type;

TypedEf T2 SECOND_VALUE_TYPE;

T1 m_VAL1;

T2 m_VAL2;

Valuelist (Const T1 & Val1, Const T2 & Val2): M_VAL1 (VAL1), M_VAL2 (VAL2) {}

Template

Valuelist (Const Valuelist & RHS): m_val1 (rhs.m_val1), m_val2 (rhs.m_val2) {}

Explicit Valuelist (null_type) {}

Valuelist () {};

}

Template

Struct KeyHolder

{

Typedef t value_type;

Const bool m_avail;

T M_VAL;

KeyHolder (): m_avail (false) {}

Explicit KeyHolder (Const T & V): M_VAL (V), M_avail (True) {}

Template

KeyHolder (const keyholder & rhs): m_avail (rhs.m_avail), m_val (rhs.m_val) {}

}

Template

Keyholder bykey (Const T & T)

{

Return KeyHolder (T);}

Template

Inline Valuelist MakevaluelIST (Const T1 & Val1, Const T2 & VAL2)

{

Return Valuelist (VAL1, VAL2);

}

#define type_kvlist_1 (t) Valuelist , NULL_TYPE>

#define type_kvlist_2 (t1, t2) Valuelist , Type_Kvlist_1 (T2)>

#define type_kvlist_3 (T1, T2, T3) Valuelist , Type_Kvlist_2 (T2, T3)>

#define vlist_1 (v1) makevaluelist (v1, null_type ())

#define VLIST_2 (V1, V2) MakevaluelIST ((V1), VLIST_1 (V2))

#define VLIST_3 (V1, V2, V3) Makevaluelist ((V1), VLIST_2 (V2, V3))

#define VLIST_4 (V1, V2, V3, V4) Makevaluelist ((V1), VLIST_3 (V2, V3, V4))

#define VLIST_5 (V1, V2, V3, V4, V5) MakevaluelIST ((V1), VLIST_4 (V2, V3, V4, V5))

#define VLIST_6 (V1, V2, V3, V4, V5, V6) Makevaluelist ((V1), VLIST_5 (V2, V3, V4, V5, V6))

#define VLIST_7 (V1, V2, V3, V4, V5, V6, V7) MakevaluelIST ((V1), VLIST_6 (V2, V3, V4, V5, V6, V7))

#define VLIST_8 (V1, V2, V3, V4, V5, V6, V7, V8) Makevaluelist ((V1), VLIST_7 (V2, V3, V4, V5, V6, V7, V8))

#define VLIST_9 (V1, V2, V3, V4, V5, V6, V7, V8, V9) MakevaluelIST ((V1), VLIST_8 (V2, V3, V4, V5, V6, V7, V8, V9)))

#define VLIST_10 (V1, V2, V3, V4, V5, V6, V7, V8, V9, V10) MakevaluelIST ((V1), VLIST_9 (V2, V3, V4, V5, V6, V7, V8, V9, V10) )

Template

Bool Operator <(Const Valuelist , T2> & Key1, Const Valuelist , T2> & Key2)

{

// KeyHolder The specific comparison movement has met our requirements.

IF (key1.m_val1! = key2.m_val1) Return Key1.m_VAL1

Return Key1.m_val2

}

BOOL Operator <(null_type, null_type)

{

Return False;

}

// The following example shows that the type of Key changes:

Typedef std :: map mymap; mymap mm;

MM [VLIST_3 (1, 5)] = "115";

MM [VLIST_3 (1, 3, 5)] = "135";

MM [VLIST_3 (1, 4, 5)] = "145";

MM [VLIST_3 (1, 2, 5)] = "125";

MM [VLIST_3 (1, 2, 4)] = "124";

MM [VLIST_3 (1, 2, 3)] = "123";

Mymap :: item = mm.lower_bound (VLIST_2 (1, 2));

MyMap :: item_bound (VLIST_2 (1, 2));

For (; bit! = Eit; bit) {

Cout << Bit-> second << endl;

}

The result of the above results should be:

123

124

125