```
auto deleter = [](wchar_t *memory) { /* omitted */ };
std::unique_ptr<wchar_t, decltype(deleter)> var(L"Hello, World.");
```

In VC++2015, it doesn't. Why?

Well it's pretty clear why from the error message: the std::unique_ptr constructor is going to construct a

]]>```
auto deleter = [](wchar_t *memory) { /* omitted */ };
std::unique_ptr<wchar_t, decltype(deleter)> var(L"Hello, World.");
```

In VC++2015, it doesn't. Why?

Well it's pretty clear why from the error message: the std::unique_ptr constructor is going to construct a new instance of the second type argument to use as the deleter for the held pointer, and that type, being a lambda, can't be constructed because it doesn't (or shouldn't, rather) have a visible constructor.

Does this mean that the VC++2013 compiler generates lambda with public constructors? Not exactly.

For example, consider the following function:

```
#include <iostream>
#include <typeinfo>
template<typename T>
T make_it()
{
T var = T();
return var;
}
```

We would expect the following code to compile just fine under VC++2013 and VC++2015; and we'd be right, this is perfectly legal.

```
int main()
{
auto instance = make_it<wchar_t>();
std::cout << typeid(instance).name() << std::endl;
return 0;
}
```

Running this produces the following output:

```
wchar_t
```

If VC++2013 was improperly generating constructors for lambda types, we would expect this code to succeed under VC++2013... but it doesn't!

```
int main()
{
auto lambda = []() {};
auto instance = make_it<decltype(lambda)>();
std::cout << typeid(instance).name() << std::endl;
return 0;
}
```

VC++2013 *also* complains about not being able to construct an instance of a lambda, just as it should!

So why did my code suddenly start breaking under VC++2015 when it compiled and executed just fine under VC++2013?

Because I wasn't making an explicit constructor call; in reality, my deleter type was getting created in a manner that is more accurately represented by this version of my make_it function:

```
template<typename T>
T make_it()
{
T var;
return var;
}
```

In VC++2013, ~~constructing a lambda on the stack is perfectly acceptable (this is the bug)~~ lambdas *appear* to be constructible when invoking the default constructor, but if the construction pattern would involve the use of the copy constructor, it's disallowed.

In VC++2015, it looks like they fixed it. Which led to some very confusing compiler errors that took a few minutes to realize what was going on. :)

Mad props to Cody Miller of the C++ team for helping me figure out what was going on here.

]]>It just so happens that I know that the first four bytes sent over the pipe is an integer (because of a previously agreed upon protocol), and it just so happens that I

]]>It just so happens that I know that the first four bytes sent over the pipe is an integer (because of a previously agreed upon protocol), and it just so happens that I really need that to be an integer, and not a unsigned char[4] (which is what I have).

So I wrote the following code, because I am Smart and Attractive:

```
int i = (i << 8) + arr[0];
i = (i << 8) + arr[1];
i = (i << 8) + arr[2];
i = (i << 8) + arr[3];
```

And immediately realized that I had managed to convert my four bytes into an integer by interpreting the bytes as being encoded in big-endian, where it was actually four bytes encoded in little-endian (the other side of the named pipe is running on the same machine).

Okay, so that’s an easy fix:

```
int i = (i << 8) + arr[3];
i = (i << 8) + arr[2];
i = (i << 8) + arr[1];
i = (i << 8) + arr[0];
```

Success, I am incredible.

BUT WAIT! What if some hypothetical future revision of my thing runs on a processor that is BIG ENDIAN – in this case, I might actually screw up the endianness the other direction!

NOTE: This is where the navel gazing comes in.

Okay! So. What’s the best way to portably define a byte-array -> integer conversion function. The first thing that came to mind was to mutter an expletive and define a union:

```
union byteint {
unsigned char bytes[4];
int integer;
} b;
b.bytes = arr;
...
```

But then I thought that they are all going to make fun of me for doing it that way, that there is a better way and if only I could know this way, my life would be much improved.

Can you think of a Better Way™?

I tossed this out to a few coworkers of mine, Cody and Zac. It took them but a moment to point that reinterpret_cast<>() could be used and should be completely portable, avoiding the need for a union.

In my defense, I had considered reinterpret_cast but immediately felt shame for thinking of it and its conjurers ways. Unconscious bias, I guess.

]]>It's a Jeep Thing. You wouldn't understand.

Of course I understand. I'm a software engineer, and am therefore very familiar with subjective elitism.

]]>It's a Jeep Thing. You wouldn't understand.

Of course I understand. I'm a software engineer, and am therefore very familiar with subjective elitism.

]]>*Let's implement a Binary Search Tree**Let's implement a Binary Search Tree, Part II**Let's implement a Binary Search Tree, Part III**Let's implement a Binary Search Tree, Part IV*

What keeps occurring to me about the BST implementation to this point,

]]>*Let's implement a Binary Search Tree**Let's implement a Binary Search Tree, Part II**Let's implement a Binary Search Tree, Part III**Let's implement a Binary Search Tree, Part IV*

What keeps occurring to me about the BST implementation to this point, is that it looks an awful lot like a dictionary. Consider:

- We have keys.
- We have values.
- You can get values using the key.
- You can't have the same key twice.

Remarkably like a dictionary. Wouldn't it be nice if our BST implementation was an implementation detail of a IDictionary

In order for that to work, though, our key - currently, an integer - would need to be comparable. Comparison would also need to be *cheap*, so while it might be attractive to, say, use a hashing function over each key, given the number of times we're comparing things, that would be terribly effective.

The other question is, do we need the key to be comparable *by value* or *by reference*?

```
FooBar f = new FooBar() { AProperty = 123; BProperty = 321; }
FooBar f1 = new FooBar() { AProperty = 123; BProperty = 321; }
...
myBst[f] = "A Value";
myBst[f1] = "Another Value";
```

In the example above, myBst[f] and myBst[f1] point to different values, but the keys are bitwise equivalent - but not reference equivalent. They are at different addresses in memory.

But wait. Is this a problem?

Well, it turns out yes, it is. FooBar doesn't implement greater than / less than operators. The Equals operators is determining reference equivalence, but there is no concept of greater than / less than comparison on this type.

We can implement those operators easily enough:

```
public static bool operator <(FooBar firstType, FooBar otherType)
{
...
}
public static bool operator >(FooBar firstType, FooBar otherType)
{
...
}
```

But can we enforce this as a type constraint? We can't require our keys all implement a particular custom interface of our design - operators are static, and static methods can't be defined in an interface. And even if they could be, that'd be a terrible idea, because you'd have to re-implement or specialize all the existing types that *are* perfectly comparable, like Int32, because it doesn't implement our custom-special interface.

What about IComparable?

Let's see:

- It defines a CompareTo method that returns a value indicating if something is equal to, less than, or greater than.
- It's defined on all the intrinsic built in types - int, double, string, etc.

Yes. I think that'd do nicely.

Next up - updated implementation, and by popular request, a GitHub repo for our little implementation.

]]>*Let's implement a Binary Search Tree**Let's implement a Binary Search Tree, Part II**Let's implement a Binary Search Tree, Part III*

To this point, we've implement addition, removal, and search.

At this point, I was going to implement a series of

]]>*Let's implement a Binary Search Tree**Let's implement a Binary Search Tree, Part II**Let's implement a Binary Search Tree, Part III*

To this point, we've implement addition, removal, and search.

At this point, I was going to implement a series of tests, but I think I'll wait for a later post to cover that. Let's clean up our implementation a bit instead.

Notice that to this point, Node has been declared public:

```
public class Node
{
...
}
```

Node, though, is an implementation detail. When you call Search(), you don't get back a Node, you get a bool indicating the result of your search and an out param pointing at the found value.

Let's make Node a private to the BinarySearchTree class:

```
public class BinarySearchTree
{
private class Node
{
...
}
...
}
```

Excellent. Now our implementation detail is hidden from view.

Something else that's bothered me; our implementation stores values as *object*. This is handy, since any managed type can be referenced or boxed as an object reference, but is less handy since dealing with this means the caller is likely going to have to do a lot of casting for no real reason.

It's likely a safe assumption that any given instance of our binary search tree is *type consistent on the stored value* - i.e. every node contains a different value and key, but the *type* of each value is the same.

Let's implement a generic form of our BinarySearchTree.

The modifications are many, but fairly straightforward. Essentially, BinarySearchTree now requires a type parameter, as does Node; any type we initialize a default value for our Node value, previously we used *null*, but since we aren't constraining our type parameter to a nullable type (a BST of integers is perfectly legit), we'll used default(T) to get an appropriate default value in those cases.

Complete code listing:

```
public class BinarySearchTree<T>
{
Node<T> _root;
public bool Add(int key, T value)
{
if (null == _root)
{
_root = new Node<T>()
{
Key = key,
Value = value
};
return true;
}
return _root.Add(key, value);
}
public bool Remove(int key)
{
bool returnValue;
if (null == _root)
returnValue = false;
else if (_root.Key == key)
{
Node<T> temporaryRoot = new Node<T> { Left = _root };
// Parent the current root node by our temporary root
returnValue = _root.Remove(key, temporaryRoot);
_root = temporaryRoot.Left;
}
else
{
returnValue = _root.Remove(key, null);
}
return returnValue;
}
public bool Search(int searchKey, out T value)
{
value = default(T);
return _root != null && _root.Search(searchKey, out value);
}
private class Node<TValue>
{
public Node<TValue> Left { get; set; }
public Node<TValue> Right { get; set; }
public TValue Value { get; set; }
public int Key { get; set; }
public Node<TValue> FindMinimum()
{
return null == Left ? this : Left.FindMinimum();
}
public bool Remove(int key, Node<TValue> parent)
{
if (Key < key)
{
return Left != null && Left.Remove(key, this);
}
if (Key > key)
{
return Right != null && Right.Remove(key, this);
}
if (Key == key)
{
if (Left != null && Right != null)
{
// We have two children
Node<TValue> minNode = Left.FindMinimum();
Key = minNode.Key;
Value = minNode.Value;
// Remove "ourselves" from the right subtree branch.
Left.Remove(Key, this);
}
else if (parent.Left == this)
{
// We're on the left side of our parent - meaning our key is greater than our parent
// Set our parents left key to our left key if we have one, otherwise, set it to our right key
parent.Left = Left ?? Right;
}
else if (parent.Right == this)
{
// We're on the right side of our parent - meaning our key is less than our parent
// Set our parents right key to our right key if we have one, otherwise, set it to our left key.
parent.Right = Right ?? Left;
}
return true;
}
throw new InvalidOperationException("Something horrible happened!");
}
public bool Search(int searchKey, out TValue value)
{
value = default(TValue);
if (Key == searchKey)
{
value = Value;
// Hey! It's us!
return true;
}
if (Key < searchKey)
{
if (Left == null)
{
return false;
}
return Left.Search(searchKey, out value);
}
if (Key > searchKey)
{
if (Right == null)
{
return false;
}
return Right.Search(searchKey, out value);
}
throw new InvalidOperationException("Something horrible happened!");
}
public bool Add(int key, TValue value)
{
if (this.Key == key)
return false; // Cannot add the same key twice
if (this.Key < key)
{
// The specified key is less than the current key; place node on the left of this node
if (null == Left)
{
Left = new Node<TValue>()
{
Key = key,
Value = value
};
return true;
}
else
{
// Left already has a node.
return Left.Add(key, value);
}
}
else if (Key > key)
{
// The specified key is more than the current key; place node on the right of this node
if (null == Right)
{
Right = new Node<TValue>()
{
Key = key,
Value = value
};
return true;
}
else
{
// Right already has a node.
return Right.Add(key, value);
}
}
throw new InvalidOperationException("Something horrible happened.");
}
}
}
```

Next up, let's take a look at the standard .NET container interfaces; wouldn't it be handy if the fact our binary search tree was a binary search tree was nothing more than an implementation detail?

]]>*For part two, see Let's implement a Binary Search Tree, Part II*

At this point in the series, we've defined our base tree structure and node structure, and implemented the necessary methods to implement additions to our tree and searches

]]>*For part two, see Let's implement a Binary Search Tree, Part II*

At this point in the series, we've defined our base tree structure and node structure, and implemented the necessary methods to implement additions to our tree and searches on our tree. (see Part I or Part II for a code listing),

Let's implement deletion.

At first blush, this might not seem to be a big deal, but in fact deletion in a binary search tree is a bit more involved that the other operations we've looked at to this point. Each node in our tree can have two children, but only one parent; therefore, in the case where the node we want to delete has multiple children, we've got a problem. Consider the following tree:

Note that in our implementation, left values are always increasing in value, while right values are always decreasing in value from any node. For example, consider node 15 - we know by definition, that no values larger than 15 will exist on the right side of the subtree formed by node 15's children; we also know that no values lower than 15's parent will exist on the right side 15's node. By definition, node 15's right side children must be less than 15, greater than 10, and less than the node 15's left side node (20).

As a result, we'll find the *smallest value* on the left side of node 15's children, and use that as our replacement node. The smallest value on the left side of the node will maintain our desired properties of our tree.

```
public Node FindMinimum()
{
return null == Left ? this : Left.FindMinimum();
}
```

Now that we can find the minimum value node for any subtree, let's implement deletion.

First up, let's handle deletion in the tree itself.

```
public bool Remove(int key)
{
bool returnValue;
if (null == _root)
returnValue = false;
else if (_root.Key == key)
{
Node temporaryRoot = new Node { Left = _root };
// Parent the current root node by our temporary root
returnValue = _root.Remove(key, temporaryRoot);
_root = temporaryRoot.Left;
}
else
{
returnValue = _root.Remove(key, null);
}
return returnValue;
}
```

Now, let's implement removal within the nodes themselves.

```
public bool Remove(int key, Node parent)
{
if (Key < key)
{
return Left != null && Left.Remove(key, this);
}
if (Key > key)
{
return Right != null && Right.Remove(key, this);
}
if (Key == key)
{
if (Left != null && Right != null)
{
// We have two children
Node minNode = Left.FindMinimum();
Key = minNode.Key;
Value = minNode.Value;
// Remove "ourselves" from the right subtree branch.
Left.Remove(Key, this);
}
else if (parent.Left == this)
{
// We're on the left side of our parent - meaning our key is greater than our parent
// Set our parents left key to our left key if we have one, otherwise, set it to our right key
parent.Left = Left ?? Right;
}
else if (parent.Right == this)
{
// We're on the right side of our parent - meaning our key is less than our parent
// Set our parents right key to our right key if we have one, otherwise, set it to our left key.
parent.Right = Right ?? Left;
}
return true;
}
throw new InvalidOperationException("Something horrible happened!");
}
```

Let's try it out.

```
static void Main(string[] args)
{
var bst = new BinarySearchTree();
bst.Add(10, "ten");
bst.Add(15, "fifteeen");
bst.Add(5, "five");
bst.Add(20, "twenty");
bst.Add(12, "twelve");
bst.Add(13, "thirteen");
bst.Add(11, "eleven");
bst.Print();
Console.WriteLine("Removing node 15...");
// Delete node 15
bst.Remove(15);
// Tree should now have now have
// a root of 10, with a right child of 5 and
// a left child of 20, with a right child of 12
bst.Print();
}
```

This produces an output of:

```
10
5
15
12
11
13
20
Removing node 15...
10
5
20
12
11
13
```

Looks good.

Next up, let's implement traversal / enumeration of the tree, and start thinking about tests.

*The following code is the code used to print the tree; it's not terribly interesting, and we won't be including it in our finished implementation only because it's only useful for the ad-hoc testing we're doing for this particular post.*

On the tree itself:

```
public void Print()
{
if (_root != null)
{
_root.Print();
}
}
```

On the node:

```
public void Print()
{
Console.WriteLine(Key);
if (Right != null)
{
Right.Print();
}
if (Left != null)
{
Left.Print();
}
}
```

]]>Last up, we defined our tree:

```
public class BinarySearchTree
{
Node _root;
public bool Add(int key, object value)
{
if (null == _root)
{
_root = new Node()
{
Key = key,
Value = value
};
return true;
}
return _root.Add(key, value);
}
}
```

And our tree would

]]>Last up, we defined our tree:

```
public class BinarySearchTree
{
Node _root;
public bool Add(int key, object value)
{
if (null == _root)
{
_root = new Node()
{
Key = key,
Value = value
};
return true;
}
return _root.Add(key, value);
}
}
```

And our tree would contain nodes:

```
public class Node
{
public Node Left { get; set; }
public Node Right { get; set; }
public object Value { get; set; }
public int Key { get; set; }
public bool Add(int key, object value)
{
if (this.Key == key)
return false; // Cannot add the same key twice
if (this.Key < key)
{
// The specified key is less than the current key; place node on the left of this node
if (null == Left)
{
Left = new Node()
{
Key = key,
Value = value
};
return true;
}
else
{
// Left already has a node.
return Left.Add(key, value);
}
}
else if (Key > key)
{
// The specified key is more than the current key; place node on the right of this node
if (null == Right)
{
Right = new Node()
{
Key = key,
Value = value
};
return true;
}
else
{
// Right already has a node.
return Right.Add(key, value);
}
}
throw new InvalidOperationException("Something horrible happened.");
}
}
```

Let's implement searching.

Let's define a search method on our node class that'll be called recursively:

```
public bool Search(int searchKey, out object value)
{
value = null;
if (Key == searchKey)
{
value = Value;
// Hey! It's us!
return true;
}
if (Key < searchKey)
{
if (Left == null)
{
return false;
}
return Left.Search(searchKey, out value);
}
if (Key > searchKey)
{
if (Right == null)
{
return false;
}
return Right.Search(searchKey, out value);
}
throw new InvalidOperationException("Something horrible happened!");
}
```

Now, let's implement search on the tree itself to kick things off.

```
public bool Search(int searchKey, out object value)
{
value = null;
return _root != null && _root.Search(searchKey, out value);
}
```

When the user calls Search(...) on our BST object, we'll kick off a call to the root node's Search(...) method if it's not null. If it is null, we'll just return false. Each node will check to see if it matches the desired searchKey - if it does, it'll return true, and set the value out parameter equal to the object stored on that node.

Let's try it out.

```
class Program
{
static void Main(string[] args)
{
var bst = new BinarySearchTree();
bst.Add(1, "one");
bst.Add(45, "forty-five");
bst.Add(13, "thirteen");
bst.Add(33, "thirty-three");
object foundValue = null;
bst.Search(33, out foundValue);
Console.WriteLine("Found Value: {0}", foundValue);
bst.Search(1, out foundValue);
Console.WriteLine("Found Value: {0}", foundValue);
bst.Search(13, out foundValue);
Console.WriteLine("Found Value: {0}", foundValue);
bst.Search(45, out foundValue);
Console.WriteLine("Found Value: {0}", foundValue);
}
}
```

Our labors now produce the following output:

```
Found Value: thirty-three
Found Value: one
Found Value: thirteen
Found Value: forty-five
```

Looks perfect.

Next up, we'll implement the slightly more complex gesture of **deletion** followed by tests.

Let's implement one from scratch.

First, we need a class to represent each node in our tree.

```
public class Node
{
public Node Left { get; set; }
public Node
```

]]>Let's implement one from scratch.

First, we need a class to represent each node in our tree.

```
public class Node
{
public Node Left { get; set; }
public Node Right { get; set; }
public object Value { get; set; }
public int Key { get; set; }
}
```

For my implementation, I want to be able to add arbitrary objects to my tree; therefore, I'm segregating the object reference stored from the key used to order it.

Let's implement the skeleton of the tree itself.

```
public class BinarySearchTree
{
Node _root;
public bool Add(int key, object value)
{
if (null == _root)
{
_root = new Node()
{
Key = key,
Value = value
};
return true;
}
return _root.Add(key, value);
}
}
```

We'll need an Add() method on our Node class; let's add that.

```
public bool Add(int key, object value)
{
if (this.Key == key)
return false; // Cannot add the same key twice
if (this.Key < key)
{
// The specified key is less than the current key; place node on the left of this node
if (null == Left)
{
Left = new Node()
{
Key = key,
Value = value
};
return true;
}
else
{
// Left already has a node.
return Left.Add(key, value);
}
}
else if (Key > key)
{
// The specified key is more than the current key; place node on the right of this node
if (null == Right)
{
Right = new Node()
{
Key = key,
Value = value
};
return true;
}
else
{
// Right already has a node.
return Right.Add(key, value);
}
}
throw new InvalidOperationException("Something horrible happened.");
}
```

Note the last line - we're handling all cases of possible key comparisons for the passed key and current node's key, so if we actually manage to fail all the provided comparisons and reach the end of the method, something horrible happened.

In all likelihood, the horrible thing that happened was someone attempted to manipulate our BST implementation from multiple threads simultaneously. Our implementation isn't thread-safe. That's future-post fodder.

Okay, we can Add nodes. Let's give it a spin.

```
static void Main(string[] args)
{
var bst = new BinarySearchTree();
bst.Add(1, "one");
bst.Add(45, "forty-five");
bst.Add(13, "thirteen");
bst.Add(33, "thirty-three");
}
```

At the end of this, we should wind up with a tree that looks like:

Next up, we'll implement searching, deletion, and tests to verify that our tree behaves correctly.

]]>