一个 value_type 为它自己的 size_type 的 std::map 使用 std::map::size_type 是什么？

Question

我有一个占用太多内存的 std::map<std::pair<std::string, std::string>, float>，为了使用更少的内存，我决定将唯一的字符串映射到整数上（例如，std::map<std::string, int>，其中每个新的唯一字符串被映射到当前 map 的 size()），并将这些整数值用作 map 的成对键（例如，std::map<std::pair<int, int>, float>）。

我想使用std::map::size_type代替int：

using map_index = std::map::size_type;
std::pair<map_index, map_index> key;

当然，这段代码无法编译，因为我需要为 map 提供参数列表:

vector.cc:14:19: error: invalid use of template-name `std::map' without an argument list
 using map_index = std::map::size_type;

以下是我（理论上）尝试实现的内容：

using map_index = std::map<std::string, map_index>::size_type;

以下是（预期的）编译器错误信息：

vector.cc:15:41: error: `map_index' was not declared in this scope
 using map_index = std::map<std::string, map_index>::size_type;

如何让编译器正确推断出 std::map 的 value_type，而其 value_type 是其自身的 size_type？

- Parker

---

小问题：我认为你把最后一句话的顺序搞反了。要知道什么是“size_type”，首先需要说明什么是“value_type”，而不是相反。一旦你知道了映射的类型，获取它的“size_type”就很容易了。 - 463035818_is_not_a_number

问题似乎在于 size_type 是 OP 的 value_type 的一部分。 - Some programmer dude

你存在循环依赖。为什么不能使用 size_t（通常会成为 size_type 的类型）？ - Some programmer dude

std::map<K, V>::size_type 很可能与 K 和 V 完全独立。如果你真的关心，可以使用 static_assert(std::is_same_v<Map::size_type, Map::mapped_type>, "Unexpected size_type") 进行断言检查。 - Caleth

使用std::map<std::string, X>不如使用boost::flyweight更好吗？ - felix

Answer 1

size_t 对于这种情况应该已经足够了。

但是，如果您坚持要这样做，可以像这样：

#include <type_traits>
#include <map>

template <class Key, class Value = size_t, size_t depth = 0, class = void>
struct GetSizeType {
    using type = typename GetSizeType<Key, typename std::map<Key, Value>::size_type, depth + 1>::type;
};

template <class Key, class Value, size_t depth>
struct GetSizeType<Key, Value, depth, std::enable_if_t<std::is_same_v<Value, typename std::map<Key, Value>::size_type>>> {
    using type = typename std::map<Key, Value>::size_type;
};

template <class Key, class Value>
struct GetSizeType<Key, Value, 100, void> {};

int main() {
    using X = GetSizeType<int>::type;

    return 0;
}

它将在GetSizeType上递归运行，当满足以下条件之一时，递归调用将停止:

• 达到递归调用深度限制(此时不会有成员type)，或者
• 找到一个std::map的特化版本，其中mapped_type和size_type相同(成员type别名为size_type)。

- felix

---

我不完全同意“在耗尽size_t之前，你会耗尽内存”的说法。类似于my_map.size() * 2;这样的操作是一个明智的操作，但在耗尽内存之前就可能溢出了。 - 463035818_is_not_a_number

@user463035818 谢谢，我已经将那部分删除了。我错误地简化了用法。 - felix

@user463035818 - 在问题所设定的上下文中，没有涉及算术运算 - size() 的结果只是被用作一个不透明的标识符。 - Toby Speight

@TobySpeight...我只是误读了问题;) 对于造成的混淆感到抱歉。 - 463035818_is_not_a_number

@vallismortis，“更极端的情况”是什么意思？如果您使用std::size_t，那么它应该能够寻址大小为1的对象，因此没有其他类型无法工作的可能性。 - Acorn

Answer 2

免责声明：此解决方案相当愚蠢。我们将通过反复（通常只执行一次）尝试实例化std::map来解决方程，直到找到具有所请求的键和自己的size_type值的映射。

template <class T>
struct identity {
    using type = T;
};

template <class K, class V = char>
struct auto_map {
    using map_type = std::map<K, V>;
    using type = typename std::conditional_t<
        std::is_same_v<
            typename map_type::mapped_type,
            typename map_type::size_type
        >,
        identity<map_type>,
        auto_map<K, typename map_type::size_type>
    >::type;
};

template <class K>
using auto_map_t = typename auto_map<K>::type;

如果元函数找不到这样的映射，则它要么因为type最终被定义为自身而出错，要么达到递归限制而中断。

- Quentin

---

这两个递归解决方案都很棒，但我不确定为什么要使用它。正如你所说，它仍然不能保证在破碎的环境中找到一个可行的解决方案，因此编译器直接选择一个并断言我们实际需要的条件会更加干净和快速，不是吗？ - Acorn

@Acorn 是的。我只是需要在进行完整重建时做些事情 ;) - Quentin

Answer 3

请使用 std::size_t。无符号整数 std::map::size_type 不会比 std::size_t 更大，在实践中，它们将是相同的类型。

如果您想确保，请断言它：

static_assert(std::is_same_v<
    std::size_t,
    std::map<std::string, std::size_t>::size_type
>);

- Acorn

Answer 4

我所使用过的所有C++实现都对所有映射使用相同的大小类型。

因此；

using map_size_type = std::map<int, int>::size_type;
using my_map = std::map<std::string, map_size_type>;
static_assert(std::is_same<map_size_type, my_map::size_type);

如果（合理的）假设失败，这只会强制编译错误。

- Yakk - Adam Nevraumont

---

我在这里链接另一个问题，因为你的答案似乎也与它相关。 - Parker

Answer 5

你确定 std::map 的 size_type 取决于键/值类型吗？

如果是这样，我看不到获取它的方法。

但是 size_type 不应该取决于键/值类型，通常为 std::size_t。

我建议

using Index0 = typename std::map<std::string, std::size_t>::size_type;

using mapIndex = typename std::map<std::string, Index0>::size_type;    

您可以使用以下代码检查是否获取了正确的类型：

static_assert( std::is_same_v<Index0, mapIndex>, "no right type");

- max66

---

编译器无法知道地图的大小类型始终相同 - 就它而言，可能存在合法的不同专业化。 - Toby Speight

@TobySpeight 是的，这正是促使我提出这个问题的原因。正是C++ map文档中的“通常与size_t相同”条款让我对此深思。 - Parker

@vallismortis - 从理论角度来看，你是正确的（就我所知）。我没有看到打破循环依赖的方法，但是通过添加static_assert(std::is_same_v<Index0, mapIndex>, "no right type");，您可以检查所选类型是否正确。 - max66

@TobySpeight - 你是对的（就我所知）；但是通过 static_assert()（请参见我的修改后的答案），我们可以检查是否已经获得了正确的类型。 - max66

Answer 6

唯一打破循环依赖的方法是使用特定类型。我建议您将map_index简单地设置为std::size_t——C++强烈暗示std::size_t可分配给map::size_type。

- Toby Speight

Answer 7

您所寻找的通常是不可能的。

可以想象（虽然牵强），std::map<int，long> :: size_type 是 int，std::map<int，int> :: size_type 是 long（以及其他整数类型类似），在这种情况下，没有可能满足 std::map<int，T> :: size_type 为 T。

相反，对于所有T，std::map<int，T> :: size_type 定义为 T，在这种情况下，没有独特的 T 满足您的“要求”。

正如几个答案（以及您自己的参考链接）所提到的那样，在实践中，它很可能仅为 size_t。

- Max Langhof

---

这正是我在寻找的答案，只不过不是我所希望的。你提供的具体示例完美地说明了问题。 - Parker