Return to map.3 CVS log

Up to [Research Unix] / researchv10dc / man / adm / man3

Annotation of researchv10dc/man/adm/man3/map.3, revision 1.1

1.1     ! root        1: .TH MAP 3+
        !             2: .CT 2 datatype
        !             3: .SH NAME
        !             4: Map \- associative array classes
        !             5: .SH SYNOPSIS
        !             6: .nf
        !             7: .B "#include <Map.h>"
        !             8: .PP
        !             9: .ds 1s \*S
        !            10: .ds S \fIS\fP
        !            11: .ds T \fIT\fP
        !            12: .ft L
        !            13: Mapdeclare(\*S,\*T)
        !            14: Mapimplement(\*S,\*T)
        !            15: .PP
        !            16: .ft L
        !            17: struct Map(\*S,\*T) {
        !            18:        Map(\*S,\*T)();
        !            19:        Map(\*S,\*T)(const \*T&);
        !            20:        Map(\*S,\*T)(const Map(\*S,\*T)&);
        !            21:        ~Map(\*S,\*T);
        !            22:        Map(\*S,\*T)& operator= (const Map(\*S,\*T)&);
        !            23:        \*T& operator[] (int);
        !            24:        int size();
        !            25:        Mapiter(\*S,\*T) element(const \*S&);
        !            26:        Mapiter(\*S,\*T) first();
        !            27:        Mapiter(\*S,\*T) last();
        !            28: };
        !            29: .PP
        !            30: .ft L
        !            31: struct Mapiter(\*S,\*T) {
        !            32:        Mapiter(\*S,\*T) (const Map(\*S,\*T)&);
        !            33:        ~Mapiter(\*S,\*T);
        !            34:        operator int();
        !            35:        \*S key();
        !            36:        \*T value();
        !            37:        Mapiter(\*S,\*T)& operator++ (Mapiter(\*S,\*T)&);
        !            38:        Mapiter(\*S,\*T)& operator-- (Mapiter(\*S,\*T)&);
        !            39: };
        !            40: .ft R
        !            41: .fi
        !            42: .SH DESCRIPTION
        !            43: A
        !            44: .I map
        !            45: is a collection of
        !            46: .I elements,
        !            47: each of which contains a
        !            48: .I key
        !            49: part of type
        !            50: .I S
        !            51: and a
        !            52: .I value
        !            53: part of type
        !            54: .I T,
        !            55: where
        !            56: .I S
        !            57: and
        !            58: .I T
        !            59: are type names.
        !            60: Both
        !            61: .I S
        !            62: and
        !            63: .I T
        !            64: must have value semantics:
        !            65: assignment or initialization have the effect of copying.
        !            66: (It is unlikely for
        !            67: .I S
        !            68: and
        !            69: .I T
        !            70: to be pointers.)
        !            71: .PP
        !            72: Map elements are ordered by key: type
        !            73: .I S
        !            74: must have a transitive boolean
        !            75: .BR operator< .
        !            76: .PP
        !            77: The macro call
        !            78: .L Mapdeclare(\*S,\*T)
        !            79: declares the classes
        !            80: .B Map(\*S,\*T)
        !            81: and
        !            82: .BR Mapiter(\*S,\*T) .
        !            83: It must appear once in every source file that uses either.
        !            84: The macro call
        !            85: .B Mapimplement(\*S,\*T)
        !            86: defines the functions that implement the map classes.
        !            87: It must appear exactly once in the entire program.
        !            88: .SS Map constructors
        !            89: .nr xx \w'\fLMap(\*S,\*T)(m)\ \fP'
        !            90: .TP \n(xxu
        !            91: .B Map(\*S,\*T)()
        !            92: An empty map.
        !            93: The value part of future elements
        !            94: is the value of an otherwise uninitialized
        !            95: static object of type
        !            96: .I T .
        !            97: .TP
        !            98: .BI Map(\*S,\*T)( x )
        !            99: An empty map whose future elements have
        !           100: default value
        !           101: .I x .
        !           102: .TP
        !           103: .BI Map(\*S,\*T)( m )
        !           104: A copy of map
        !           105: .I m
        !           106: obtained by copying the elements and default value of
        !           107: .I m.
        !           108: .SS Map operators
        !           109: .TP  \n(xxu
        !           110: .IB n " = " m
        !           111: All the elements of map
        !           112: .I n
        !           113: are deleted and and
        !           114: copies of the elements of
        !           115: .I m 
        !           116: are added.
        !           117: The default value of
        !           118: .I n
        !           119: does not change.
        !           120: Running time is
        !           121: .IR O (log(| m |)
        !           122: +
        !           123: .RI log(| n |)),
        !           124: where
        !           125: .RI | m |
        !           126: means
        !           127: .IB m .size() .
        !           128: .TP
        !           129: .IB m [ k ]
        !           130: A reference
        !           131: to the value part of the element of map
        !           132: .I m
        !           133: with key
        !           134: .BR k .
        !           135: If the element does not exist, it is created.
        !           136: Running time is
        !           137: .IR O (log(| m |)) .
        !           138: .SS Other Map functions
        !           139: .TP  \n(xxu
        !           140: .IB m .size()
        !           141: The number of elements in
        !           142: .LR m .
        !           143: Running time is
        !           144: .IR O (1).
        !           145: .TP
        !           146: .IB m .element( k )
        !           147: A map iterator 
        !           148: referring to the element of
        !           149: .I m
        !           150: with key
        !           151: .I k
        !           152: if such an element exists.
        !           153: Otherwise the result is vacuous.
        !           154: Running time is
        !           155: .IR O (log(| m |)) .
        !           156: .TP
        !           157: .IB m .first()
        !           158: .br
        !           159: .ns
        !           160: .TP
        !           161: .IB m .last()
        !           162: A map iterator
        !           163: referring to the element of
        !           164: .I m
        !           165: with the smallest (or largest) key.
        !           166: If
        !           167: .L m
        !           168: has no elements, the result is vacuous.
        !           169: Running time is
        !           170: .IR O (log(| m |)) .
        !           171: .SS "Map iterators"
        !           172: For every class
        !           173: .B Map(\*S,\*T)
        !           174: there is a class
        !           175: .BR Mapiter(\*S,\*T) .
        !           176: A map iterator identifies a map object and possibly
        !           177: an element in that map.
        !           178: An iterator that does not identify an element is
        !           179: .IR vacuous .
        !           180: .SS Mapiter constructors
        !           181: .TP  \n(xxu
        !           182: .BI Mapiter(\*S,\*T)( m )
        !           183: A vacuous iterator referring to map
        !           184: .I m.
        !           185: Running time is
        !           186: .IR O (1).
        !           187: .SS Mapiter operators
        !           188: .TP  \n(xxu
        !           189: .IB i " = " j
        !           190: Make iterator
        !           191: .I i
        !           192: refer (for now) to the same map as does
        !           193: .I j.
        !           194: .TP
        !           195: .BI (int) i
        !           196: Zero if iterator
        !           197: .I i
        !           198: is vacuous, otherwise nonzero.
        !           199: .TP
        !           200: .BI ++ i
        !           201: .br
        !           202: .ns
        !           203: .TP
        !           204: .BI -- i
        !           205: If iterator
        !           206: .I i
        !           207: is vacuous, make it refer to the map element with
        !           208: the smallest (or largest) key
        !           209: Otherwise, make it refer to the map element with the
        !           210: next key greater (or less) than the key of the
        !           211: current element.
        !           212: If no such element exists,
        !           213: .I i
        !           214: becomes vacuous.
        !           215: The running time of a single increment
        !           216: operation for map
        !           217: .I m
        !           218: is
        !           219: .IR O (log(| m |)).
        !           220: However an iterator 
        !           221: takes only time
        !           222: .IR O (| m |)
        !           223: to sequence through the whole map.
        !           224: .SS Other mapiter functions
        !           225: .TP  \n(xxu
        !           226: .IB i .key()
        !           227: .br
        !           228: .ns
        !           229: .TP
        !           230: .IB i .value()
        !           231: The key (or value) part of the element referred to by
        !           232: .I i .
        !           233: If
        !           234: .I i
        !           235: is vacuous, return
        !           236: the value of an otherwise uninitialized static
        !           237: object of appropriate type.
        !           238: Running time is
        !           239: .IR O (1).
        !           240: .SH EXAMPLES
        !           241: .EX
        !           242: struct city { char name[100]; };
        !           243: typedef int population;
        !           244: int operator< (const city&, const city&);
        !           245: .EE
        !           246: .PP
        !           247: .B Mapdeclare(name,population)
        !           248: .PP
        !           249: .B Map(name,population) gazetteer;
        !           250: .PP
        !           251: .B "// Print big cities; set populations of others to zero.
        !           252: .PP
        !           253: .EX
        !           254:        for(Mapiter(name,population) i = gazetteer.first(); i; i++)
        !           255:                if(i.value() > 1000000)
        !           256:                        printf("%s\en", i.key().name);
        !           257:                else
        !           258:                        gazetteer[i.key()] = 0;
        !           259: .EE
        !           260: .SH BUGS
        !           261: A `type name'
        !           262: .B Map(\*S,\*T)
        !           263: or
        !           264: .BR Mapiter(\*S,\*T) 
        !           265: that contains spaces will be mangled by
        !           266: .IR cpp (8).
        !           267: .br
        !           268: There is no way to delete a single element.
        !           269: .br
        !           270: Ambiguities can occur if the type name
        !           271: .I S
        !           272: contains an underscore.
        !           273: .br
        !           274: No precautions are taken against running out of memory.

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.