2012-02-20 37 views
5

Tôi hiện đang làm việc trên một cách đơn giản để thực hiện cấu trúc cây xâm nhập trong C#. Vì tôi chủ yếu là một lập trình viên C++, tôi lập tức muốn sử dụng CRTP. Đây là mã của tôi:C# - Cấu trúc cây xâm nhập, sử dụng CRTP

public class TreeNode<T> where T : TreeNode<T> 
{ 
    public void AddChild(T a_node) 
    { 
     a_node.SetParent((T)this); // This is the part I hate 
    } 

    void SetParent(T a_parent) 
    { 
     m_parent = a_parent; 
    } 

    T m_parent; 
} 

này hoạt động nhưng ... Tôi không thể hiểu tại sao tôi phải bỏ khi gọi a_node.SetParent ((T) này), như tôi đang sử dụng hạn chế loại generic .. C# cast có chi phí và tôi không muốn truyền dàn diễn viên này trong mỗi lần triển khai thu thập xâm nhập ...

+0

Tôi cho phép bản thân mình đơn giản hóa ví dụ của bạn. Vui lòng hoàn nguyên nếu bạn không đồng ý. – usr

+1

Thành thật mà nói, điều này trông giống như một headf thông minh ** k. Có gì sai với các cách truyền thống hơn để đại diện cho cây sử dụng bố cục thay thế? Điều này làm bạn mua gì? Tôi hy vọng rằng không có vẻ quá đối kháng. Tôi chỉ tò mò thôi. – spender

+0

@spender phân nửa số lượng phân bổ và giảm số lượng người theo dõi bạn cần tuân theo. Vì vậy, trong mã hiệu suất cao, nó có thể là một sự cân bằng hợp lý. Đối với những cây nhỏ hơn, đó có lẽ là một ý tưởng tồi. – CodesInChaos

Trả lời

3

đây là loại TreeNode ít nhất. Nó có thể được bắt nguồn hoặc nó có thể chính xác TreeNode. SetParent mong đợi một T. Nhưng T có thể là một kiểu khác với cái này. Chúng ta biết rằng điều này và T đều xuất phát từ TreeNode nhưng chúng có thể là các kiểu khác nhau.

Ví dụ:

class A : TreeNode<A> { } 
new TreeNode<A>() //'this' is of type 'TreeNode<A>' but required is type 'A' 
0

Không ai đảm bảo rằng T và loại this đều giống nhau. Họ thậm chí có thể là các lớp con không liên quan của TreeNode.

Bạn mong đợi T được sử dụng trong mẫu mẫu tò mò định kỳ, nhưng các ràng buộc chung không thể diễn tả điều đó.

Việc triển khai ngu ngốc có thể được định nghĩa là StupidNode:TreeNode<OtherNode>.

0

Vấn đề là với dòng này:

TreeNode<T> where T : TreeNode<T> 

T là một TreeNode là một định nghĩa đệ quy nó không thể được xác định trước biên dịch hoặc thậm chí tĩnh kiểm tra. Không sử dụng mẫu, hoặc nếu bạn làm bạn cần phải cấu trúc lại & tách các nút từ payload (Tức là dữ liệu nút từ nút chính nó.)

public class TreeNode<TPayload> 
{ 
    TPayload NodeStateInfo{get;set;} 

    public void AddChild(TreeNode<TPayload> a_node) 
    { 
     a_node.SetParent(this); // This is the part I hate 
    } 

    void SetParent(TreeNode<TPayload> a_parent) 
    { 
    } 
} 

Ngoài ra tôi không chắc chắn lý do tại sao bạn đang gọi điện thoại a_node .SetParent (điều này). Có vẻ như AddChild được đặt tên khéo léo hơn là SetParent, vì bạn đang thiết lập cá thể này làm cha mẹ của a_node. Có thể đó là một số thuật toán bí truyền mà tôi không quen thuộc, nếu không nó không có vẻ đúng.

+0

Trong khi các bộ sưu tập dựa trên thành phần thường là một ý tưởng tốt hơn, các bộ sưu tập xâm nhập có vị trí của chúng. 'TreeNode trong đó T: TreeNode ' ràng buộc có ý nghĩa trong ngữ cảnh này. Nó có thể được hài lòng bởi mẫu mẫu tò mò định kỳ. Việc thực hiện 'AddChild' cũng tốt cho tôi. Trong một cây, bạn hoặc thực hiện 'SetParent' hoặc' AddChild' một cách rõ ràng, và sau đó làm cho một cái khác gọi cái mà bạn đã thực hiện. – CodesInChaos

0

Hãy xem xét những gì sẽ xảy ra nếu chúng ta đi chệch khỏi ước CRTP bằng cách viết ...

public class Foo : TreeNode<Foo> 
{ 
} 

public class Bar : TreeNode<Foo> // parting from convention 
{ 
} 

... và sau đó gọi các mã trên như sau:

var foo = new Foo(); 
var foobar = new Bar(); 
foobar.AddChild(foo); 

Cuộc gọi AddChild ném một InvalidCastException nói Unable to cast object of type 'Bar' to type 'Foo'.

Về thành ngữ CRTP - đó là quy ước một mình yêu cầu loại chung phải giống như khai báo ing. Ngôn ngữ phải hỗ trợ các trường hợp khác không tuân theo quy ước CRTP. Eric Lippert đã viết một bài đăng trên blog tuyệt vời về chủ đề này, rằng anh ta đã liên kết với nhau từ crtp via c# answer khác.

Tất cả những gì đã nói, nếu bạn thay đổi việc thực hiện điều này ...

public class TreeNode<T> where T : TreeNode<T> 
{ 
    public void AddChild(T a_node) 
    { 
     a_node.SetParent(this); 
    } 

    void SetParent(TreeNode<T> a_parent) 
    { 
     m_parent = a_parent; 
    } 

    TreeNode<T> m_parent; 
} 

... các mã trên mà trước đây ném InvalidCastException hiện đang làm việc.Thay đổi này làm cho m_Parent một loại TreeNode<T>; làm this một trong hai loại T như trong Foo lớp trường hợp hoặc một lớp con của TreeNode<T> trong trường hợp Bar lớp từ Bar thừa hưởng từ TreeNode<Foo> - một trong hai cách cho phép chúng ta bỏ qua các diễn viên trong SetParent và thiếu sót mà tránh được những ngoại lệ cast không hợp lệ kể từ khi nhiệm vụ là hợp pháp trong mọi trường hợp. Chi phí thực hiện việc này không còn có thể tự do sử dụng T ở tất cả các địa điểm như trước đây đã được sử dụng để hy sinh phần lớn giá trị của CRTP.

Một đồng nghiệp/bạn của tôi coi mình là một người mới đến một ngôn ngữ/ngôn ngữ-tính năng cho đến khi anh ta có thể thành thật nói rằng anh ấy "đã sử dụng nó trong giận dữ;" đó là, anh ta biết ngôn ngữ đủ tốt để bị thất vọng rằng không có cách nào để hoàn thành những gì anh ta cần hoặc làm như vậy là đau đớn. Điều này rất tốt có thể là một trong những trường hợp đó, vì có những giới hạn và sự khác biệt ở đây để lặp lại sự thật là generics are not templates.

0

Khi bạn đang làm việc với các loại tham chiếu và bạn biết thực tế rằng diễn viên của bạn dọc theo phân cấp loại sẽ thành công (không có truyền tùy chỉnh ở đây), thì không cần thực sự truyền bất kỳ thứ gì. Giá trị của số nguyên tham chiếu là giống nhau trước và sau khi truyền, vậy tại sao không chỉ bỏ qua các diễn viên?

Điều đó có nghĩa là bạn có thể viết phương thức AddChild bị coi thường này trong CIL/MSIL. Phương thức mã cơ thể của phương thức như sau:

ldarg.1 
ldarg.0 
stfld TreeNode<class T>::m_parent 
ret 

.NET sẽ không quan tâm đến tất cả những gì bạn không truyền giá trị. Các Jitter dường như chỉ quan tâm đến kích thước của các cửa hàng là phù hợp, mà họ luôn luôn là để tham khảo.

Tải phần mở rộng Hỗ trợ IL cho Visual Studio (có thể phải mở tệp vsix và sửa đổi phiên bản được hỗ trợ) và khai báo phương thức C# là extern với thuộc tính MethodImpl.ForwardRef. Sau đó, chỉ cần khai báo lại lớp trong tệp .il và thêm phương thức triển khai thực hiện mà bạn cần, phần thân được cung cấp ở trên.

Lưu ý rằng điều này cũng theo cách thủ công phương thức SetParent của bạn vào AddChild.

Các vấn đề liên quan