C# stl

  • Thread starter Thread starter Harold Howe
  • Start date Start date
H

Harold Howe

Having developed in C++ prior to learning C#, I have always felt like
..NET was missing something. Specifically, something that fills the role
of the STL.

With that in mind, I have launched an open source project to create an
STL like library in C# 2.0. The project is called CSTL, and is available
from sourceforge.net:

http://sourceforge.net/projects/cstl

The library is pre-alpha, incomplete and not ready for primetime use.
However, the concepts are pretty much in place.

Here is an example of the Count algorithm:

int [] values = new int[] {1,2,3,2,2,4,5,2};
int count = Algorithm.Count(values, 2);


Here is an example of the CopyIf algorithm and back insertion iterators

int [] values = new int[] {1,2,3,2,2,4,5,2};
List<int> dest = new List<int>();

Algorithm.CopyIf(values, IteratorUtil.BackInserter(dest)
delegate(int x) { return x>2;});

// dest now contains {3,4,5}

There are other projects like this out there. However, none of them seem
quite right to me. Usually, they don't have an iterator concept, or they
use C++ in non CLS compliant ways.

Feedback is welcome.

H^2
Remove .bounce from email address.
 
Harold,

I think that before you take this too far, you should take a look at
LINQ, and see the overlap between what you are doing, and what is going to
be presented there. There are many concepts that are similar, and I would
hate to see you do so much work which is only going to end up being provided
by MS.
 
I think that before you take this too far, you should take a look at
LINQ, and see the overlap between what you are doing, and what is going to
be presented there.
Click to expand...

Thanks for the suggestion and the heads up. How long until C# 3.0 is
ready for production use? From what little I could find, Orcas is
looking like it may come in the second half of 2007. From past
experience, I know it would take an additional 4 months or so until my
group adopts it.

Worst case scenario is that LINQ renders CSTL completely irrelevant. If
that is true, and it happens in the first half of 2008 or later, then
the developement of CSTL, for me personally, will have been worth it
because I need some of its features now.

If C# 3.0 is released for production use in 2005, then I might change my
tune I guess. Is there a chance that C# 3.0 would be released before Orcas?

H^2
 
Hello Harold,

Nicolas wanted just point that there are too much things around that need
to be improved, rather that doing smth that will be realized soon in the
bounds of framework :)

For example, you can help guys from Nemerle (www.nemerle.org) to realize
these features :)
HH> Thanks for the suggestion and the heads up. How long until C# 3.0 is
HH> ready for production use? From what little I could find, Orcas is
HH> looking like it may come in the second half of 2007. From past
HH> experience, I know it would take an additional 4 months or so until
HH> my group adopts it.
HH>
HH> Worst case scenario is that LINQ renders CSTL completely irrelevant.
HH> If that is true, and it happens in the first half of 2008 or later,
HH> then the developement of CSTL, for me personally, will have been
HH> worth it because I need some of its features now.
HH>
HH> If C# 3.0 is released for production use in 2005, then I might
HH> change my tune I guess. Is there a chance that C# 3.0 would be
HH> released before Orcas?

---
WBR,
Michael Nemtsev :: blog: http://spaces.msn.com/laflour

"At times one remains faithful to a cause only because its opponents do not
cease to be insipid." (c) Friedrich Nietzsche
 
That's probably in the middle of 2008? On what am I basing this on? wild
guess.

--

________________________
Warm regards,
Alvin Bruney [MVP ASP.NET]

[Shameless Author plug]
Professional VSTO.NET - Wrox/Wiley
The O.W.C. Black Book with .NET
www.lulu.com/owc, Amazon
Blog: http://www.msmvps.com/blogs/alvin
-------------------------------------------------------
 
the C# folks at MSFT was stated that the C# v2.0 -> v3.0 cycle will be
much shorter that the v1.0 -> v2.0, because v2.0 required changes to
the CLR, while v3.0 does not. That could make an official release in
2006 possible.
 
Harold Howe said:
Having developed in C++ prior to learning C#, I have always felt like .NET
was missing something. Specifically, something that fills the role of the
STL.
Click to expand...

Harold,

Your project seems very interesting - I'll be sure to download the lib and
play some.

I'm curious what your position on type inference limitations in C# are. I
remember a thread from a while ago where Dietmar Kuehl was talking about
problems implementing STL-like algorithms in C#. Rereading the thread now
("Constraints on Generics ??")message 8 in the following thread)
http://groups.google.com/group/micr...drew+queisser&rnum=109&hl=en#4eabecf7e92f67c6

I'm wondering which route you are taking.

Andrew
 
Hello James,

JC> the C# folks at MSFT was stated that the C# v2.0 -> v3.0 cycle will
JC> be much shorter that the v1.0 -> v2.0, because v2.0 required changes
JC> to the CLR, while v3.0 does not. That could make an official
JC> release in 2006 possible.

Moreover, it totally compatible with C# 2.0 by byte-code. All that new features
are pure syntactic and realized on the compiling stage.
Thus, there is nothing break-throughing in LINQ

---
WBR,
Michael Nemtsev :: blog: http://spaces.msn.com/laflour

"At times one remains faithful to a cause only because its opponents do not
cease to be insipid." (c) Friedrich Nietzsche
 
I'm curious what your position on type inference limitations in C# are.
Click to expand...

They are a drag, to be honest. But I try to work around them as best I can.
I
remember a thread from a while ago where Dietmar Kuehl was talking about
problems implementing STL-like algorithms in C#. Rereading the thread now
("Constraints on Generics ??")message 8 in the following thread)

I'm wondering which route you are taking.
Click to expand...

I have read that thread. Actually, it was the inspiration that got me
started on this whole thing.

Dietmar's two approaches were

public E MinElement<E, C>(E enumerator, C comparer)
where E: Enumerator<T> // or: E: Enumerator<E.ValueType>
where C: Comparer<T> // ... C: Comparer<E.ValueType>
{
// whatever...
}

and

public Enumerator<T> MinElement<T>(Enumerator<T> enumerator,
Comparer<T> comparer)

In CSTL, I have an abstraction for iterators. So I tend not to return
enumerators directly. However, I ran into the same issue that Dietmar
mentions above. In fact, I posted some questions on type inference last
week to this group (subject: Generic type inferrence and anonymous
methods).

My initial attempt at coding MinElement looked like this:

public static I MinElement<I,T>(I begin, I end)
where I: ForwardIterator<T>
where T: IComparable<T>
{ ... }

When I try to call this, I get

main.cs(31,25): error CS0411: The type arguments for method
'Algorithm.MinElement<I,T>(I, I)' cannot be inferred from the usage.
Try specifying the type arguments explicitly.

So I changed the method to this, which is similar to Dietmar's second form:

public static ForwardIterator<T> MinElement<T>(
ForwardIterator<T> begin, ForwardIterator<T> end)
where T: IComparable<T>
{ ... }

Note that ForwardIterator is an interface and not a class.

As Dietmar mentioned, the first form is more desirable, especially in
algorithms that return iterators. The second form results in a reduction
in type information. For example

int[] values = new int[]{1,2,3,4,5};
ListIterator<int> begin = IteratorUtil.Begin(values);
ListIterator<int> end = IteratorUtil.End(values);

//ERROR!
ListIterator<int> min = Algorithm.MinElement(begin,end)

This errors out because MinElement returns the weaker interface type. In
reality, it is returning a ListIterator, but I have to cast in order to
get access to that type.

H^2
 
Harold Howe said:
I'm curious what your position on type inference limitations in C# are.
Click to expand...

They are a drag, to be honest. But I try to work around them as best I
can.
[snip]
When I try to call this, I get

main.cs(31,25): error CS0411: The type arguments for method
'Algorithm.MinElement<I,T>(I, I)' cannot be inferred from the usage.
Try specifying the type arguments explicitly.
Click to expand...

Don't you just want to yell at the compiler "No! You try a little harder!"?
There are probably good reasons for this beyond my grasp but it seems like a
little more inference should be possible.
So I changed the method to this, which is similar to Dietmar's second
form:

public static ForwardIterator<T> MinElement<T>(
ForwardIterator<T> begin, ForwardIterator<T> end)
where T: IComparable<T>
{ ... }

Note that ForwardIterator is an interface and not a class.

As Dietmar mentioned, the first form is more desirable, especially in
algorithms that return iterators. The second form results in a reduction
in type information. For example

int[] values = new int[]{1,2,3,4,5};
ListIterator<int> begin = IteratorUtil.Begin(values);
ListIterator<int> end = IteratorUtil.End(values);

//ERROR!
ListIterator<int> min = Algorithm.MinElement(begin,end)

This errors out because MinElement returns the weaker interface type. In
reality, it is returning a ListIterator, but I have to cast in order to
get access to that type.
Click to expand...

Here you are just trying to return the exact same type as that of the
argument so it's hard to understand why that doesn't work. I think it must
have something to do with the fact that generic types are real honest to
goodness types, not type templates, so your specifying the argument and
return values as ForwardIterator<T> makes them exactly that. I guess that's
why we call generics generics and templates templates.

Andrew
 
Harold said:
Algorithm.CopyIf(values, IteratorUtil.BackInserter(dest)
delegate(int x) { return x>2;});
Click to expand...

I like inserters from STL, C# doesn't have anything similar -- and I
miss it, it's the inverse of an IEnumerator -- just as useful. To be
really useful, the definition needs to be shared in System.Collections,
so developers won't have to adapt different declarations.

Unfortunately, some of the strength of STL is that it can independently
declare (and implement) the same algorithm on many data-structures.
That power stems from being able to add overloads to a name-space from
independent places. That just won't work with C#. And there is no
partial specialization either, so you'll be hard pressed to "collect"
different implementations under the same name.

Also, standard iteration in C# is IEnumerator<T>, which doesn't have
begin and end. You'll get into a lot of work mapping collection-types to
iterators to stay in the STL-spirit.

You can accept the IEnumerator<T> as standard, and still declare
algorithms like copy-if:

CopyIf(IEnumerator<T> values, IInserter<T> inserter, Predicate<T> pred);

I personally prefer adaption where possible, utilizing that there is a
garbage-collector. Of course, you need to be careful when mutating the
constructed proxy, but the caller can always copy it if he wants his own.

/// Return only the items of Parent that satisfy Pred
class FilterCollection<T>: ICollection<T> {
public readonly ICollection<T> Parent;
public readonly Predicate<T> Pred;
...
}

The caller can always add the filtered collection to an existing
collection, using the same CPU-effort.

I have a handy library of adapters, that apply transformations to
ICollection and IDictionary, and it's code can get acceptable
readability using it, here are a few usage examples:

float[] cc1s =
CollectionUtil.ToArray(CollectionUtil.Transform<float,
float>(shortest_path.Values, delegate(float d) { return
(float)Math.Exp(-d); }));

// caught in missing type-inference for anonymous-delegate :)
public IDictionary<Address, float> edgeEvaluator(
ICollection<Address> keys,
TransformCollection<Address, float>.Transformer eval)
{ return DictionaryUtil.Function<Address, float>(keys, eval); }

IDictionary<Address, float> NeighboursOf(Address a)
{
if (a == Root) // Special treatment for root-node
return edgeEvaluator(Network.EntryPoints.Keys,
delegate(Address to) { return
(float)-Math.Log(Network.Nodes[to].RouteChance); });
else if (Network.Nodes[a].Type.CanRoute )
return edgeEvaluator(Network.Neighbours[a].Keys,
delegate(Address to) { return Distance(a, to); });
else // only routers and Root are allowed out-edges
There are other projects like this out there. However, none of them seem
quite right to me. Usually, they don't have an iterator concept, or they
use C++ in non CLS compliant ways.
Click to expand...

Sorry for not checking myself, but are your iterators like c++
iterators? can you mutate through them?
Feedback is welcome.
Click to expand...

Best of luck to you, it just might work -- but a lot of stuff thats used
in intricate ways in STL is simply not there in C#: traits, free
functions, partial-specialization, ...
 
Helge said:
Sorry for not checking myself, but are your iterators like c++
iterators? can you mutate through them?
Click to expand...

Yes.

public interface InputIterator<T> : IEquatable<InputIterator<T>>, ICloneable
{
T Read();
void MoveNext();
void Assign(InputIterator<T> iterator);
}

public interface OutputIterator<T> : ICloneable
{
void Write(T t);
void MoveNext();
void Assign(InputIterator<T> iterator);
}

The forward, bidirectional and random access interfaces follow as you
would expect.

H^2
 
Back
Top