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 ?

Nameplate

what does the _, notation mean? – Best

It's simply a "garbage" variable named _. pairs() returns key, value, but in this example I only need the value. It is kind of a convention (adopted in the book "Programming in Lua" lua.org/pil/index.html) to use this _ variable to store things yon don't need. – Nameplate

I've seen the convention of naming "garbage" variables _ used in Python and JavaScript, too. – Ironbound

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.

Scruff

Perhaps also function keysOfSet(set) local ret={} for k,_ in pairs(set) do ret[#ret+1]=k end return ret end – Torsibility

I'm a bit new to the Lua and want to know how I would accomplish this at the creation of the table. Would it just be created as {keyvalue = true, keyvalue2 = true, keyvalue3 = true, [...]}, or —as I'm kind of hoping since representing sets is probably a common use of tables— is there a more concise way? – Fairchild

@TwistedCode You can use a function to create the set like here. – Scruff

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.

Dali

An 'official' method would probably do this in C, which would be faster. But if done only in lua, as you said, this is the most efficient method possible! – Hiatt

Answer 3

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.

Mack

A good explanation, but does not really add anything to the discussion. It probably would have been a better idea to edit interjay's answer. – Jolin

Answer 4

-- in some helper module
function utils_Set(list)
    local set = {}
    for _, l in ipairs(list) do set[l] = true end
    return set
end

-- your table here
long_table = { "v1", "v2", "v1000"}

-- Consult some value
_set = utils_Set(long_table)
if _set["v1"] then print("yes!") end

Lantha

Liked this because doesn’t require constant maintenance of a parallel table. – Rosenkranz

Answer 5

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.

Ecumenicity