std::set                                 1593
stdext::hash_set                         2047

Wintellect.PowerCollections.Set          1328
Wintellect.PowerCollections.OrderedSet   1890

using System;
using Wintellect.PowerCollections;


delegate void Tester();

class MyRandom
{
    int seed;

    public int Next()
    {
        seed = (int) (seed * 214013L + 2531011L);
        return (seed >> 16) & 0x7fff;
    }
}

class Test
{
    static void InvokeTest(Tester tester, string comment)
    {
        int timer0 = Environment.TickCount;
        tester();
        int timer1 = Environment.TickCount;
        Console.WriteLine("{0,-40} {1}", comment, timer1 - timer0);
    }
        
    const int N_OPS = 100;
    const int N_ITERATIONS = 100000;
    
    static void Main()
    {
        InvokeTest(
            delegate
            {
                MyRandom random = new MyRandom();
                Set<int> s  = new Set<int>();
                for (int i = 0; i < N_ITERATIONS; i++)
                {
                    s.Clear();
                    for (int j = 0 ;j < N_OPS; j++)
                    {
                        if (random.Next() % 2 == 0)
                        {
                            s.Add(random.Next());
                        }
                        else
                        {
                            s.Contains(random.Next());
                        }
                    }
                }
            },
            "Wintellect.PowerCollections.Set");
            
        InvokeTest(
            delegate
            {
                MyRandom random = new MyRandom();
                OrderedSet<int> s  = new OrderedSet<int>();
                for (int i = 0; i < N_ITERATIONS; i++)
                {
                    s.Clear();
                    for (int j = 0 ;j < N_OPS; j++)
                    {
                        if (random.Next() % 2 == 0)
                        {
                            s.Add(random.Next());
                        }
                        else
                        {
                            s.Contains(random.Next());
                        }
                    }
                }
            },
            "Wintellect.PowerCollections.OrderedSet");
    }
}

#include <set>
#include <hash_set>
#include <stdlib.h>
#include <time.h>

class MyRandom
{
    int seed;
    
public:    
    MyRandom()
        : seed(0)
    {
    }
    
    int Next()
    {
        seed = (int) (seed * 214013L + 2531011L);
        return (seed >> 16) & 0x7fff;
    }
};

const int N_OPS = 100;
const int N_ITERATIONS = 100000;


template <class T>
void InvokeTest(const T& tester, char* comment)
{
    int t1 = clock();    
    tester.Run();
    int t2 = clock();    
    int time = t2 - t1;
    printf("%-40s %10d\n", comment, time);
}


template <class S>
class Tester
{
public:
    void Run() const
    {
        S s;
        MyRandom random;
        
        for (int i = 0; i < N_ITERATIONS; i++)
        {
            s.clear();
            for (int j = 0 ;j < N_OPS; j++)
            {
                if (random.Next() % 2 == 0)
                {
                    s.insert(random.Next());
                }
                else
                {
                    s.find(random.Next());
                }
            }
        }
    }
};

int main()
{
    InvokeTest(Tester<std::set<int> >(), "std::set");
    InvokeTest(Tester<stdext::hash_set<int> >(), "stdext::hash_set");
}

public class A
{
    [XmlElement("ht")]
    public Hashtable _ht = new Hashtable();
    
    public A()
    {
        _ht.Add(1, "a");
        _ht.Add(2, "b");
        _ht.Add(3, "c");
    }
}

class Program
{
    static void Main(string[] args)
    {
        /*
        В этой строке получаем исключение.
        Cannot serialize member A._ht of type System.Collections.Hashtable, because it implements IDictionary.
        При использовании Dictionary<int, string> ситуация аналогичная.
        */
        XmlSerializer xs = new XmlSerializer(typeof(A));


        /* Сюда уже не доходит, я просто для полноты картины написал этот код */
        A a = new A();
        
        using (TextWriter tw = File.CreateText("test.xml"))
        {
            xs.Serialize(tw, a);
            tw.Close();
        }
    }
}

1. Индусы пишут в "operator <" вызов Sleep(1000); и поэтому он медленный
   
2. Роме слабо реализовать этот оператор для класса StateSet. Правда он в операторе switch представляется с трудом, но это не важно.

    public override int GetHashCode()
    {
        return 0;
    }

class Path
{
    public char Drive;
    public string Directory;
    public string Filename;
    public int Attributes;

    public override int GetHashCode()
    {
        int hash = 0;
        hash ^= Drive.GetHashCode();
        if (Directory != null)
            hash ^= Directory.GetHashCode();
        if (Filename != null)
            hash ^= Filename.GetHashCode();
        hash ^= Attributes.GetHashCode();
        return hash;
    }

    public override bool Equals(object obj)
    {
        Path path = obj as Path;
        if (path == null)
            return false;
        if (Drive != path.Drive)
            return false;
        if (Directory != path.Directory)
            return false;
        if (Filename != path.Filename)
            return false;
        if (Attributes != path.Attributes)
            return false;
        return true;
    }
}

    public bool Less(Path path)
    {
        if (path == null)
            return false;
        if (Drive < path.Drive)
            return true;
        if (Drive > path.Drive)
            return false;
        if (Directory < path.Directory)
            return true;
        if (Directory > path.Directory)
            return false;
        if (Filename < path.Filename)
            return true;
        if (Filename > path.Filename)
            return false;
        if (Attributes < path.Attributes)
            return true;
        if (Attributes > path.Attributes)
            return false;
        return false;
    }

public class A
{
    public int data = 3;
        
    public A()
    {
    }
}

A a1 = new A();
A a2 = new A();
            
int h1 = a1.GetHashCode();
int h2 = a2.GetHashCode();

A>>Ну предложи что-то своё. Только так, чтобы работало

class Path
{
    public char Drive;
    public string Directory;
    public string Filename;
    public int Attributes;

    public override int GetHashCode()
    {
        return
        /* Что тут надо написать, чтобы значения всех битов были равновероятны и независимы?
           Причём не в теории, где Drive от 0 до 255, а на практике. */;
    }
}

WH>Других идей что-то в голову не приходит

class A
{
 private string _s1;
 private string _s2;

 public override int GetHashCode()
 {
  return _s1.GetHashCode() ^ _s2.GetHashCode();
 }
}

WH>    public bool Less(Path path)
WH>    {
WH>        if (path == null)
WH>            return false;
WH>        if (Drive < path.Drive)
WH>            return true;
WH>        if (Drive > path.Drive)
WH>            return false;
WH>        if (Directory < path.Directory)
WH>            return true;
WH>        if (Directory > path.Directory)
WH>            return false;
WH>        if (Filename < path.Filename)
WH>            return true;
WH>        if (Filename > path.Filename)
WH>            return false;
WH>        if (Attributes < path.Attributes)
WH>            return true;
WH>        if (Attributes > path.Attributes)
WH>            return false;
WH>        return false;
WH>    }
WH>

Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net

A>Ты внимательно почитай о чём речь. Мы говорили не о коллекциях, а об операторе switch по любым объектам. Чтобы это было реализовано не абы как, а качественно, из констант после case надо построить двочное дерево поиска. А для этого надо сами эти константы упорядочить. Иначе switch ничем не будет отличаться от последовательности if, а нам такой switch не нужен!

void TestMethod(object obj)
{
    switch (obj)
    {
        case new Class1(someState1): SomeBehavior1() break;
        case new Class1(someState2): SomeBehavior2() break;
        case new Class1(someState3): SomeBehavior3() break;
        case new Class2(someState1): SomeBehavior4() break;
        default:                     SomeBehavior5() break;
    }
}

static Dictionary<object, int> _unic_comiler_name1;

void TestMethod(object obj)
{
    if (_unic_comiler_name1 == null)
    {
        // Инициализация хэш-таблицы используемой для реализации switch-а
        _unic_comiler_name1 = Dictionary<object, int>()
        
        _unic_comiler_name1.Add(new Class1(someState1), 1);
        _unic_comiler_name1.Add(new Class1(someState2), 2);
        _unic_comiler_name1.Add(new Class1(someState3), 3);
        _unic_comiler_name1.Add(new Class2(someState1), 4);
    }
    
    // Для подобных свитчей (с последовательными индексами)
    // компилятор генерирует оптимальный код (O(1)).
    
    int index;
    // Если ключа не будет в хэш-таблице, то будет возвращено значение "0".
    _unic_comiler_name1.TryGetValue(obj, out index)
    
    switch (index)
    {
        case 1:  SomeBehavior1() break;
        case 2:  SomeBehavior2() break;
        case 3:  SomeBehavior3() break;
        case 4:  SomeBehavior4() break;
        default: SomeBehavior5() break;
    }
}

using System;

class Program
{
    static void Main()
    {
        Test("A");
        Test("X");
    }

    static void Test(string str)
    {
        switch (str)
        {
            case "A": Console.WriteLine("str содержит 'A'"); break;
            case "B": Console.WriteLine("str содержит 'B'"); break;
            case "C": Console.WriteLine("str содержит 'C'"); break;
            case "D": Console.WriteLine("str содержит 'D'"); break;
            case "E": Console.WriteLine("str содержит 'E'"); break;
            case "F": Console.WriteLine("str содержит 'F'"); break;
            default: Console.WriteLine("str содержит что-то иное"); break;
                
        }
    }
}

private static void Test(string str)
{
      string text1 = str;
      if (text1 != null)
      {
            int num1;
            if (<PrivateImplementationDetails>{DC3A279F-4631-445B-A3D2-D9E0196B55E0}.$$method0x6000002-1 == null)
            {
                  Dictionary<string, int> dictionary1 = new Dictionary<string, int>(6);
                  dictionary1.Add("A", 0);
                  dictionary1.Add("B", 1);
                  dictionary1.Add("C", 2);
                  dictionary1.Add("D", 3);
                  dictionary1.Add("E", 4);
                  dictionary1.Add("F", 5);
                  <PrivateImplementationDetails>{DC3A279F-4631-445B-A3D2-D9E0196B55E0}.$$method0x6000002-1 = dictionary1;
            }
            if (<PrivateImplementationDetails>{DC3A279F-4631-445B-A3D2-D9E0196B55E0}.$$method0x6000002-1.TryGetValue((string) text1, ref (int) ref num1))
            {
                  switch (num1)
                  {
                        case 0:
                        {
                              Console.WriteLine("str \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 'A'");
                              return;
                        }
                        case 1:
                        {
                              Console.WriteLine("str \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 'B'");
                              return;
                        }
                        case 2:
                        {
                              Console.WriteLine("str \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 'C'");
                              return;
                        }
                        case 3:
                        {
                              Console.WriteLine("str \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 'D'");
                              return;
                        }
                        case 4:
                        {
                              Console.WriteLine("str \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 'E'");
                              return;
                        }
                        case 5:
                        {
                              Console.WriteLine("str \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 'F'");
                              return;
                        }
                  }
            }
      }
      Console.WriteLine("str \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0447\u0442\u043e-\u0442\u043e \u0438\u043d\u043e\u0435");
}

Суть в том, что классы реализующие IDictionary в частности, и коллекции вообще это проблема от которой надо избавляться, а не решать.

A>А что ты сможешь посчитать осмысленный хеш не перебрав все элементы множества?

pos = (h1(obj) + k*h2(obj)) mod M

A>Выходит проектировали сразу для плохой и хеш таблица заполненая меньше чем наполовину это норма?

Выходит проектировали сразу для плохой и хеш таблица заполненая меньше чем наполовину это норма?

Dictionary<string, List<MyType>> dic =...

bool T::operator < (T t);

A>А зачем ObjectIDGenerator реализовывать с помошью деревьев? Предположим, что нельзя/сложно, какое это отношение имеет к оператору switch?

Давайте думать есть ли случаи когда оператор < реализовать тяжело , а == легко.