projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | .. Sequences/Concepts//Extensible Associative Sequence |80 |
| 2 | ||
| 3 | Extensible Associative Sequence | |
| 4 | =============================== | |
| 5 | ||
| 6 | Description | |
| 7 | ----------- | |
| 8 | ||
| 9 | An |Extensible Associative Sequence| is an |Associative Sequence| that supports | |
| 10 | insertion and removal of elements. In contrast to |Extensible Sequence|, | |
| 11 | |Extensible Associative Sequence| does not provide a mechanism for | |
| 12 | inserting an element at a specific position. | |
| 13 | ||
| 14 | ||
| 15 | Expression requirements | |
| 16 | ----------------------- | |
| 17 | ||
| 18 | |In the following table...| ``s`` is an |Associative Sequence|, | |
| 19 | ``pos`` is an iterator into ``s``, and ``x`` and ``k`` are arbitrary types. | |
| 20 | ||
| 21 | In addition to the |Associative Sequence| requirements, the following must be met: | |
| 22 | ||
| 23 | +-------------------------------+---------------------------------------+---------------------------+ | |
| 24 | | Expression | Type | Complexity | | |
| 25 | +===============================+=======================================+===========================+ | |
| 26 | | ``insert<s,x>::type`` | |Extensible Associative Sequence| | Amortized constant time | | |
| 27 | +-------------------------------+---------------------------------------+---------------------------+ | |
| 28 | | ``insert<s,pos,x>::type`` | |Extensible Associative Sequence| | Amortized constant time | | |
| 29 | +-------------------------------+---------------------------------------+---------------------------+ | |
| 30 | | ``erase_key<s,k>::type`` | |Extensible Associative Sequence| | Amortized constant time | | |
| 31 | +-------------------------------+---------------------------------------+---------------------------+ | |
| 32 | | ``erase<s,pos>::type`` | |Extensible Associative Sequence| | Amortized constant time | | |
| 33 | +-------------------------------+---------------------------------------+---------------------------+ | |
| 34 | | ``clear<s>::type`` | |Extensible Associative Sequence| | Amortized constant time | | |
| 35 | +-------------------------------+---------------------------------------+---------------------------+ | |
| 36 | ||
| 37 | ||
| 38 | Expression semantics | |
| 39 | -------------------- | |
| 40 | ||
| 41 | |Semantics disclaimer...| |Associative Sequence|. | |
| 42 | ||
| 43 | +-------------------------------+-------------------------------------------------------------------+ | |
| 44 | | Expression | Semantics | | |
| 45 | +===============================+===================================================================+ | |
| 46 | | ``insert<s,x>::type`` | Inserts ``x`` into ``s``; the resulting sequence ``r`` is | | |
| 47 | | | equivalent to ``s`` except that | | |
| 48 | | | :: | | |
| 49 | | | | | |
| 50 | | | at< r, key_type<s,x>::type >::type | | |
| 51 | | | | | |
| 52 | | | is identical to ``value_type<s,x>::type``; see |insert|. | | |
| 53 | +-------------------------------+-------------------------------------------------------------------+ | |
| 54 | | ``insert<s,pos,x>::type`` | Equivalent to ``insert<s,x>::type``; ``pos`` is ignored; | | |
| 55 | | | see |insert|. | | |
| 56 | +-------------------------------+-------------------------------------------------------------------+ | |
| 57 | | ``erase_key<s,k>::type`` | Erases elements in ``s`` associated with the key ``k``; | | |
| 58 | | | the resulting sequence ``r`` is equivalent to ``s`` except | | |
| 59 | | | that ``has_key<r,k>::value == false``; see |erase_key|. | | |
| 60 | +-------------------------------+-------------------------------------------------------------------+ | |
| 61 | | ``erase<s,pos>::type`` | Erases the element at a specific position; equivalent to | | |
| 62 | | | ``erase_key<s, deref<pos>::type >::type``; see |erase|. | | |
| 63 | +-------------------------------+-------------------------------------------------------------------+ | |
| 64 | | ``clear<s>::type`` | An empty sequence concept-identical to ``s``; see | | |
| 65 | | | |clear|. | | |
| 66 | +-------------------------------+-------------------------------------------------------------------+ | |
| 67 | ||
| 68 | .. Invariants | |
| 69 | ---------- | |
| 70 | ||
| 71 | For any extensible associative sequence ``s`` the following invariants always hold: | |
| 72 | ||
| 73 | ||
| 74 | Models | |
| 75 | ------ | |
| 76 | ||
| 77 | * |set| | |
| 78 | * |map| | |
| 79 | ||
| 80 | .. * |multiset| | |
| 81 | ||
| 82 | ||
| 83 | See also | |
| 84 | -------- | |
| 85 | ||
| 86 | |Sequences|, |Associative Sequence|, |insert|, |erase|, |clear| | |
| 87 | ||
| 88 | ||
| 89 |