Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/Monoid.html @ 45

Last change on this file since 45 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 2.9 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2001
4  --
5  -- Distributed under the Boost Software License, Version 1.0.
6  -- (See accompanying file LICENSE_1_0.txt or copy at
7  -- http://www.boost.org/LICENSE_1_0.txt)
8  -->
9<Head>
10<Title>Monoid</Title>
11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
12        ALINK="#ff0000"> 
13<IMG SRC="../../../boost.png" 
14     ALT="C++ Boost" width="277" height="86"> 
15
16<BR Clear>
17
18<H1><A NAME="concept:Monoid"></A>
19Monoid
20</H1>
21
22A <i>Monoid</i> is a concept that describes a simple kind of algebraic
23system. A <b>monoid</b> consists of a set of elements <i>S</i>, a
24binary operation, and an identity element. The C++ representation of a
25monoid consists of a function object that implements the binary
26operation, a set of objects that represent the elements of <i>S</i>,
27and an object that represents the identity element.
28
29
30<H3>Refinement of</H3>
31
32The element type must be a model of <a
33href="../../utility/Assignable.html">Assignable</a> and <a
34href="../../utility/CopyConstructible.html">CopyConstructible</a>.
35The function object type must be a model of <a
36href="http://www.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>.
37
38<h3>Notation</h3>
39
40<Table>
41<TR>
42<TD><tt>X</tt></TD>
43<TD>Is the element type of the Monoid.</TD>
44</TR>
45
46<TR>
47<TD><tt>a, b</tt></TD>
48<TD>are objects of type <tt>X</tt>.</TD>
49</TR>
50
51<TR>
52<TD><tt>op</tt></TD>
53<TD>Is the function object implementing the Monoid operation.</TD>
54</TR>
55
56<TR>
57<TD><tt>i</tt></TD>
58<TD>is an object of type <tt>X</tt> and is the identity element
59for the Monoid.</TD>
60</TR>
61
62
63</table>
64
65<h3>Valid Expressions</h3>
66
67<Table border>
68
69<tr>
70<td><a name="sec:source"><TT>op(a,&nbsp;b)</TT></a></TD>
71<TD>See below for semantics.<br>
72Return type: <TT>X</TT>
73</TD>
74</TR>
75
76<tr>
77<TD><TT>a&nbsp;==&nbsp;b</TT></TD>
78<TD>Returns true if <tt>a</tt> and <tt>b</tt> represent
79     the same element of <i>S</i>.<br>
80Return type: <TT>bool</TT>
81</TD>
82</TR>
83
84<tr>
85<TD><TT>a&nbsp;!=&nbsp;b</TT></TD>
86<TD>Returns true if <tt>a</tt> and <tt>b</tt> represent
87     different elements of <i>S</i>.<br>
88Return type: <TT>bool</TT>
89</TD>
90</TR>
91
92</TABLE>
93
94<P>
95
96<H3>Invariants</H3>
97
98<UL>
99  <li>Closure<br>
100     The result of <tt>op(a, b)</tt> is also an element of <i>S</i>.
101  <li>Associativity<br>
102     <tt>op(op(a, b), c) == op(a, op(b, c))</tt>
103  <li>Definition of Identity Element<br>
104       <tt>op(a, i) == a</tt>
105</UL>
106
107<br>
108<HR>
109<TABLE>
110<TR valign=top>
111<TD nowrap>Copyright &copy 2000-2001</TD><TD>
112<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
113Indiana University (<A
114HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
115<A HREF="../../../people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
116<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
117Indiana University (<A
118HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
119</TD></TR></TABLE>
120
121</BODY>
122</HTML> 
Note: See TracBrowser for help on using the repository browser.