Monoliths "Unstrung"
Difficulty: 3 / 10

"All for one, and one for all" may work for Musketeers, but it doesn't work nearly as well for class designers. Here's an example that is not altogether exemplary, and it illustrates just how badly you can go wrong when design turns into overdesign. The example is, unfortunately, taken from a standard library near you...

Problem

JG Question

1. What is a "monolithic" class, and why is it bad? Explain.

Guru Questions

2. List all the member functions of std::basic_string.

3. Which ones should be members, and which should not? Why?

Solution

Avoid Unduly Monolithic Designs

1. What is a "monolithic" class, and why is it bad? Explain.

The word "monolithic" is used to describe software that is a single big, indivisible piece, like a monolith. The word "monolith" comes from the words "mono" (one) and "lith" (stone) whose vivid image of a single solid and heavy stone well illustrates the heavyweight and indivisible nature of such code.

A single heavyweight facility that thinks it does everything is often a dead end. After all, often a single big heavyweight facility doesn't really do more -- it often does less, because the more complex it is, the narrower its application and relevance is likely to be.

In particular, a class might fall into the monolith trap by trying to offer its functionality through member functions instead of nonmember functions, even when nonmember nonfriend functions would be possible and at least as good. This has at least two drawbacks:

Where it's practical, break generic components down into pieces.

Guideline: Prefer "one class (or function), one responsibility."

Guideline: Where possible, prefer writing functions as nonmember nonfriends.

The rest of this article will go further toward justifying the latter guideline.

The Basics of Strings

2. Name all the member functions of std::basic_string.

It's, ahem, a fairly long list. Counting constructors, there are no fewer than 103 member functions. Really. If that's not monolithic, it's hard to imagine what would be.

Imagine yourself in an underground cavern, at the edge of a subterranean lake. There is a submerged channel that leads to the next air-filled cavern. You prepare to dive into the black water and swim through the flooded tunnel...

Take a deep breath, and repeat after ISO/IEC 14882:1998(E) [1]:

It's important to ask these and related questions because we want to put as many functions into the last bucket as possible.

A word about efficiency: For each function, we'll consider whether it can be implemented as a nonmember nonfriend function as efficiently as a member function. Is this premature optimization (an evil I often rail against)? Not a bit of it. The primary reason why I'm going to consider efficiency is to demonstrate just how many of basic_string's member functions could be implemented "equally well as nonmember nonfriends." I want to specifically shut down any accusations that making them nonmember nonfriends is a potential efficiency hit, such as preventing an operation from being performed in constant time if the standard so requires. A secondary reason is optimizing a library is not premature when the library's implementer has concrete information from past experience (e.g., past user reports, or his own experience in the problem domain) about what operations are being used by users in time-sensitive ways. So don't get hung up about premature optimization -- we're not falling into that trap here. Rather, we are primarily investigating just how many of basic_string's members could "equally well" be implemented as nonmember nonfriends. Even if you are expecting many to be implementable as nonmembers, the actual results may well surprise you.

Operations That Must Be Members

As a first pass, let's sift out those operations that just have to be members. There are some obvious ones at the beginning of the list.

Clearly the above functions must be members. It's impossible to write a constructor, destructor, assignment operator, or [] operator in any other way!

12 functions down, 91 to go...

Operations That Should Be Members

We asked: Which operations need access to internal data we would otherwise have to grant via friendship? Clearly these have a reason to be members, and normally ought to be. This list includes the following, some of which provide indirect access to (e.g., begin()) or change (e.g., reserve()) the internal state of the string:

The above ought to be members not only because they're tightly bound to basic_string, but they also happen to form the public interface that nonmember nonfriend functions will need to use. Sure, you could implement these as nonmember friends, but why?

There are a few more that I'm going to add to this list as fundamental string operations:

We'll return to the question of insert(), erase(), and replace() a little later. For replace() in particular, it's important to be able to choose well and make the most flexible and fundamental version(s) into member(s).

Into the Fray: Possibly-Contentious Operations That Can Be Nonmember Nonfriends

First in this section, allow me to perform a stunning impersonation of a lightning rod by pointing out that all of the following functions have something fundamental in common, to wit: Each one could obviously as easily -- and as efficiently -- be a nonmember nonfriend.

Sure they can be nonmember nonfriends, that's obvious, no sweat. Of course, the above functions also happen to have something else pretty fundamental in common: They're mentioned in the standard library's container and sequence requirements, as member functions. Hence the lightning-rod effect...

"Yeah, wait!" I can already hear some standardiste-minded people saying, heading in my direction and resembling the beginnings of a brewing lynch mob. "Not so fast! Don't you know that basic_string is designed to meet the C++ Standard's container and sequence requirements, and those requirements require or suggest that some of those functions be members? So quit misleading the readers! They're members -- live with it!" Indeed, and true, but for the sake of this discussion I'm going to waive those requirements with a dismissive wave of a hand and a quick escape across some back yards past small barking dogs and various clothes drying on the line.

Having left my pursuers far enough behind to resume reasoned discourse, here's the point: For once, the question I'm considering here isn't what the container requirements say. It's which functions can without loss of efficiency be made nonmember nonfriends, and whether there's any additional benefit to be gained from doing so. If those benefits exist for something the container requirements say must be a member, well, why not point out that the container requirements could be improved while we're at it? And so we shall...

Take empty() as a case in point. Can we implement it as a nonmember nonfriend? Sure... the standard itself requires the following behavior of basic_string::empty(), in the C++ Standard, subclause 21.3.3, paragraph 14:

Returns: size() == 0.

Well, now, that's pretty easy to write as a nonmember without loss of efficiency:

template<class charT, class traits, class Allocator>
bool empty( const basic_string<charT, traits, Allocator>& s )
{
  return s.size() == 0;
}

Notice that, while we can make size() a member and implement a nonmember empty() in terms of it, we could not do the reverse. In several cases here there's a group of related functions, and perhaps more than one could be nominated as a member and the others implemented in terms of that one as nonmembers. Which function should we nominate to be the member? My advice is to choose the most flexible one that doesn't force a loss of efficiency -- that will be the enabling flexible foundation on which the others can be built. In this case, we choose size() as the member because its result can always be cached (indeed, the standard encourages that it be cached because size() "should" run in constant time), in which case an empty() implemented only in terms of size() is no less efficient than anything we could do with full direct access to the string's internal data structures.

For another case in point, what about at()? The same reasoning applies. For both the const and non-const versions, the standard requires the following:

Throws: out_of_range if pos >= size().

Returns: operator[]( pos ).

That's easy to provide as a nonmember, too. Each is just a two-line function template, albeit a bit syntactically tedious because of all those template parameters and nested type names -- and remember all your typenames! Here's the code:

template<class charT, class traits, class Allocator>
typename basic_string<charT, traits, Allocator>
         ::const_reference
at( const basic_string<charT, traits, Allocator>& s,
    typename basic_string<charT, traits, Allocator>
             ::size_type pos )
{
  if( pos >= s.size() ) throw out_of_range( "don't do that" );
  return s[pos];
}

template<class charT, class traits, class Allocator>
typename basic_string<charT, traits, Allocator>::reference
at( basic_string<charT, traits, Allocator>& s,
    typename basic_string<charT, traits, Allocator>
             ::size_type pos )
{
  if( pos >= s.size() )
    throw out_of_range( "I said, don't do that" );
  return s[pos];
}

What about clear()? Easy, that's the same as erase(begin(),end()). No fuss, no muss. Exercise for the reader, and all that.

What about length()? Easy, again -- it's defined to give the same result as size(). What's more, note that the other containers don't have length(), and it's there in the basic_string interface as a sort of "string thing", but by making it a nonmember suddenly we can consisently say "length()" about any container. Not too useful in this case because it's just a synonym for size(), I grant you, but a noteworthy point in the principle it illustrates -- making algorithms nonmembers immediately also makes them more widely useful and usable.

In summary, let's consider the benefits and drawbacks of providing functions like at() and empty() as members vs. nonmembers. First, just because we can write these members as nonmembers (and nonfriends) without loss of efficiency, why should we do so? What are the actual or potential benefits? Here are several:

Having said that, what are the potential drawbacks? Here are two, although in my opinion they are outweighed by the above advantages:

With perhaps these more contentious choices out of the way, then, let's continue with other operations that can be nonmember nonfriends. Some, like those listed above, are mentioned in the container requirements as members; again, here we're considering not what the standard says we must do, but rather what given a blank page we might choose to do in designing these as members vs. nonmember nonfriends.

More Operations That Can Be Nonmember Nonfriends

Consider first resize():

What's the linchpin holding all the members of this group together as valid nonmember nonfriends? It's insert(), hence insert()'s status as a good choice to be the member that does the work and encapsulates the append-related access to the string's internals in one place, instead of spreading the internal access all over the place in a dozen different functions.

Next, insert(): For those of you who might think that six-count'em-six versions of assign() and six-count'em-six versions of append() might have been a little much, those were just the warmup... now we consider the eight-count'em-eight versions of insert(). Above, I've already nominated the three-parameter version of insert() as a member, and now it's time to justify why. First, as noted above, insert() is a more general operation than append(), and having a member insert() allowed all the append() operations to be nonmember nonfriends; if we didn't have at least one insert() as a member, then at least one of the append()s would have had to be a member, and so I chose to nominate the more fundamental and flexible operation. But we have eight-count'em-eight flavors of insert() -- which one (or more) ought to be the member(s)? Five of the eight forms of insert() are already specified in terms of the three-parameter form, and the others can also be implemented efficiently in terms of the three-parameter form, so we only need that one form to be a member. The others can all be nonmember nonfriends.

For those of you who might think that the eight-count'em-eight versions of insert() take the cake, well, that was warmup too. In a moment we'll consider the ten-count'em-ten forms of replace(). Before we attempt those, though, let's take a short break to tackle an easier function first, because it turns out that erase() is instructive in building up to dealing with replace()...

Coffee Break (Sort Of): Erasing erase()

Next erase(): After talking about the total 30-count'em-30 flavors of assign(), append(), insert(), and replace() -- and having dealt with 20 of the 30 already above -- you will be relieved to know that there are only three forms of erase(), and that only two of them belong in this section. After what we just went through for the others, this is like knocking off for a well-deserved coffee break...

The troika of erase() members is a little interesting. At least one of these erase() functions must be a member (or friend), there being no other way to erase efficiently using the other already-mentioned member functions alone. There are actually two "families" of erase() functions:

erase( pos, length )
    basic_string& erase(size_type pos = 0, size_type n = npos);

erase( iter, ... )
    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);

First, notice that the two families' return types are not consistent: the first version returns a reference to the string, whereas the other two return iterators pointing immediately after the erased character or range. Second, notice that the two families' argument types are not consistent: the first version takes an offset and length, whereas the other two take an iterator or iterator range; fortunately, we can convert from iterators to offsets via pos = iter - begin() and from offsets to iterators via iter = begin() + pos.

(Aside: The standard does not require, but an implementer can choose, that basic_string objects store their data in a contiguous charT array buffer in memory. If they do, then the conversion from iterators to positional offsets and vice versa clearly need incur no overhead. (I would argue that even segmented storage schemes could provide for very efficient conversion back and forth between offsets and iterators using only the container's and iterator's public interfaces.)

This allows the first two forms to be expressed in terms of the third (again, remember your typenames and qualifications!):

template<class charT, class traits, class Allocator>
basic_string<charT, traits, Allocator>&
erase( basic_string<charT, traits, Allocator>& s,
       typename Allocator::size_type pos = 0,
       typename Allocator::size_type n =
         basic_string<charT, traits, Allocator>::npos )
{
  if( pos > s.size() )
    throw out_of_range( "yes, we have no bananas" );
  typename basic_string<charT, traits, Allocator>::iterator
    first = s.begin()+pos,
    last = n == basic_string<charT, traits, Allocator>::npos
           ? s.end() : first + min( n, s.size() - pos );
  if( first != last )
    s.erase( first, last );
  return s;
}

template<class charT, class traits, class Allocator>
typename basic_string<charT, traits, Allocator>::iterator
erase( basic_string<charT, traits, Allocator>& s,
       typename basic_string<charT, traits, Allocator>
                ::iterator position )
{
  return s.erase( position, position+1 );
}

OK, coffee break's over...

Back to Work: Replacing replace()

Next, replace(): Truth be told, the ten-count'em-ten replace() members are less interesting than they are tedious and exhausting.

At least one of these replace() functions must be a member (or friend), there being no other way to replace efficiently using the other already-mentioned member functions alone. In particular, note that you can't efficiently implement replace() in terms erase() followed by insert() or vice versa because both ways would require more character shuffling, and possibly buffer reallocation.

Note again that we have two families of replace() functions:

replace( pos, length, ... )
    basic_string& replace(size_type pos1, size_type n1, // #1
                          const basic_string& str);
    basic_string& replace(size_type pos1, size_type n1, // #2
                          const basic_string& str,
                          size_type pos2, size_type n2);
    basic_string& replace(size_type pos, size_type n1,  // #3
                          const charT* s, size_type n2);
    basic_string& replace(size_type pos, size_type n1,  // #4
                          const charT* s);
    basic_string& replace(size_type pos, size_type n1,  // #5
                          size_type n2, charT c);

replace( iter, iter, ... )
    basic_string& replace(iterator i1, iterator i2,     // #6
                          const basic_string& str);
    basic_string& replace(iterator i1, iterator i2,     // #7
                          const charT* s, size_type n);
    basic_string& replace(iterator i1, iterator i2,     // #8
                          const charT* s);
    basic_string& replace(iterator i1, iterator i2,     // #9
                          size_type n, charT c);
    template<class InputIterator>                       // #10
      basic_string& replace(iterator i1, iterator i2,
                            InputIterator j1,
                            InputIterator j2);

This time, the two families' return types are consistent; that's a small pleasure. But, as with erase(), the two families' argument types are not consistent: one family is based on an offset and length, whereas the other is based on an iterator range. As with erase(), because we can convert between iterators and positions, we can easily implement one family in terms of the other.

When considering which must be members, we want to choose the most flexible and fundamental version(s) as members and implement the rest in terms of those. Here are a few pitfalls one might encounter while doing this analysis, and how one might avoid them. Consider first the first family:

Consider second the second family:

So it appears that the best we can do is two member functions upon which we can then build everything else as nonmember nonfriends. The members are the "iter, iter, num, char" and templated versions. The nonmembers are everything else. (Exercise for the reader: For each of the other eight versions, write sample implementations as efficient nonmember nonfriends.)

Note that #10 well illustrates the power of templates -- this one function can be used to implement all but two of the others without any loss of efficiency, and to implement the remaining ones with what would probably be only a minor loss of efficiency (constructing a temporary basic_string containing n copies of a character).

Time for another quick coffee break...

Coffee Break #2: Copying copy() and substr()

Oh, copy(), schmopy(). Note that copy() is a somewhat unusual beast, and that its interface is inconsistent with the std::copy() algorithm. Note again the signature:

Each family has four members:

All of these can be written efficiently as nonmember nonfriends; the implementations are left as exercises for the reader. Having said that, we're done!

But let's add one final note about string finding. In fact, you might have noticed that, in addition to the extensive bevy of basic_string::*find*() algorithms, the C++ Standard also provides a not-quite-as-extensive-but-still-plentiful bevy of std::*find*() algorithms. In particular:

What's more, the nonmember algorithms are more flexible, because they work on more than just strings. Indeed, all of the basic_string::*find*() algorithms could be implemented using the std::find and std::find_end(), tossing in appropriate predicates and/or reverse_iterators as necessary.

So what about just ditching the basic_string::*find*() families altogether and just telling users to use the existing std::find*() algorithms? One caution here is that, even though the basic_string::*find*() work can be emulated, doing it with the default implementations of std::find*() would incur significant loss of performance in some cases, and there's the rub. The three forms each of find() and rfind() that search for substrings (not just individual characters) can be made much more efficient than a brute-force search that tries each position and compares the substrings starting at those positions. There are well-known algorithms that construct finite state machines on the fly to run through a string and find a substring (or prove is absence) in linear time, and it might be desirable to take advantage of such techniques.

To take advantage of such optimizations, could we provide overloads (not specializations, see [6]) of std::find*() that work on basic_string iterators? Yes, but only if basic_string::iterator is a class type, not a plain charT*. The reason is that we wouldn't want to specialize std::find() for all pointer types is because not all character pointers necessarily point into strings; so we would need basic_string::iterator to be a distinct type that we can detect and partially specialize on. Then those specializations could perform the optimizations and work at full efficiency for matching substrings.

Decomposition and encapsulation are Good Things. In particular, it's often best to separate the algorithm from the container, which is what the STL does most of the time.

It's widely accepted that basic_string has way too many member functions. Of the 103 functions in basic_string, only 32 really need to be members, and 71 could be written as nonmember nonfriends without loss of efficiency. In fact, many of them needlessly duplicate functionality already available as algorithms, or are themselves algorithms that would be useful more widely if only they were decoupled from basic_string instead of buried inside it.

Don't repeat basic_string's mistakes in your design -- decouple your algorithms from your containers, use template specialization or overloading to get special-purpose behavior where warranted (as for substring searching), and above all follow the guidelines:

References

[1] A thick tome also known as the ISO C++ Standard.

[2] H. Sutter. "What's In a Class? The Interface Principle" (C++ Report, 10(3), March 1998).

[3] H. Sutter. Exceptional C++, Items 31-34 (Addison-Wesley, 2000).

[4] S. Meyers. “How Non-Member Functions Improve Encapsulation” (C/C++ Users Journal, 18(2), February 2000).

[5] S. Meyers. Effective STL (Addison-Wesley, 2000).

[6] H. Sutter. "Why Not Specialize Function Templates?" (C/C++ Users Journal, 19(7), July 2001).

Copyright © 2009 Herb Sutter