How to check if a table contains an element in Lua?

Question

Is there a method for checking if a table contains a value ? I have my own (naive) function, but I was wondering if something "official" exists for that ? Or something more efficient...

function table.contains(table, element)
  for _, value in pairs(table) do
    if value == element then
      return true
    end
  end
  return false
end

By the way, the main reason I'm using this functions is to use tables as sets, ie with no duplicate elements. Is there something else I could use ?

Answer 1

You can put the values as the table's keys. For example:

function addToSet(set, key)
    set[key] = true
end

function removeFromSet(set, key)
    set[key] = nil
end

function setContains(set, key)
    return set[key] ~= nil
end

There's a more fully-featured example here.

Answer 2

Given your representation, your function is as efficient as can be done. Of course, as noted by others (and as practiced in languages older than Lua), the solution to your real problem is to change representation. When you have tables and you want sets, you turn tables into sets by using the set element as the key and true as the value. +1 to interjay.

Answer 3

I can't think of another way to compare values, but if you use the element of the set as the key, you can set the value to anything other than nil. Then you get fast lookups without having to search the entire table.

Answer 4

I know this is an old post, but I wanted to add something for posterity. The simple way of handling the issue that you have is to make another table, of value to key.

ie. you have 2 tables that have the same value, one pointing one direction, one pointing the other.

function addValue(key, value)
    if (value == nil) then
        removeKey(key)
        return
    end
    _primaryTable[key] = value
    _secodaryTable[value] = key
end

function removeKey(key)
    local value = _primaryTable[key]
    if (value == nil) then
        return
    end
    _primaryTable[key] = nil
    _secondaryTable[value] = nil
end

function getValue(key)
    return _primaryTable[key]
end

function containsValue(value)
    return _secondaryTable[value] ~= nil
end

You can then query the new table to see if it has the key 'element'. This prevents the need to iterate through every value of the other table.

If it turns out that you can't actually use the 'element' as a key, because it's not a string for example, then add a checksum or tostring on it for example, and then use that as the key.

Why do you want to do this? If your tables are very large, the amount of time to iterate through every element will be significant, preventing you from doing it very often. The additional memory overhead will be relatively small, as it will be storing 2 pointers to the same object, rather than 2 copies of the same object. If your tables are very small, then it will matter much less, infact it may even be faster to iterate than to have another map lookup.

The wording of the question however strongly suggests that you have a large number of items to deal with.