|
|
|
|
Advertisement
|
Do you think of vectors, deques and the other STL containers as arrays on steroids? You were probably taught it that way. You may have been told that officially these containers have great freedom in how they are implemented internally, that an iterator is free to be a big, grown-up class, and certainly not just a humble pointer, and that you shouldn't rely on internal implementation details [10]. But the array paradigm is just so hard to resist.....
This isn't necessarily bad. It breaks encapsulation, in that you are making an assumption about the internal implementation of a container, rather than relying on the bare information in its external interface, but it does allow you to make use of your intuitive understanding of arrays and pointers. It is an example of structural conformance -- the container presents a particular interface that we recognise from other contexts. It looks and smells like an array—and we already understand arrays. Provided that it performs in the way people think it should, nothing goes wrong. This isn't really a software design issue -- it is more a matter of philosophy as to the relative priorities of strict encapsulation and structural conformance. How useful is it to pander to people's expectations, if it might potentially lead them astray?
If all proxied containers were as redundant as vector<bool> [11], and all useful containers were as STL-compliant as vector<string>, we would demand absolute structural conformance and sweep aside the very occasional corner-case. We would not countenance the risk of anyone being deceived by a familiar interface. However, the Catenator is a perfect counter-example. It is intuitively a container with some structural conformance to a vector, but if you think of it as just like a vector, or an array on steroids, you might occasionally be led astray. It is up to the programmer to remember that he is dealing with impossibly large lists and to act accordingly. You could instead provide a completely bespoke interface:
Catenator<std::string> catenator1(vectorstring);
for (std::size_t i = 0; i < catenator1.how_many_items_there_are(); ++i) {
std::cout << catenator1.provide_checked_data_at_index(i);
}
But the cost in terms of reuse is surely too high. Most of the time, structural conformance is too useful to be
ignored. Reconciliation is not a matter of rules but of broad principles. Here are a couple you might like to try out:
So catenator.size() should tell you how many items there are in the catenator and it should do it cheaply and not,
say, by iterating through all the underlying items. Time to burn all those operator[]
implementations that use a linked list.
For instance, in the Catenator class we provide an operator[]. The benefits of providing array-style
access are balanced by a responsibility to prevent the programmer from misusing it. So a naive implementation
might look like this:
value_type operator[](std::size_t index);But this is nasty to any hapless programmer. The following code will compile and run flawlessly:
value_type t = catenator[1]; catenator[2] = t;The first line is blameless. The second line will faithfully copy
t into an unnamed temporary before
casting it into the abyss, along with your career. One simple solution is to define const value_type operator[](std::size_t index) const;And this is the solution that is actually adopted within the Catenator. If you want finer control over the uses of the result of
operator[], replace the return type with a nested class within Catenator:
class Catenator {
....
class ArrayReturn {
value_type t_;
public:
ArrayReturn(value_type tt) : t_(tt) { }
value_type& operator=(value_type tt) {
//put lvalue use here
}
operator value_type( ) {
//put rvalue use here, eg
return t_;
}
};
ArrayReturn operator[](std::size_t index) {
...
return ArrayReturn(result);
}
};
But note that (unless implemented as a bolt-in class inheriting from value_type) this will not allow
constructions such as:
catenator[1].const_mem_function();
The Catenator class is templatized on the underlying item together with a set of traits describing how to manipulate that item. For instance, the length of an item, reversing the item, cutting the last part of the item and inserting new bits in the item are all traits of the item. Another one of these manipulations allows the creation of new empty items:
template<typename T> CatenatorTraits {
....
static T createempty() { return T(); }
....
};
This trait is included to allow the Catenator to contain items that do not have a default constructor—whether a class can be default constructed or requires some other method of creation is surely a trait of that class.
But now consider a customised container aimed at improving the memory handling characteristics of existing containers. It would still be templatized on the contained item and also on a set of traits for that item. But the allocation procedure for new items would be a key policy decision for that container:
template<
typename T,
typename Tr = MemTraits<T>,
typename M = MemAllocator<T>
> MemContainer {
....
};
So how has the same operation transformed itself from a trait carried along with the underlying item into a policy of
the containing class? Clearly, the distinction depends on the purpose of the container. There is no objective
difference. This is a continuation of the philosophy of C++: providing programmers with sufficient flexibility to
extend the language as they see fit. To determine whether an operation is a policy or a trait, you must first know
the purpose of the enclosing class: a shift in perspective is all it takes to transform one into the other.
There is another example of this in the Catenator. The search routines provide scope for the use of wildcards or variable matches, such as matching upper and lower case. Is the way you match the underlying item a trait of that item or a policy of the Catenator? For instance, considering upper and lower case matching, are the strings themselves case-insensitive or is the Catenator simply choosing to ignore case when comparing the strings? This is a rare example where it can be argued either way. The actual Catenator implementation makes it a trait rather than a policy of the Catenator. This avoids adding another template argument to the Catenator itself (or using virtual functions to vary the matching operation). It also allows all the variation in behaviour depending on the member class to be determined in a single place (the traits class) and at compile time. This decision is based, once again, on how the Catenator is to be used in practice. It is assumed that many different types might be contained within a Catenator and that how you match those types is unlikely to vary much. If Catenators contained only one or two types, but a wide variety of behaviour in how those types matched was required, then it might be more efficient—and require less typing—if the matching algorithm were implemented instead as a separate policy.
C++ is variously applauded or criticised for leaving the programmer in charge. It does not take design decisions
for you. The Catenator class, apart from being a useful solution to a set of common problems, shows when you
have to take these decisions yourself. Those decisions are not always determined by logic, but also by
philosophy, good taste and etiquette.
operator[] to return a member of
type reference. In Table 32 in section 20.1.5., reference is required to be
a T&. As the elements of the Catenator returned by operator[] are
constructed when needed and not stored anywhere, they don't have an address and so can't provide a
T&.
deque and other STL containers are still not restricted in this way:
their storage need not be, and is generally not, contiguous.
vector<bool>, together
with a list of its other shortcomings.
|
Sponsored Links
|