Question about table.remove.

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Question about table.remove.

yan jun
here is a sample:
--====================================================
t = {1}
table.remove(t,2)    --no error, return nil
table.remove(t,3)    --throw an error: "position out of bounds"
--====================================================

"table.remove" is implemented by "tremove" in C, and here is the code about "tremove" in lua5.3:

/*=====================================================
static int tremove (lua_State *L) {
  lua_Integer size = aux_getn(L, 1, TAB_RW);
  lua_Integer pos = luaL_optinteger(L, 2, size);
  if (pos != size)  /* validate 'pos' if given */
    luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
  lua_geti(L, 1, pos);  /* result = t[pos] */
  for ( ; pos < size; pos++) {
    lua_geti(L, 1, pos + 1);
    lua_seti(L, 1, pos);  /* t[pos] = t[pos + 1] */
  }
  lua_pushnil(L);
  lua_seti(L, 1, pos);  /* t[pos] = nil */
  return 1;
}
/*=====================================================

I am curious about that why "size + 1" is the validate position?
Does the positon length+1 has a special meaning?

thanks everybody!
Reply | Threaded
Open this post in threaded view
|

Re: Question about table.remove.

Xianfu Pan

table.remove (list [, pos])

Removes from list the element at position pos, returning the value of the removed element. When pos is an integer between 1 and #list, it shifts down the elements list[pos+1], list[pos+2], ···, list[#list] and erases element list[#list]; The index pos can also be 0 when #list is 0, or #list + 1; in those cases, the function erases the element list[pos].

The default value for pos is #list, so that a call table.remove(l) removes the last element of list l.


2018-06-06 19:42 GMT+08:00 yan jun <[hidden email]>:
here is a sample:
--====================================================
t = {1}
table.remove(t,2)    --no error, return nil
table.remove(t,3)    --throw an error: "position out of bounds"
--====================================================

"table.remove" is implemented by "tremove" in C, and here is the code about "tremove" in lua5.3:

/*=====================================================
static int tremove (lua_State *L) {
  lua_Integer size = aux_getn(L, 1, TAB_RW);
  lua_Integer pos = luaL_optinteger(L, 2, size);
  if (pos != size)  /* validate 'pos' if given */
    luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
  lua_geti(L, 1, pos);  /* result = t[pos] */
  for ( ; pos < size; pos++) {
    lua_geti(L, 1, pos + 1);
    lua_seti(L, 1, pos);  /* t[pos] = t[pos + 1] */
  }
  lua_pushnil(L);
  lua_seti(L, 1, pos);  /* t[pos] = nil */
  return 1;
}
/*=====================================================

I am curious about that why "size + 1" is the validate position?
Does the positon length+1 has a special meaning?

thanks everybody!

Reply | Threaded
Open this post in threaded view
|

Re: Question about table.remove.

Francisco Olarte
On Thu, Jun 14, 2018 at 4:01 AM, Xianfu Pan <[hidden email]> wrote:

> table.remove (list [, pos])
>
> Removes from list the element at position pos, returning the value of the
> removed element. When pos is an integer between 1 and #list, it shifts down
> the elements list[pos+1], list[pos+2], ···, list[#list] and erases element
> list[#list]; The index pos can also be 0 when #list is 0, or #list + 1; in
> those cases, the function erases the element list[pos].
>
> The default value for pos is #list, so that a call table.remove(l) removes
> the last element of list l.

Yeah, those are the docs and they are easily understood.

What I wonder in the case of #list+1 is that #list is defined as being
before a nil ( non existent ) index/key ( I think if it is then
list[1] is nil and if greater than 0 then t[#list]~=nil and
t[#list+1]==nil ). So when pos=#list+1 there is never an element to
erase at list[pos]. The moving code then seems to degenerate to
redundantly setting list[pos] to nil.

It seems like an off by one error kept in case someone depends on it.
But may be somebody can explain it.

Allowing the "just after end" index ( or pointer ) as valid is common
in many libraries / languages, like in C++ STL or in C pointers ( in C
a 10 element array can produce 11 valid pointer, every element plus
one pass the end, but the last one cannot be dereferenced, it is valid
in the sense than producing it and doing some ops, like substracting
the start pointer from it, are defined ) , to be able to refer to full
containers as half-open intervals and other niceties, but given lua
habit of using closed intervals it seems strange, and normally even if
the "one paste the end" index is valid in many places it cannot be
used to remove the unexistant element.

Francisco Olarte.

Reply | Threaded
Open this post in threaded view
|

Re: Question about table.remove.

siney-2
In reply to this post by yan jun

I think it just tell you no element been removed , you should stop to call remove again by in loop,

You can check returned value is nil to know index is invalid without triggering an error.

 

发件人: <[hidden email]> 代表 yan jun <[hidden email]>
答复: Lua mailing list <[hidden email]>
日期: 201866 星期三 下午7:43
收件人: "[hidden email]" <[hidden email]>
主题: Question about table.remove.

 

here is a sample:

--====================================================

t = {1}

table.remove(t,2)    --no error, return nil

table.remove(t,3)    --throw an error: "position out of bounds"

--====================================================

 

"table.remove" is implemented by "tremove" in C, and here is the code about "tremove" in lua5.3:

 

/*=====================================================

static int tremove (lua_State *L) {
  lua_Integer size = aux_getn(L, 1, TAB_RW);
  lua_Integer pos = luaL_optinteger(L, 2, size);
  if (pos != size)  /* validate 'pos' if given */
    luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
  lua_geti(L, 1, pos);  /* result = t[pos] */
  for ( ; pos < size; pos++) {
    lua_geti(L, 1, pos + 1);
    lua_seti(L, 1, pos);  /* t[pos] = t[pos + 1] */
  }
  lua_pushnil(L);
  lua_seti(L, 1, pos);  /* t[pos] = nil */
  return 1;
}

/*=====================================================

 

I am curious about that why "size + 1" is the validate position?

Does the positon length+1 has a special meaning?

 

thanks everybody!

Reply | Threaded
Open this post in threaded view
|

Re: Question about table.remove.

Soni "They/Them" L.


On 2018-06-14 04:31 AM, siney wrote:

>
> I think it just tell you no element been removed , you should stop to
> call remove again by in loop,
>
> You can check returned value is nil to know index is invalid without
> triggering an error.
>
> *发件人**: *<[hidden email]> 代表yan jun
> <[hidden email]>
> *答复**: *Lua mailing list <[hidden email]>
> *日期**: *2018年6月6日星期三下午7:43
> *收件人**: *"[hidden email]" <[hidden email]>
> *主题**: *Question about table.remove.
>
> here is a sample:
>
> --====================================================
>
> t = {1}
>
> table.remove(t,2)    --no error, return nil
>
> table.remove(t,3)    --throw an error: "position out of bounds"
>
> --====================================================
>
> "table.remove" is implemented by "tremove" in C, and here is the code
> about "tremove" in lua5.3:
>
> /*=====================================================
>
> static int tremove (lua_State *L) {
>   lua_Integer size = aux_getn(L, 1, TAB_RW);
>   lua_Integer pos = luaL_optinteger(L, 2, size);
>   if (pos != size)  /* validate 'pos' if given */
>     luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
>   lua_geti(L, 1, pos);  /* result = t[pos] */
>   for ( ; pos < size; pos++) {
>     lua_geti(L, 1, pos + 1);
>     lua_seti(L, 1, pos);  /* t[pos] = t[pos + 1] */
>   }
>   lua_pushnil(L);
>   lua_seti(L, 1, pos);  /* t[pos] = nil */
>   return 1;
> }
>
> /*=====================================================
>
> I am curious about that why "size + 1" is the validate position?
>
> Does the positon length+1 has a special meaning?
>
> thanks everybody!
>

It is the only way to have a no-op. E.g.

len = 0
t = setmetatable({}, {__index=function(t, k) return (k >= 0 and k <=
len) and k or nil end, __len=function() return len end})
table.remove(t) -- works fine, not strictly safe (removes t[0])
table.remove(t, 0) -- works fine, not strictly safe either (removes t[0])
table.remove(t, 1) -- works fine, safe (doesn't remove t[0])
len = 1
table.remove(t, 1) -- removes our element
table.remove(t, 2) -- doesn't remove our element
table.remove(t, 0) -- errors

I guess this simplifies some table.remove-using code? I still find this
implementation rather odd (why not check `if t[pos] == nil and t[pos -
1] == nil then error end`, as it would improve performance in theory?
then again length calculation is binary search which is pretty fast if
your CPU doesn't have any memory cache (or with very large tables). I
just feel like it's unnecessary complexity (in the big-O sense).)

Reply | Threaded
Open this post in threaded view
|

Re: Question about table.remove.

Sam Putman
In reply to this post by yan jun


On Wed, Jun 6, 2018 at 4:42 AM, yan jun <[hidden email]> wrote:
here is a sample:
--====================================================
t = {1}
table.remove(t,2)    --no error, return nil
table.remove(t,3)    --throw an error: "position out of bounds"
--====================================================

"table.remove" is implemented by "tremove" in C, and here is the code about "tremove" in lua5.3:

/*=====================================================
static int tremove (lua_State *L) {
  lua_Integer size = aux_getn(L, 1, TAB_RW);
  lua_Integer pos = luaL_optinteger(L, 2, size);
  if (pos != size)  /* validate 'pos' if given */
    luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
  lua_geti(L, 1, pos);  /* result = t[pos] */
  for ( ; pos < size; pos++) {
    lua_geti(L, 1, pos + 1);
    lua_seti(L, 1, pos);  /* t[pos] = t[pos + 1] */
  }
  lua_pushnil(L);
  lua_seti(L, 1, pos);  /* t[pos] = nil */
  return 1;
}
/*=====================================================

I am curious about that why "size + 1" is the validate position?
Does the positon length+1 has a special meaning?

thanks everybody!

My suspicion is that this behavior matches that of iterators.  A call to ipairs(t) returns a 
function which, in the end, yields nil for the equivalent of t[#t + 1].

Reply | Threaded
Open this post in threaded view
|

Re: Question about table.remove.

yan jun
In reply to this post by Soni "They/Them" L.
May be is the reason you had mentioned.
Let's take a look at the examples below:
---------------------
array = {1,2,3}
--Example A:
while true do
  if table.remove(array,1) == nil then
  break;
  end;
  ...
end;

--Example B:
while true do
  if array[1] == nil then
  break;
  end;
  table.remove(array,1);
  ...
end;
---------------------
In some situation, it can simplified the code while "table.remove" accept the index len+1.
But i think example B is more clearly to tell what does this codes do, and can adapt to future changes of lua(maybe table.remove(len+1) will trigger an error one day.)

thx for the reply.

On 2018-06-14 04:31 AM, siney wrote:
>
> I think it just tell you no element been removed , you should stop to
> call remove again by in loop,
>
> You can check returned value is nil to know index is invalid without
> triggering an error.
>