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.

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.

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.

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.

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.