<HTML>
<!--
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2001
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. We make no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<Title>Monoid</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../c++boost.gif"
ALT="C++ Boost" width="277" height="86">
<BR Clear>
<H1><A NAME="concept:Monoid"></A>
Monoid
</H1>
A <i>Monoid</i> is a concept that describes a simple kind of algebraic
system. A <b>monoid</b> consists of a set of elements <i>S</i>, a
binary operation, and an identity element. The C++ representation of a
monoid consists of a function object that implements the binary
operation, a set of objects that represent the elements of <i>S</i>,
and an object that represents the identity element.
<H3>Refinement of</H3>
The element type must be a model of <a
href="../../utility/Assignable.html">Assignable</a> and <a
href="../../utility/CopyConstructible.html">CopyConstructible</a>.
The function object type must be a model of <a
href="http://www.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>.
<h3>Notation</h3>
<Table>
<TR>
<TD><tt>X</tt></TD>
<TD>Is the element type of the Monoid.</TD>
</TR>
<TR>
<TD><tt>a, b</tt></TD>
<TD>are objects of type <tt>X</tt>.</TD>
</TR>
<TR>
<TD><tt>op</tt></TD>
<TD>Is the function object implementing the Monoid operation.</TD>
</TR>
<TR>
<TD><tt>i</tt></TD>
<TD>is an object of type <tt>X</tt> and is the identity element
for the Monoid.</TD>
</TR>
</table>
<h3>Valid Expressions</h3>
<Table border>
<tr>
<td><a name="sec:source"><TT>op(a, b)</TT></a></TD>
<TD>See below for semantics.<br>
Return type: <TT>X</TT>
</TD>
</TR>
<tr>
<TD><TT>a == b</TT></TD>
<TD>Returns true if <tt>a</tt> and <tt>b</tt> represent
the same element of <i>S</i>.<br>
Return type: <TT>bool</TT>
</TD>
</TR>
<tr>
<TD><TT>a != b</TT></TD>
<TD>Returns true if <tt>a</tt> and <tt>b</tt> represent
different elements of <i>S</i>.<br>
Return type: <TT>bool</TT>
</TD>
</TR>
</TABLE>
<P>
<H3>Invariants</H3>
<UL>
<li>Closure<br>
The result of <tt>op(a, b)</tt> is also an element of <i>S</i>.
<li>Associativity<br>
<tt>op(op(a, b), c) == op(a, op(b, c))</tt>
<li>Definition of Identity Element<br>
<tt>op(a, i) == a</tt>
</UL>
<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000-2001</TD><TD>
<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
Indiana University (<A
HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
<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>
<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>
</BODY>
</HTML>
