Memory isn't the issue. Both factors and string vectors only store each unique string once in memory. The issue is the limitation that factor levels can only be strings and not any other data type. Also, I think testing strings for equality is O(1) since it should simplify to a pointer comparison.

That's not right. Factor _levels_ can only be integers, factor _labels_ can only be strings since labels are the printable representation of a level. Maybe you could store the "real" values of a level as attribute (I.e. metadata) of the factor. Anyway, I think that's as solvable problem.

Well, I don't know if there's a standard terminology used elsewhere, but what you call labels, R calls levels.

Erm ... Well, I admit it's somewhat confusing.

    factor(x = character(), levels, labels = levels, exclude = NA, ordered = is.ordered(x), nmax = NA)

    [...]

    levels
    :   an optional vector of the values (as character strings) that x might 
        have taken. The default is the unique set of values taken by 
        as.character(x), sorted into increasing order of x. Note that this set 
        can be specified as smaller than sort(unique(x)).

    labels
    :   either an optional character vector of (unique) labels for the 
        levels (in the same order as levels after removing those in exclude), or 
        a character string of length 1.

This way, you can do something like that:

    > x <- 1:3
    > factor(x, levels = 1:2, labels = c("foo", "bar"))
    [1] foo  bar  <NA>
    Levels: foo bar

But this actually is:

    > factor(as.character(x), levels = c("1", "2"), labels = c("foo", "bar"))
    [1] foo  bar  <NA>
    Levels: foo bar