So now I'm back to work on Super Awesome Library 5000. Or possibly STL.Net. Or maybe SGL. I haven't decided yet. Its pretty close to being at a point where I would feel comfortable showing off actual code, but not quite. I think I'm going to finish up with the basic algorithms and maybe implement a deque, and then release a demo version before I do any hard work on the sorted containers [although I have a basic Set class put together, it is pretty ugly and doesn't quite work yet].
In the mean time, I'm going to give a basic overview of the project as a whole, and some of the design decisions I've made along the way.
First of all, let me make it clear that this was a project born of boredom. Neccessity may be the mother of invention, but boredom is the drunk uncle that nobody really likes. It basically started because I was a little annoyed that enumerators in .Net don't allow you to modify the values you are enumerating. I missed my iterators, but realized that given the behavior of .Net generics iterators wouldn't work anyhow. But then one day I got bored [my internet broke down so I couldn't play WoW, and I have no television] and decided that I would go ahead and try to implement iterators anyhow. I knew I would fail, but I had nothing better to do with my time.
As luck would have it, I succeeded. Or somewhat succeeded...it was rudimentary, but a good proof of concept. My internet was still down, so I figured what the hell...why not just go all the way and recreate the whole shebang? Now, its evolved into something I want to do just because I can.
The reason I say all that is because I'm still convincing myself that its OK to reinvent the wheel in this case [embarrass] I'm fully expecting the end result to be slower than the standard counterparts, as well as harder to use in some regards, and probably less safe to boot. And I know it isn't portable as of yet, because mono is incapable of running it [although gmcs does compile it all properly]. But maybe I'll learn something useful1, or people will find it handy. At the very least, I'll have something to chug away at while I'm bored [grin]
So, onto the actual design. To begin with, let me explain where it isn't going to be a straight port, and why.
The biggest difference is that I've decided to omit custom allocators. From a design standpoint, they seem to go against the idea of running in a managed environment. From a practical standpoint, I wouldn't know how to program a custom allocator in .Net anyhow. Also, .Net doesn't allow you to specify default parameters, so you would have to explicitly state that you wanted the standard allocator every single time. This fact is compounded by MSs decision to not implement typedefs in C#, so even that shorthand isn't possible in the language I chose to implement this system in. All together, the decision to remove custom allocators was a pretty easy one to make.
A similar process will probably result in sorted containers not being parameterized on comparators. As I mentioned, I haven't actually completed this portion of things yet, but I will almost certainly go the route of System.Collections.Generic.SortedDictionary, and accept a Comparer object. I haven't quite finished analyzing what effects this will have, however, so the final result remains to be seen.
I am also discarding the SC++L style of using_lots_of_underscores in favor of a more .Net-friendly UsingLotsOfCapitalization.
Iterators are an actual concrete type rather than the abstract pseudo-type they are in C++. In addition to allowing Iterators to work at all within the confines of .Net generics, they allowed me to make Distance and Advance member functions rather than global functions. This is quite important, as I'm pretty sure its the only way functions like std::lower_bound can perform better with vectors than they do with lists. It is impossible to specialize generics, so there can only be one implementation of Advance(itr, n), which would have to be to the effect of while(n--) itr++;. But, itr.Advance(n) can be inherited by a RandomAccessIterator to be just itr += n;2
For obvious reasons, iterators aren't dereferenced via *itr. Instead, a property Value is exposed.
There are no iterator tags, or type-traits, or anything like that, because generics would be completely unable to utilize them. Instead, such information is carried in the inheritance. If you are implementing a BidirectionalIterator, then you inherit from BidirectionalIterator. I suppose that isn't entirely accurate...you can use inheritance in C++ to achieve similar effects, but you don't *have* to. distance_type is always int, and you just have to keep track of value_type on your own3.
Although they do not now, ultimately the containers will all expose .Net-style interfaces. Vector will inherit from IList, and so forth. The primary reason they don't already is because I'm lazy. I'm also torn on whether or not to rename List so it is a little less confusing when mingled in with the standard containers. I suppose naming it LinkedList wouldn't be *that* bad, but that can wait. They do currently inherit from IEnumerable [and its generic cousin] so they can be used with foreach.
I think that pretty much covers the big changes that I'm aware of. Although I used a lot of words to describe them, they're largely superficial and don't really effect how you actually use everything. Implementations are a little odd, but that's something I have to worry about, not you [grin] The weirdness, however, all comes from inheriting from the proper objects. Once you've done that, all the grunt work is done, and you just have to provide three or four implementations so that all the real hard stuff [like overloaded operators, which were a bitch and a half to get working right] is done for you automagically.
I want to move onto implementation details, but I have to work in two hours and honestly, I'm not sure I have the time. Its pretty complex, and I'd rather not just throw the stuff out there without explaining why I did what I had to do. So that can wait for another day.
CM
1 Speaking of learning something, did you know that _ is a valid name in C#? I assume it works in other languages as well, I've just never bothered to try it and see. I'm tempted to write a class named _ and fill it with functions named __ and ___ and ____ just for the hell of it. Unfortunately, this knowledge was learned independant of STL.Net, so I haven't quite justified my time yet.
2 In my last journal entry, I stated the following:
Quote:
The biggest hurdle I think I have left to overcome is how to specialize algorithms for specific types of iterators. Haven't had any inspirations on that front in a while, so I fear it might not happen.
This was only partially true, and was mostly my memory playing tricks on me. I haven't had any inspirations as to how to specialize algorithms...instead, I think making Distance and Advance member functions has allowed me to work around the problem to a certain extent. I forgot about that. It isn't a perfect solution, but its good enough for government work.
3 The lack of a way to specify value_type is, to date, the biggest annoyance I have with this whole system. I say that only half-heartedly, however, as I'm not positive a simple typedef would actually solve any of the problems I associate with the lack of said typedef. It is a conventient scapegoat, though.
