Better Software - November 2008 - (Page 15) Code Craft class recently_used_list { public: void insert(const std::string & most_recent) { std::vector ::iterator found = std::find( elements.begin(), elements.end(), most_recent); if(found != elements.end()) elements.erase(found); elements.insert( elements.begin(), most_recent); } std::vector list() const { return elements; } private: std::vector elements; }; Listing 3 class recently_used_list { const std::vector & list() const { return elements; } }; Listing 4 data type, an operation that preserves uniqueness on insertion and would otherwise be repetitive, tedious, and error prone to write against the typedef in listing 1. The cons: We have failed to capture any of the other constraints or behavior that makes a recently used list a recently used list—as opposed to just a resizeable array. We have allowed operations, such as inserting arbitrary values in arbitrary places, that make sense for vector but not for a recently used list. Furthermore, even though we have a member function, we are still using C’s struct rather than C++’s class, and we have yet to use the private keyword. That must be the problem! Listing 3 addresses this “problem” in a way that turns out to be quite common in practice. We now have a capsule in the form of the recently_used_ list class. The separation between declared public and private parts defines a boundary. The class captures some of the essential features of a recently used list, but whether it does so succinctly, completely, and efficiently is another matter. We have simplified the act of insertion but not much else. This qualified assessment suggests only qualified success. Although many programmers would consider this code to be sufficiently encapsulated—and, therefore, their work complete—this style of class design is almost as unencapsulated as the code in listing 2. And we’ve only just started. called functions. This could prove expensive. So, in listing 4 we have returned the result by reference, bypassing the copy, and have retained source compatibility with all the dependent code that would have been meaningful against listing 3. The list function retains its query status, marked with a trailing const, but now returns a const-qualified reference to elements. This ensures that the caller can look at the elements but can’t change them. On the one hand, it is important not to become overly obsessed with micro-optimizations. These often distract programmers from seeing the bigger picture. On the other hand, it also makes sense to avoid coding habits that squander resources and introduce gratuitous pessimizations. How gratuitous? In comparing the relative performance of using the code in listing 3 with that of listing 4—for example, to call the size function on the result of list—you can be looking at a difference of two orders of magnitude in execution time. In this example, another motivation for returning by reference rather than by copy is to satisfy the principle of least astonishment. The code in listing 3 blows up quite spectacularly should you try to iterate over the contents by calling iterator operations on the result of list. Each iterator returned will be traversing against its own temporary (and deceased) copy of the content. So, the code in listing 4 is not only more efficient, it is safer. But is it better encapsulated? Possibly, given the improved usage experience, but only possibly. A trade has been made that may make you feel a little uncomfortable. We have committed the internal implementation to being a vector. If we were to choose another container, such as a list or a deque, class recently_used_list { const std::vector & list() const { return elements; } std::vector & list() { return elements; } }; Listing 5 Citing References In C++, by default, function arguments and results are passed by copy. For simple types, such as integers and pointers, this is both unsurprising and cheap. However, in returning elements every time the list function is called, we are copying an array that holds strings, each of which is also copied. Given the limited capabilities of recently_used_list’s public interface, the list function is likely to be one of the most heavily www.StickyMinds.com NOVEMBER 2008 BETTER SOFTWARE 15 http://www.StickyMinds.com
For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.