A sum is very similar to a product. It is a collection of addends.
But there is a difference: We want our sum to collect addends of the
same type (A+A = 2*A).
Collecting means: Searching if there is something equal. The search itself is
a O(n) process. But since we have to do it with every addend the collection
of same addends becomes a O(n2) process with a potential expensive
erasure of matching terms. So we should think about an efficient solution.
Additionally there must be a prefactor associated with every addend.
How to realize this?
There is a very simple, elegant and efficient solution to this problem: The STL type map.
A map is an associative container that is: it maps a key onto a value.
Think of a phone book. A phone book maps names (keys) onto phone numbers (values).
You could also think of a vector as a map. A vector maps consecutive cardinal numbers
onto a value. The STL map generalizes these consecutive cardinal numbers to
an arbitrary type. The only thing a map requires from the key is that it must
provide a strong ordering for efficiency reasons (enable binary search).
But what has this to do with our problem of collecting same addends of a sum?
Use the addend as the key and the counting number as the value! That's it.
Once again we want to keep everything pretty general and use templates. Now there are two potentially variable types in our concept of a sum: The addend and the counting number. We template both. This will turn out to be very useful for example if we replace the counting numbers with rational numbers (not floating point or integer numbers).
Interface: Sum.H
1 #include <map>
2 #include <iostream>
3
4 using namespace std;
5
6
7 /*!
8 Implements a sum
9
10 */
11 template <class Object, class Field>
12 class Sum :
13 public map<Object, Field> {
14 public:
15
16 //! inplace addition of an Object
17 Sum<Object, Field> & operator += (Object const & o);
18
19 //! inplace subtraction of an Object
20 Sum<Object, Field> & operator -= (Object const & o);
21
22 //! inplace addition of a Sum of Objects
23 Sum<Object, Field> & operator += (Sum<Object, Field> const & s);
24
25 //! inplace subtraction of a Sum of Objects
26 Sum<Object, Field> & operator -= (Sum<Object, Field> const & s);
27
28 //! inplace addition of an Object-Field pair
29 Sum<Object, Field> & operator += (pair<Object, Field> const & p);
30
31
32 };
33
34
35 //! output operator for Sums of Ts
36 template <class Object, class Field>
37 ostream & operator << (ostream & o, Sum<Object, Field> const & p);
38
39 #include "Sum.CH"
Implementation: Sum.CH
1 template <class Object, class Field>
2 inline
3 Sum<Object, Field> & Sum<Object, Field>::operator += (Object const & o)
4 {
5 (*this)[o] += 1;
6 return *this;
7 }
8
9 template <class Object, class Field>
10 inline
11 Sum<Object, Field> & Sum<Object, Field>::operator -= (Object const & o)
12 {
13 (*this)[o] -= 1;
14 return *this;
15 }
16
17 template <class Object, class Field>
18 inline
19 Sum<Object, Field> & Sum<Object, Field>::operator += (Sum<Object, Field> const & s)
20 {
21 for ( typename Sum<Object, Field>::const_iterator i=s.begin() ; i!=s.end() ; ++i )
22 (*this)[i->first] += i->second;
23 return *this;
24 }
25
26 template <class Object, class Field>
27 inline
28 Sum<Object, Field> & Sum<Object, Field>::operator -= (Sum<Object, Field> const & s)
29 {
30 for ( typename Sum<Object, Field>::const_iterator i=s.begin() ; i!=s.end() ; ++i )
31 (*this)[i->first] -= i->second;
32 return *this;
33 }
34
35 template <class Object, class Field>
36 inline
37 Sum<Object, Field> & Sum<Object, Field>::operator += (pair<Object, Field> const & p)
38 {
39 (*this)[p.first] += p.second;
40 return *this;
41 }
42
43 template <class Object, class Field>
44 inline
45 ostream & operator << (ostream & o, Sum<Object, Field> const & p)
46 {
47 for ( typename Sum<Object, Field>::const_iterator i=p.begin() ; i!=p.end() ; ++i )
48 {
49 if ( i->second<0 )
50 {
51 if ( i!=p.begin() )
52 o << " - ";
53 else
54 o << "-";
55 }
56 else
57 {
58 if ( i!=p.begin() )
59 o << " + ";
60 }
61 if ( abs(i->second)!=1 )
62 o << abs(i->second) << "*";
63 o << i->first;
64 }
65 return o;
66 }
Let's test it: Sum_Test.C
1 #include "Sum.H"
2 #include <string>
3
4 using namespace std;
5
6 int main()
7 {
8 Sum<string, int> p;
9
10 p += string("A");
11 p += string("B");
12 p += string("B");
13 p += string("B");
14 p += string("A");
15
16 cout << p << endl;
17
18 return 0;
19 }
The output is (download files into a fresh directory, compile and link with g++ *.C, run a.out)
2*A + 3*BOkay. That seems to make sense...