Why Strings as Classes?

superdan super at dan.org
Mon Aug 25 19:31:52 PDT 2008


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? 

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?

these are serious questions. not in jest not rhetorical and not trick.

> 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.

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.

> In most cases, you get 
> a performance **benefit** because you can mix and match the container 
> and algorithm implementations that most suit your needs. You can design 
> your own performance solution, rather than being stuck a single "low 
> level" implementation that might be good for the general case but isn't 
> ideal for your problem.

assuming there are iterators in the picture, sure. there is a performance benefit. even more so when said mixing and matching is done during compilation.

> Over in another message BCS said he wants an array index to compile to 3 
> ASM ops. Cool I'm all for it.

great. but then you must be all for the consequences of it.

> I don't know a whole lot about the STL, but my understanding is that 
> most C++ compilers are smart enough that they can produce the same ASM 
> from an iterator moving over a vector as incrementing a pointer over an 
> array.

they are because stl is designed in a specific way. that specific way is lightyears away from the design you outline above.

> So the default implementation is damn fast.

not sure what you mean by default here, but playing along.

> But if someone else, with special design constraints, needs to implement 
> a custom container template, it's no problem. As long as the container 
> provides a function for getting iterators to the container elements, it 
> can consume any of the STL algorithms too, even if the performance isn't 
> as good as the performance for a vector.
> 
> There's no good reason the same technique couldn't provide both speed 
> and API flexibility for text processing.

you see here's the problem. you systematically forget to factor in the cost of reaching through a binary interface. and if that's not there, congrats. you just discovered perpetual motion.

stl is fast for two main reasons. one. it uses compile-time interfaces and not run-time interfaces as you want. two. it defines and strictly uses a compile-time hierarchy of iterators with stringent complexity guarantees.

your container design can't be fast because it uses runtime interfaces. let alone that you don't mention complexity guarantees. but let's say those can be provided. but the fundamental problem is that you want runtime interfaces for a very low level data structure. fast that can't be. please understand.



More information about the Digitalmars-d mailing list