computer science goes bonk / all posts / rss / about

what's in an enum?

Pop quiz, hotshot:

int main() {
  enum Result {
    LOSE = 0,
    WIN,
    DIE_TRYING
  } result;

  switch (result) { 
   case LOSE:
    break;
   case WIN:
    break;
   case DIE_TRYING:
    break;
   default:
    // can't get here?
  }
}

How many possible values can result hold?

...

The answer, of course, is four. In addition to LOSE, WIN, and DIE_TRYING, WIN | DIE_TRYING is a valid value for result.

A rule of thumb is that enums can hold any value that fits into the smallest bit pattern required by the enum. Since the Result enum needs two bits to store 00b, 01b, and 10b, one valid value is 11b, a.k.a. WIN | DIE_TRYING.


a type by any other name

There are only two hard problems in computer science:

  1. naming things,
  2. cache invalidation, and
  3. off-by-one errors.

This is a post about naming things. Consider the following code:

template <typename T>
void foo() {
  T::iterator it;
}

int main() {}

Will this code compile?

No, because the compiler doesn't know that T::iterator refers to a type.

How do I fix it?

You need to use the typename keyword, like so:

template <typename T>
void foo() {
  typename T::iterator it;
}

int main() {}

Why is typename necessary?

T::iterator is called a dependent name, because it depends on what T is. Most of the time, dependent names in templates are not assumed to be types.

Why can't the compiler assume this dependent name is a type?

Because T::iterator might not refer to a type. Here's an example of a potential T where T::iterator isn't a type:

struct Bar {
  static int iterator;
};

Why can't the compiler figure out which names refer to types automatically?

Because the template definition might work either way -- with T::iterator as a type or with T::iterator as a variable:

int b;

template <typename T>
void baz() {
  T::iterator *b;
}

In the above code, does the body of baz:

  • declare a variable named b that is a pointer to the type T::iterator, or
  • multiply the global variable b with the static variable T::iterator, and ignore the result?

If all we've seen is the template, we don't know. It could be either.

Why doesn't the compiler delay processing the template definition until it sees an instantiation?

Good question. Here are some reasons why the compiler parses template definitions when it sees them:

  • It allows the compiler to generate errors sooner.

  • If the compiler waited until it saw an instantiation, it would have to decide if code that appears between definition and instantiation could be used in the template. For example, a better match for an overloaded function call might be introduced -- should it be ignored?

  • Worst of all, different instantiations of the ambiguous template above would mean the same chunk of code could produce totally different parse trees, which seems unlikely to match programmer intent.

My head hurts.

TL;DR: Use the typename keyword with dependent names in templates to indicate those names are types.


explicit out-parameters

Can we have C#-style explicit outparams in C++? elcapaldo showed me a neat approach last week that I'll try to reproduce here. (Of course Logan supplied the cool stuff; any errors are all mine.)

How it looks in C#

In C#, everything defaults to pass-by-value. If you want to be able to modify an argument to a method, you have to attach either a ref or out modifier to the argument at both the method definition and at each call site:

// 'value' is marked as an outparam
public bool TryGetValue(string key, out string value) { ... }

public void SomeMethod()
{
  string value;
  if (TryGetValue("bar", out value))   // 'value' must be marked as an outparam
  {
    ...
  }
}

The out keyword implies a number of things, but the most noticeable effect is that consumers of methods with outparams have to explicitly acknowledge that they're using outparams.

Can we do something similar in C++?

How it looks in C++

Consider the following definition of the Out type, along with a couple of helper functions named out:

// parameters of type T can be passed as type Out<T>
template <typename T>
class Out {
private:
  struct OutRefHolder {
    T &ref_;
    explicit OutRefHolder(T &ref) : ref_(ref) {}
  };

public:
  Out(OutRefHolder &&oref) : ref_(oref.ref_) {}
  Out(Out &&o) : ref_(o.ref_) {}
  Out(const Out&) = delete;
  Out() = delete;

  template <typename Q>
  void operator=(Q &&q) {
    ref_ = std::forward<Q>(q);
  }

  template <typename Y>
  friend typename Out<Y>::OutRefHolder out(Y &ref);
  template <typename Y>
  friend typename Out<Y>::OutRefHolder out(Out<Y> &o);

private:
  T &ref_;
};

// helper functions to create something convertible to an Out<Y>
template <typename Y>
typename Out<Y>::OutRefHolder out(Y &ref) {
  return typename Out<Y>::OutRefHolder(ref);
}
template <typename Y>
typename Out<Y>::OutRefHolder out(Out<Y> &o) {
  return typename Out<Y>::OutRefHolder(o.ref_);
}

Given that definition, we can use the Out type and the out functions like so:

#include <iostream>
#include <string>
#include "Out.h"

bool get_prop(const std::string &key, Out<std::string> value) {
  if (key == "keymaster") {
    value = "gatekeeper";
    return true;
  }
  return false;
}

int main() {
  std::string value;
  if (get_prop("keymaster", out(value))) {
    std::cout << value << '\n';  // displays "gatekeeper"
  }
}

The definition of Out makes it hard to mis-use: an Out<T> isn't copyable and isn't easy to create, except indirectly via the out functions.

The result: if you write functions that take an Out<T>, the easiest path by far forces people to explicitly acknowledge that they're passing an outparam. Just like C#.


get yer filthy hands off my control block

Exposition

Yesterday, Logan pointed out that you can construct a shared_ptr<T> that manages some T but shares a control block with some completely different shared_ptr<U>:

template <typename T> class shared_ptr {
public:
  // constructs a shared_ptr that shares ownership with r and stores p
  template<typename U> shared_ptr(shared_ptr<U> const &r, T *p);
  // ...
};

This is a pretty cool use of shared_ptr that I had not seen before.

A Compelling Example

Say you have two objects -- one nested inside the other -- that need to be able to refer to eachother. If you give each object a shared_ptr to the other object, they'll leak-lock eachother until your program dies of consumption. You could break the symmetry by giving one a weak_ptr to the other, but then you run the risk of one object expiring before the other.

What we really want is both objects to stay alive as long as either is around:

#include <memory>
#include <iostream>

struct Foo;

struct Bar {
  Bar(Foo *f) : foo(f) { std::cout << "Bar\n"; }
  ~Bar() { std::cout << "~Bar\n"; }
  // goal: this Foo should be valid as long as this Bar is alive
  Foo *foo;
};

struct Foo : std::enable_shared_from_this<Foo> {
  Foo() : bar(new Bar(this)) { std::cout << "Foo\n"; }
  ~Foo() { std::cout << "~Foo\n"; }
  // give someone access to our Bar
  std::shared_ptr<Bar> getBar() {
    return std::shared_ptr<Bar>(shared_from_this(), bar.get());
  }
  std::unique_ptr<Bar> bar;
};

int main() {
  std::shared_ptr<Bar> bar;
  {
    std::shared_ptr<Foo> foo(new Foo);
    bar = foo->getBar();
  }
  std::cout << "foo is dead now...or is it?\n";
}

When run, the above code produces the following output:

Bar
Foo
foo is dead now...or is it?
~Foo
~Bar

The Thrilling Conclusion

By attaching the shared_ptr<Bar> to the control block for the shared_ptr<Foo>, we can enforce the idea that if we grab a Bar from a Foo, the Foo will live at least as long as the Bar does.


std::is_array and std::extent in C++11

Rats.

#include <iostream>
#include <type_traits>

void foo(int arr[]);

int main() {
  int arr[10] = {0};

  std::cout 
    << std::boolalpha                      // output:
    << std::is_array<decltype(arr)>::value //  true
    << ' '
    << std::extent<decltype(arr)>::value   //  10
    << '\n';

  foo(arr);
}

void foo(int arr[]) {
  std::cout 
    << std::boolalpha                      // output:
    << std::is_array<decltype(arr)>::value //  false
    << ' '
    << std::extent<decltype(arr)>::value   //  0
    << '\n';
}

(A little background reading)


Next Page ยป