Consider the following Lua multimap example.
Multimap = {}; function Multimap:__index(key) if (key == 'keys') then local ret = {} for k,_ in pairs(self) do ret[#ret+1] = k; end return ret; else return rawget(getmetatable(self), key) end end function Multimap.Create() local self = {}; setmetatable(self, Multimap); return self; end function Multimap:Insert(key, value) local list = self[key]; if (list == nil) then list = {}; self[key] = list; end table.insert(list, value); end function Multimap:Remove(key, value) local list = self[key]; assert(list ~= nil, "key not found"); for i = 1,#list do if (list[i] == value) then table.remove(list, i); if (#list == 0) then self[key] = nil; end return; end end error("value not found"); end -- testing m = Multimap.Create() m:Insert(1,5) m:Insert(2,6) m:Insert(3,7) m:Insert(1,8) m:Remove(2,6) print(pcall(function() m:Remove(2,6) -- will produce assert exception end)) print("keys left: ", table.concat(m.keys, ','))
You can implement this in C ++ in several ways.
- Use the heavy Lua API. The code below almost exactly matches Lua.
#include <Lua/src/lua.hpp> int Multimap_Index(lua_State* L) { lua_settop(L, 2); // force 2 arguments const char *key_value = "key"; size_t key_len; const char *key = lua_tolstring(L, 2, &key_len); if (!strncmp(key, key_value, strlen(key_value))) { int i = 0; lua_newtable(L); // stack : self, key, ret = {} int ret = lua_gettop(L); lua_pushnil(L); // stack : self, key, ret, nil while (lua_next(L, 1) != 0) { // stack : self, key, ret, k, v lua_pop(L, 1); // stack : self, key, ret, k lua_len(L, ret); // stack : self, key, ret, k, #ret lua_pushvalue(L, -2); // stack : self, key, ret, k, #ret, k lua_rawseti(L, ret, lua_tointeger(L, -2)+1); // ret[#ret+1] = k ; || stack : self, key, ret, k, #ret lua_pop(L, 1); // stack : self, key, ret, k } // stack : self, key, ret return 1; } else { lua_getmetatable(L, 1); // stack : self, key, metatable(self) lua_pushvalue(L, 2); // stack : self, key, metatable(self), key lua_rawget(L, -2); // stack : self, key, metatable(self), rawget(metatable(self), key) return 1; } } int Multimap_Remove(lua_State* L) { lua_settop(L, 3); // force 3 arguments: self, key, value lua_checkstack(L, 12); // reserve 12 arguments on stack (just in case) lua_pushvalue(L, 2); // stack: self, key, value, key lua_gettable(L, 1); // stack: self, key, value, list = self[key] if (lua_isnil(L, -1)) luaL_error(L, "key not found"); lua_len(L, -1); // stack: self, key, value, list, #list int count = lua_tointeger(L, -1); lua_pop(L, 1); // stack: self, key, value, list for (int i = 1; i <= count; ++i) { lua_rawgeti(L, -1, i); // stack: self, key, value, list, v = list[i] if (lua_compare(L, 3, 5, LUA_OPEQ)) { // if (list[i] == value) lua_getglobal(L, "table"); // stack : self, key, value, list, v, table lua_getfield(L, -1, "remove"); // stack : self, key, value, list, v, table, table.remove lua_pushvalue(L, 4); lua_pushinteger(L, i); // stack : self, key, value, list, v, table, table.remove, list, i lua_call(L, 2, 0); // table.remove(list, i); || stack : self, key, value, list, v, table lua_pushnil(L); if (lua_next(L, 4) == 0) { // if list is empty table lua_pushvalue(L, 2); lua_pushnil(L); lua_settable(L, 1); // self[key] = nil } return 0; } } luaL_error(L, "value not found"); } int main() { auto L = luaL_newstate(); luaL_openlibs(L); lua_newtable(L); int Multimap = lua_gettop(L); // Multimap = {} lua_pushvalue(L, Multimap); lua_setglobal(L, "Multimap"); // _G.Multimap = Multimap; // option 1: create a C function for operation // Multimap.__index = &Multimap_Index lua_pushcfunction(L, Multimap_Index); lua_setfield(L, Multimap, "__index"); // option 2: compile Lua code and use it luaL_loadstring(L, "local self = {};\n" "setmetatable(self, Multimap);\n" "return self;\n" ); lua_setfield(L, Multimap, "Create"); // Multimap.Create = &Multimap_Create luaL_loadstring(L, "local self, key, value = ...;\n" // initialize local variables from parameters here "local list = self[key];\n" "if (list == nil) then\n" " list = {};\n" " self[key] = list;\n" "end\n" "table.insert(list, value);\n" ); lua_setfield(L, Multimap, "Insert"); // Multimap.Create = &Multimap_Insert lua_pushcfunction(L, Multimap_Remove); lua_setfield(L, Multimap, "Remove"); // Multimap.Create = &Multimap_Remove lua_getfield(L, Multimap, "Create"); lua_call(L, 0, 1); int m = lua_gettop(L); lua_getfield(L, m, "Insert"); // stack : m, m.insert int Insert = lua_gettop(L); // m.Insert(m, 1, 5) lua_pushvalue(L, Insert); lua_pushvalue(L, m); lua_pushinteger(L, 1); lua_pushinteger(L, 5); lua_call(L, 3, 0); // m.Insert(m, 2, 6) lua_pushvalue(L, Insert); lua_pushvalue(L, m); lua_pushinteger(L, 2); lua_pushinteger(L, 6); lua_call(L, 3, 0); // m.Insert(m, 3, 7) lua_pushvalue(L, Insert); lua_pushvalue(L, m); lua_pushinteger(L, 3); lua_pushinteger(L, 7); lua_call(L, 3, 0); // m.Insert(m, 1, 8) lua_pushvalue(L, Insert); lua_pushvalue(L, m); lua_pushinteger(L, 1); lua_pushinteger(L, 8); lua_call(L, 3, 0); // m.Remove(m, 2, 6) lua_getfield(L, m, "Remove"); lua_pushvalue(L, m); lua_pushinteger(L, 2); lua_pushinteger(L, 6); lua_call(L, 3, 0); // m.Remove(m, 2, 6) lua_getfield(L, m, "Remove"); lua_pushvalue(L, m); lua_pushinteger(L, 2); lua_pushinteger(L, 6); lua_pcall(L, 3, 0, 0); printf("%s\n", lua_tostring(L, -1)); lua_getglobal(L, "table"); lua_getfield(L, -1, "concat"); lua_getfield(L, m, "keys"); lua_pushstring(L, ","); lua_call(L, 2, 1); printf("keys left: %s\n", lua_tostring(L, -1)); lua_close(L); return 0; }
- OR you can use Lua user data that use std :: multimap (it will take me another hour to implement this, so ask if you really need it - this does not follow from your question)