Dictionary class is missing key methods

[limbonaut]

Godot version

4.2.1-stable

godot-cpp version

4.2

System information

Manjaro GNOME, NVIDIA X11, Forward+

Issue description

Dictionary is missing get_value_at_index, get_key_at_index and get_valid. get_valid is easy to work around, but the other two are problematic. The workaround if to get keys() and values() to iterate over, and it's slow.

Steps to reproduce

N/A

Minimal reproduction project

N/A

[AThousandShips]

These are not exposed, and Dictionary is not a declared type on the godot-cpp side, so this is a limitation on the binds side, just like this isn't available in GDScript

This would require either declaring Dictionary on the godot-cpp side, or exposing it to the binds, i.e. exposing it to GDScript as well

How is iterating over the keys and values slower? How have you confirmed that this would be slower than using the non-exposed methods? Given the implementation in c++ the get_key/value_at_index methods are pretty slow:

	int index = 0;
	for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
		if (index == p_index) {
			return E.key;
		}
		index++;
	}

	return Variant();

It iterates over the map, which is a hash map, so the time for each operation is O(n), so nominally using this to iterate over the dictionary is O(n^2), copying the keys and values and iterating over them instead is most likely faster, quite a bit faster in fact

Instead doing fetching just the keys, and then iterating over those, is nominally an O(n) operation, fetching the keys is O(n), and looking up each key in the dictionary is amortized constant

[limbonaut]

I assumed it's slow. You are right, for iterations it should be faster to use keys()/values(). I guess they are not important enough to expose since edge cases, when you need to get a single key/value at a certain index, are rare.

[AThousandShips]

Well I'd suggest confirming it's slow before opening an issue 🙂, assumptions are dangerous when they inform decisions like these

You can still get the key and index as a specific index though, with those methods getting the keys and values, and they aren't meaningfully slower when doing them once (just "I want this specific entry", then just do dict[dict.keys()[i])), and if iterating it's actually faster as explained above 🙂

I'd say a more useful improvement would be to add enumeration, i.e. begin/end such as is available on the packed arrays, which GDExtension has support for (as you can do it in GDScript), which would be equivalent to for (const Variant &key : dict.keys()) but without having to produce the array first

[limbonaut]

Enumerations would be great! :+1: My main reason to open this issue was that they are absent from the GDExtension API, for compatibility reasons. I'm considering porting a module with a support for compilation as both GDExtension and as an engine module. But the workaround is ~good enough~ actually faster.

[AThousandShips]

Do try the following for enumeration, from the example code:

Variant test_variant_iterator(const Variant &p_input) {
	Array output;

	Variant iter;

	bool is_init_valid = true;
	if (!p_input.iter_init(iter, is_init_valid)) {
		if (!is_init_valid) {
			return "iter_init: not valid";
		}
		return output;
	}

	bool is_iter_next_valid = true;
	bool is_iter_get_valid = true;
	do {
		if (!is_iter_next_valid) {
			return "iter_next: not valid";
		}

		Variant value = p_input.iter_get(iter, is_iter_get_valid);
		if (!is_iter_get_valid) {
			return "iter_get: not valid";
		}
		output.push_back(((int)value) + 5);

	} while (p_input.iter_next(iter, is_iter_next_valid));

	if (!is_iter_next_valid) {
		return "iter_next: not valid";
	}

	return output;
}

This could be made more convenient, but at the moment I don't think there's an extension detail to indicate that a type is iterable, so would need that I think

Edit: Will do some testing later to more easily do this as a for loop, should be trivial, will see though, could be able to also create a macro for ease, such as GODOT_FOR_EACH which takes something like:

#define GODOT_FOR_EACH(m_variable, m_iterable)

Which then would be used so:

GODOT_FOR_EACH(foo, iterable) {
   bar(foo);
}

[limbonaut]

Ideally, it would be nice to have a common iteration solution for Dictionary in both the engine module code and GDExtension code. Less #ifdefs. I'll stick to keys()/values() from now on, but for(kv : dic) would be a nicer and cleaner alternative.

[dsnopek]

I'd say a more useful improvement would be to add enumeration, i.e. begin/end such as is available on the packed arrays, which GDExtension has support for (as you can do it in GDScript), which would be equivalent to for (const Variant &key : dict.keys()) but without having to produce the array first

Being able to iterate over Array like this would be really cool, and probably not even that hard to add!

However, since we try to match the API of the engine itself, we'd need to first add it to Array in Godot before we could add it here.