Why Strings as Classes?

[superdan]

Christopher Wright Wrote:

> superdan wrote:
> > Benji Smith Wrote:
> > 
> >> superdan wrote:
> >>> relax. believe me i'm tryin', maybe you could put it a better way and meet me in the middle.
> >> Okay. I'll try :)
> > 
> > 'preciate that.
> > 
> >> Think about a collection API.
> > 
> > okay.
> > 
> >> The container classes are all written to satisfy a few basic primitive 
> >> operations: you can get an item at a particular index, you can iterate 
> >> in sequence (either forward or in reverse). You can insert items into a 
> >> hashtable or retrieve them by key. And so on.
> > 
> > how do you implement getting an item at a particular index for a linked list? 
> 
> class Node(T)
> {
> 	Node!(T) next;
> 	T value;
> }

so far so good.

> class LinkedList(T)
> {
> 	Node!(T) head;
> 
> 	/** Gets the ith item of the list. Throws: SIGSEGV if i >= length of 
> the list. Time complexity: O(N) for a list of length N. This operation 
> is provided for completeness and not recommended for frequent use in 
> large lists. */
> 	T opIndex(int i)
> 	{
> 		auto current = head;
> 		while (i)
> 		{
> 			current = current.next;
> 		}
> 		return current.value;
> 	}
> }

oopsies. houston we got a problem here. problem is all that pluggable sort business works only if it can count on a constant time opIndex. why? because sort has right in its spec that it takes o(n log n) time. if u pass LinkedList to it you obtain a nonsensical design that compiles but runs afoul of the spec. because with that opIndex sort will run in quadratic time and no amount of commentin' is gonna save it from that.

this design is a stillborn.

what needs done is to allow different kinds of containers implement different interfaces. in fact a better way to factor things is via iterators, as stl has shown.

> > how do you make a hashtable, an array, and a linked list obey the same interface? guess hashtable has stuff that others don't support?
> 
> You have an interface for collections (you can add, remove, and get the 
> length, maybe a couple other things).

this is an incomplete response. what do you add for a vector!(T)? A T. what do you add for a hash!(T, U)? you tell me. and you tell me how you make that signature consistent across vector and hash.

> You have an interface for lists (they're collections, and you can index 
> them).

wrong. don't ever mention a linear-time indexing operator in an interview. you will fail it right then. you can always define linear-time indexing as a named function. but never masquerade it as an index operator.

> Then you can use all the collection-oriented stuff with lists, and you 
> can do special list-type things with them if you want.
> 
> > these are serious questions. not in jest not rhetorical and not trick.
> 
> Yes, but they're solved problems.

apparently not since you failed at'em.

> >> Someone else comes along and writes a library of algorithms. The 
> >> algorithms can operate on any container that implements the necessary 
> >> operations.
> > 
> > hm. things are starting to screech a bit. but let's see your answers to your questions above.
> > 
> >> When someone clever comes along and writes a new sorting algorithm, I 
> >> can plug my new container class right into it, and get the algorithm for 
> >> free. Likewise for the guy with the clever new collection class.
> > 
> > things ain't that simple.
> 
> Collection-oriented library code will care sufficiently about 
> performance that this mix-and-match stuff is not feasible.

what's that supposed to mean? you sayin' stl don't exist?

> Almost 
> anything else doesn't care enough to take only an 
> AssociativeArrayHashSet and not a TreeSet or a LinkedList or a primitive 
> array.

wrong for the reasons above.

> > saw this flick "the devil wears prada", an ok movie but one funny remark stayed with me. "you are in desperate need of chanel." 
> > 
> > i'll paraphrase. "you are in desperate need of stl." you need to learn stl and then you'll figure why you can't plug a new sorting algorithm into a container. you need more guarantees. and you need iterators.
> > 
> >> We don't bat an eye at the idea of containers & algorithms connecting to 
> >> one another using a reciprocal set of interfaces.
> > 
> > i do. it's completely wrong. you need iterators that broker between containers and algos. and iterators must give complexity guarantees.
> 
> I don't. If I'm just going to iterate through the items of a collection, 
> I only care about the opApply. If I need to index stuff, I don't care if 
> I get a primitive array or Bob Dole's brand-new ArrayList class.

you too are in desperate need for stl.