]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ++++++++++++++++++++++++++++ |
2 | Interoperability Revisited | |
3 | ++++++++++++++++++++++++++++ | |
4 | ||
5 | :date: $Date$ | |
6 | :copyright: Copyright Thomas Witt 2004. | |
7 | ||
8 | .. Distributed under the Boost | |
9 | .. Software License, Version 1.0. (See accompanying | |
10 | .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
11 | ||
12 | Problem | |
13 | ======= | |
14 | ||
15 | The current iterator_facade specification makes it unneccessarily tedious to | |
16 | implement interoperable iterators. | |
17 | ||
18 | In the following text a simplified example of the current iterator_facade specification is used to | |
19 | illustrate the problem. | |
20 | ||
21 | In the current specification binary operators are implemented in the following way:: | |
22 | ||
23 | template <class Derived> | |
24 | struct Facade | |
25 | { | |
26 | }; | |
27 | ||
28 | template <class T1, T2> | |
29 | struct is_interoperable : | |
30 | or_< | |
31 | is_convertible<T1, T2> | |
32 | , is_convertible<T2, T1> | |
33 | > | |
34 | {}; | |
35 | ||
36 | template< | |
37 | class Derived1 | |
38 | , class Derived2 | |
39 | > | |
40 | enable_if<is_interoperable<Derived1, Derived2>, bool> operator==( | |
41 | Derived1 const& lhs | |
42 | , Derived2 const& rhs | |
43 | ) | |
44 | { | |
45 | return static_cast<Derived1 const&>(lhs).equal_to(static_cast<Derived2 const&(rhs)); | |
46 | } | |
47 | ||
48 | The problem with this is that operator== always forwards to Derived1::equal_to. The net effect is that the | |
49 | following "obvious" implementation of to interoperable types does | |
50 | not quite work. :: | |
51 | ||
52 | struct Mutable : Facade<Mutable> | |
53 | { | |
54 | bool equal_to(Mutable const&); | |
55 | }; | |
56 | ||
57 | struct Constant : Facade<Constant> | |
58 | { | |
59 | Constant(); | |
60 | Constant(Constant const&); | |
61 | Constant(Mutable const&); | |
62 | ||
63 | ... | |
64 | ||
65 | bool equal_to(Constant const&); | |
66 | }; | |
67 | ||
68 | Constant c; | |
69 | Mutable m; | |
70 | ||
71 | c == m; // ok, dispatched to Constant::equal_to | |
72 | m == c; // !! error, dispatched to Mutable::equal_to | |
73 | ||
74 | Instead the following "slightly" more complicated implementation is necessary | |
75 | ||
76 | struct Mutable : Facade<Mutable> | |
77 | { | |
78 | template <class T> | |
79 | enable_if<is_convertible<Mutable, T> || is_convertible<T, Mutable>, bool>::type equal_to(T const&); | |
80 | }; | |
81 | ||
82 | struct Constant : Tag<Constant> | |
83 | { | |
84 | Constant(); | |
85 | Constant(Constant const&); | |
86 | Constant(Mutable const&); | |
87 | ||
88 | template <class T> | |
89 | enable_if<is_convertible<Constant, T> || is_convertible<T, Constant>, bool>::type equal_to(T const&); | |
90 | }; | |
91 | ||
92 | Beside the fact that the code is significantly more complex to understand and to teach there is | |
93 | a major design problem lurking here. Note that in both types equal_to is a function template with | |
94 | an unconstrained argument T. This is necessary so that further types can be made interoperable with | |
95 | Mutable or Constant. Would Mutable be defined as :: | |
96 | ||
97 | struct Mutable : Facade<Mutable> | |
98 | { | |
99 | bool equal_to(Mutable const&); | |
100 | bool equal_to(Constant const&); | |
101 | }; | |
102 | ||
103 | Constant and Mutable would still be interoperable but no further interoperable could be added | |
104 | without changing Mutable. Even if this would be considered acceptable the current specification forces | |
105 | a two way dependency between interoperable types. Note in the templated equal_to case this dependency | |
106 | is implicitly created when specializing equal_to. | |
107 | ||
108 | Solution | |
109 | ======== | |
110 | ||
111 | The two way dependency can be avoided by enabling type conversion in the binary operator | |
112 | implementation. Note that this is the usual way interoperability betwween types is achieved | |
113 | for binary operators and one reason why binary operators are usually implemented as non-members. | |
114 | ||
115 | A simple implementation of this strategy would look like this :: | |
116 | ||
117 | template< | |
118 | class T1 | |
119 | , class T2 | |
120 | > | |
121 | struct interoperable_base : | |
122 | if_< | |
123 | is_convertible< | |
124 | T2 | |
125 | , T1 | |
126 | > | |
127 | , T1 | |
128 | , T2> | |
129 | {}; | |
130 | ||
131 | ||
132 | template< | |
133 | class Derived1 | |
134 | , class Derived2 | |
135 | > | |
136 | enable_if<is_interoperable<Derived1, Derived2>, bool> operator==( | |
137 | Derived1 const& lhs | |
138 | , Derived2 const& rhs | |
139 | ) | |
140 | { | |
141 | typedef interoperable_base< | |
142 | Derived1 | |
143 | , Derived2 | |
144 | >::type Base; | |
145 | ||
146 | return static_cast<Base const&>(lhs).equal_to(static_cast<Derived2 const&(rhs)); | |
147 | } | |
148 | ||
149 | This way our original simple and "obvious" implementation would | |
150 | work again. :: | |
151 | ||
152 | c == m; // ok, dispatched to Constant::equal_to | |
153 | m == c; // ok, dispatched to Constant::equal_to, m converted to Constant | |
154 | ||
155 | The backdraw of this approach is that a possibly costly conversion of iterator objects | |
156 | is forced on the user even in cases where direct comparison could be implemented | |
157 | in a much more efficient way. This problem arises especially for iterator_adaptor | |
158 | specializations and can be significantly slow down the iteration over ranges. Given the fact | |
159 | that iteration is a very basic operation this possible performance degradation is not | |
160 | acceptable. | |
161 | ||
162 | Luckily whe can have our cake and eat it by a slightly more clever implementation of the binary | |
163 | operators. :: | |
164 | ||
165 | template< | |
166 | class Derived1 | |
167 | , class Derived2 | |
168 | > | |
169 | enable_if<is_convertible<Derived2, Derived1>, bool> operator==( | |
170 | Derived1 const& lhs | |
171 | , Derived2 const& rhs | |
172 | ) | |
173 | { | |
174 | return static_cast<Derived1 const&>(lhs).equal_to(static_cast<Derived2 const&(rhs)); | |
175 | } | |
176 | ||
177 | template< | |
178 | class Derived1 | |
179 | , class Derived2 | |
180 | > | |
181 | enable_if<is_convertible<Derived1, Derived2>, bool> operator==( | |
182 | Derived1 const& lhs | |
183 | , Derived2 const& rhs | |
184 | ) | |
185 | { | |
186 | return static_cast<Derived2 const&>(rhs).equal_to(static_cast<Derived1 const&(lhs)); | |
187 | } | |
188 | ||
189 | Given our simple and obvious definition of Mutable and Constant nothing has changed yet. :: | |
190 | ||
191 | c == m; // ok, dispatched to Constant::equal_to, m converted to Constant | |
192 | m == c; // ok, dispatched to Constant::equal_to, m converted to Constant | |
193 | ||
194 | But now the user can avoid the type conversion by supplying the | |
195 | appropriate overload in Constant :: | |
196 | ||
197 | struct Constant : Facade<Constant> | |
198 | { | |
199 | Constant(); | |
200 | Constant(Constant const&); | |
201 | Constant(Mutable const&); | |
202 | ||
203 | ... | |
204 | ||
205 | bool equal_to(Constant const&); | |
206 | bool equal_to(Mutable const&); | |
207 | }; | |
208 | ||
209 | c == m; // ok, dispatched to Constant::equal_to(Mutable const&), no conversion | |
210 | m == c; // ok, dispatched to Constant::equal_to(Mutable const&), no conversion | |
211 | ||
212 | This definition of operator== introduces a possible ambiguity when both types are convertible | |
213 | to each other. I don't think this is a problem as this behaviour is the same with concrete types. | |
214 | I.e. :: | |
215 | ||
216 | struct A {}; | |
217 | ||
218 | bool operator==(A, A); | |
219 | ||
220 | struct B { B(A); }; | |
221 | ||
222 | bool operator==(B, B); | |
223 | ||
224 | A a; | |
225 | B b(a); | |
226 | ||
227 | a == b; // error, ambiguous overload | |
228 | ||
229 | Effect | |
230 | ====== | |
231 | ||
232 | Iterator implementations using iterator_facade look exactly as if they were | |
233 | "hand-implemented" (I am working on better wording). | |
234 | ||
235 | a) Less burden for the user | |
236 | ||
237 | b) The definition (standardese) of specialized adpters might be easier | |
238 | (This has to be proved yet) |