3

Is naming a class according to its implementation an acceptable practice?

e.g. SortedSet if the class is maintains a sorted list of unique items or TreeSet if it using a binary search tree structure instead.

7

A class identifier should reflect things that outside users of that class identifier are likely to care about. Because different users are likely to care about different things, it will generally not be possible to find a name with the "perfect" level of descriptiveness for all usage scenarios.

Note that there is a common pattern of List foo<Bar> = new ArrayList<Bar>(); Code which creates the list selects a kind of list to create, but code which uses the list doesn't need to use the identifier ArrayList. It's debatable whether the word "Array" is semantically meaningful, or would have been omitted if such were possible. Arguably a better pattern would have been List foo<Bar> = List<Bar>.CreateNew();, in which case most client code would never have to see the class name ArrayList; the collection types were implemented early on in the development of Java, however, and thus reflect a mixture of good and bad practices.

Note, by the way, that while Java will not allow an interface to be used in a new expression, there really wouldn't be anything wrong semantically with allowing programmers to say new List() when they want a new object which implements the List interface, they don't need the object to do anything beyond what's included in the interface, and they don't want to promise to refrain from using any particular features of the interface. Most code which wants a new empty list shouldn't care whether it's backed by a single array, an array of arrays, a linked list of arrays, or some other structure.

  • 1
    ergo: SortedSet is acceptable because when client code iterates over the object it will iterate over a sorted sequence, whereas SetTree is unnecessary because it's implementation is of no consequence to the client code? – cheezsteak Nov 10 '14 at 20:43
  • 1
    @ptwales: Correct, if clients are expected to care that the data is sorted, and would not be expected to care that a set was stored as a tree; a slight caveat, however, is that some people who see the name SortedSet might expect that for efficiency the set would require items to be added mostly in order. A name like SortedTreeSet would say something about the expected performance characteristics, which clients might possibly care about. – supercat Nov 10 '14 at 20:55
  • "there really wouldn't be anything wrong semantically with allowing programmers to say new List()" what? how would this make any sense at all? List isn't a class, it doesn't contain any code, it doesn't DO anything. what would you expect it to return? – sara Apr 19 '16 at 14:52
  • @kai: It would return an instance of some type which implements List in a fashion suitable for the constructor arguments (if any); the call would be equivalent to calling a static member of List. – supercat Apr 19 '16 at 14:57
  • what constructor? an interface by definition has no constructor, because it is not a class. there is nothing to implement the interface, because all you have is an interface. what you're describing sounds more like an abstract class with a private constructor and a private nested derived class that can be created via a static factory method. – sara Apr 19 '16 at 15:05
4

Look no further than C++'s STL:

std::map

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

std::unordered_map

std::unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once hash is computed, it refers to the exact bucket the element is placed into.

std::set

std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as red-black trees.

std::unordered_set

std::unordered_set is an associative container that contains set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

I believe these examples reasonably reflect your case. This is just a smattering. There are a number of other examples.

However, note @Deduplicator's comment below, and my response. The STL names reflect differences in the how the classes can and should be used, not their internal implementations. I'm not sure about your example. If there is no impact on how a consumer interacts with the class, then IMO implementation details should not be reflected in its name. A class's name should reflect its intended usage by consumers.

If there is a significant different in performance, such as might be the case in your example, depending on the type and volume of data being stored, then perhaps a name reflecting that might work better. "SortedSet" and "QuickSet", for example, such as we find with Quicksort - although that is simply a generic name for a particular algorithm, not the formal name of a class.

  • 2
    The names actually reflect the contract, not the implementation. A small but important difference. (A good thing, as a user really only should care about the public interface) – Deduplicator Nov 11 '14 at 2:30
  • @Deduplicator - I understand what you're saying and I agree. The naming here does reflect how a consumer would interact with the class, although it's not particularly explicit. My analogy to the example cited in the question is correct - but it doesn't exactly match the question as stated. The answer to the question exactly as stated - with respect to the internal implementation, would he "No", like you said. – Vector Nov 11 '14 at 4:20
  • 1
    @Deduplicator -see my edit. – Vector Nov 11 '14 at 4:26
3

Since other (Java) implementations of Collections describe their implementation, sometimes to great detail (e.g. CopyOnWriteArrayList) I would say yes, naming after the implementation is fine, and is expected.

Unlike @supercat, I think this detailed naming is a good thing, as, unfortunately, at some point, somebody actually has to pick a specific implementation - a HashMap where things are super fast but unsorted, or a TreeMap which is slightly slower but things are sorted, or some ConcurrentXXX version?

It might be o.k. to follow his idea and have List.newInstance() or Map.newInstance(), but "they" would have to spec which kind of "default, best general purpose" implementation it does create. This might cause a lot of arguments.

Often in my code I will implement a protected method to generate a new collection, e.g.

protected Map newMap() {
   return new HashMap();
}

and allow end users to override if they prefer something else.

  • IMHO, code should endeavor to specify what it needs, and leave open things it doesn't care about; good languages should facilitate that. If a future version of a framework comes up with an improved "general-purpose" implementation of a base class or interface which has a different internal design, but will work interchangeably with the old one in any code which doesn't use Reflection or serialization, replacing the old implementation with a new implementation of the same class would break things, but having a factory method return the new type shouldn't break any properly-written clients. – supercat Nov 12 '14 at 15:52
  • Clients which rely upon the internal design of a class should make instances using the constructor of the exact class they want, but clients who aren't going to be concerned about the design internals should create instances in a way which would allow the framework to substitute a different class whose internals are different but whose external behavior remains the same. – supercat Nov 12 '14 at 15:53
  • @supercat I agree with you in theory. In practice, I don't, which is why my classes often have a protected newCollection() method. :-) In Java, my defaults are ArrayList and HashMap. But many of my coworkers preferred LinkedList and LinkedHashMap as defaults. And when you now throw in concurrency I don't think anybody can pick a "reasonable" default implementation. – user949300 Nov 13 '14 at 19:11
  • Having factory methods for such purposes is fine. My point was that most consumers of things like ArrayList don't really care whether or not all items are allocated in a single contiguous array, but some might; having code only use type ArrayList when it cares about such things would allow framework authors to do things differently (e.g. a List implementation could keep a queue of pending insert or delete requests, and handle read-by-index requests by adjusting the index based upon those pending requests; when enough items are added or deleted, or the cost of adjusting... – supercat Nov 13 '14 at 19:29
  • ...read-by-index requests gets too great, then apply all pending operations at once). Many consumers of List would be happy with such an implementation, but a few might not. If code could indicate "in advance" whether such new implementations would be desirable, that would be helpful. Even with regard to things like concurrency, having a factory method which accepted a "requirements" parameter could be nicer than having a variety of collection types that would fit different needs, and would allow framework authors to develop more specific types when a need for them was demonstrated. – supercat Nov 13 '14 at 19:32
2

Ask yourself this question: "if I do this, does it make the program easier to understand?".

Outside of functionality, one of your main goals when writing code should be clarity. Code is read many, many times more than it is written so it should be as easy to understand as possible. Choose patterns that aid in readability.

1

SortedSet seems perfectly fine to me. TreeSet might just be called Set but I don't think it's a huge deal. I actually like TreeSet better than std::set in C++. I might be an oddball since I'm so data-oriented. The idea behind std::set is that it shouldn't matter whether it's using a binary tree or a skip list for its implementation, provided it fulfills its algorithmic requirements. That's a wonderful idea except for the fact that the standard library aims to be as applicable as possible for the most performance-critical areas. Besides that, if you tell any computer scientists that you're using a "balanced binary tree" or "hash table", we already understand so much about the algorithmic complexity of your data structure without pages and pages of documentation. If you ask me, that's very concise documentation, not irrelevant implementation details! Why'd we spend all this time in CS if we're just going to use sets and maps and not care about the data structures behind them?

Of course you have to know your audience to figure out how technical or not you should be, but I'd say C++ is too difficult of a language to be trying to hide information about data structures from the C++ developer, and that C++ developers are often too performance-oriented to not care about things beyond algorithmic complexity in deciding what container or algorithm to use. I think to many of us it is worth noting that std::sort uses an introsort typically with a special case for sorting small ranges. We geek out on that stuff. Of course if there was a magical way to make std::sort the one sort to rule them all, then I'd prefer std::sort, at which point we can be like:

Yep, I'm using std::sort. It is the fastest sort in the entire world for all possible input cases for all possible vendor implementations that will ever come to existence on this planet and using any other sort, including Intel's own parallel sort, is just a masturbatory exercise in slowing down code.

But there is generally no algorithm to rule them all, no data structure to rule them all. Each one comes with its pros and cons that go way beyond algorithmic complexity. It is easier to answer questions about who the hottest woman is alive (Jessica Alba) than what algorithm or data structure is best. I would have preferred introsort for the name, and where's my std::radix_sort? I love radix sorts and I've replaced std::sort with naive radix sorts in applicable cases with reasonable boosts but I'd prefer to just use a standardized version that the C++ library implementers can micro-tune like crazy.

When performance is a concern, in practice, I often find those details about the underlying data representation just as important as the algorithmic details. For a blatant example, the fact that vector is implemented using a contiguous array is actually a detail that affects usage in many scenarios. That goes beyond performance. The fact that it uses an internal array makes a huge difference in whether its underlying contents can be passed along to C APIs which expect a pointer to an array, e.g. It's something worth noting and mentioning (which C++11 and beyond now do, but it wasn't always so). Beyond that, understanding its underlying data representation gives you a very precise idea of exactly how much a compacted vector will use which can be useful in those cases where we have to be frugal with memory use (embedded systems, e.g., if you are ballsy enough to use standard containers there). It isn't a good enough feeling for me if I'm working on a raytracer to just know basic things like that std::vector is a random-access sequence with amortized constant time push_backs. It is really worth noting that it's just an array which keeps track of capacity and size and reallocates when trying to insert to a full one (I even find the growth rate typically being 1.5 to 2x the former size to be of interest).

As a less blatant example, the idea that deque often uses page-sized blocks is a non-trivial detail important to people who use it, since the only reason you'd use deque over vector in cases where you didn't need constant-time push_front would be if those internal differences in data representations affect performance or robustness (for example, you might want to avoid vector in a case where you're tempted to allocate data larger than the OS might typically be able to find as a set of contiguous pages, since deque is only partially contiguous).

These details often do matter to the users of the library as evident by the number of people talking and speculating about the implementation details even when the authors tried not to mention it. In performance-critical areas, things like memory layout and memory usage can be just as important to note as algorithmic complexity in deciding whether or not to use this or that.

Now that's different from spilling implementation details which never matter, or doing so in a way that makes an interface harder to comprehend and use. For example, I don't care about the data structures internally used in a particle system in a game engine when all I can do is write code against it, since I have no choice but to use the game engine's particle system. So there it makes no sense to me to make clients have to know more than they need to know just to use the particle system. I would prefer to know the minimum in that case and let the game developers focus on the internal data representation since such knowledge wouldn't aid me in the slightest except maybe to pester the game developers about seeking more optimal representations, for which they'd probably ignore me anyway.

So err on the side of minimalism and not mentioning the details, but keep in mind that sometimes the details do matter to people using the library. When it comes to generalized data structures, I'm often hungry for more information about underlying data representations, memory layouts, and memory usage, not less.

  • That vector is compatible with a C array is promised by it's data() member, not by it's internal implementation. Specifically, it isn't just calling new T[size] when it reallocates. (more like new std::aligned_storage<T>[capacity]) – Caleth Dec 7 '17 at 11:22
  • And if you need interopability with C arrays, you still have a choice. Both vector and array have data() members with the same promises – Caleth Dec 7 '17 at 11:26
  • That's the case with C++11 where it has become a standard guarantee, but in the 90s it wasn't always so. It used to be the case where there was no standard guarantee that vector was contiguous, but often people speculated that it is a reliable enough assumption that vector would always be internally represented as a dynamic array under the hood to access &vec[0] when passing a vector's contents to a C API. Back then there was no data method. Main point there is that these details always mattered before they were even guaranteed and documented. – user204677 Dec 7 '17 at 11:35
  • ... and if anything, the fact that vector now documents and guarantees this with a data method newly added for this specific purpose kind of supports that reasoning. The underlying data representations of these containers always mattered to people in selecting their containers of choice. They're not irrelevant implementation details. Like even if std::set fulfilled its algorithmic requirements, people in practice are probably just as interested in its memory usage characteristics. It would not be so desirable to use std::set if it required 200 bytes of memory overhead per element, e.g. – user204677 Dec 7 '17 at 11:37
  • As another example, people have come up with libraries like SmallVector in LLVM here: llvm.org/doxygen/classllvm_1_1SmallVector.html. What point is there to such a container if it doesn't have any different algorithmic complexity than std::vector? And that's where I think the original idea of the STL as it was called back then by Stepanov made a misstep of trying to focus only on algorithmic complexity, since there's more than complexity requirements guiding our choices in performance-critical areas. – user204677 Dec 7 '17 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.