关键词：
【中文标题】在编译时查找 std::map 的重复值【英文标题】：Finding duplicate values of std::map at compile time 【发布时间】：2021-09-14 05:24:17 【问题描述】：我有一个 模板 类 (BiMap)，它被用作 双向 地图，用于 查找目的，例如enum 值映射到 std::string 等效项，反之亦然。
要实现这一点，std::string 值必须也是唯一的，以防止重复的 std::string 值在 按值搜索 查找期间返回第一个找到的 enum 键.
template<typename Key, typename Value>
class BiMap
public:
explicit BiMap(std::initializer_list<std::pair<Key, Value>> &&items) : bimap_items.begin(), items.end()
assert(!HasDuplicates(bimap_));
Key GetKeyFromValue(const Value &value) const
auto it = std::find_if(bimap_.begin(), bimap_.end(), [&value](const std::pair<Key, Value> &kvp)
return kvp.second == value;
);
return (it != bimap_.end() ? it->first : Key());
Value GetValueFromKey(const Key &key) const
auto it = bimap_.find(key);
return (it != bimap_.end() ? it->second : Value());
private:
const std::map<Key, Value> bimap_;
;
我使用一个名为 HasDuplicates 的函数来检查任何重复值：
template<typename Key, typename Value>
bool HasDuplicates(const std::map<Key, Value> &bimap)
// Create a map to use the values as keys
std::map<Value, Key> value_key_map;
for (auto &kvp : bimap) value_key_map.emplace(kvp.second, kvp.first);
// If there are no duplicate values then the sizes should be the same
std::cout << "HasDuplicates: " << std::boolalpha << (value_key_map.size() != bimap.size()) << std::endl;
return (value_key_map.size() != bimap.size());
我可以运行以下示例代码，它会指示在运行时是否有任何重复值：
// Test 1: No duplicates
std::cout << "**No duplicates test:**" << std::endl;
const BiMap<std::string, int> bi_map_no_dups("foo", 1, "bar", 2, "foobar", 3);
std::cout << "foo: " << bi_map_no_dups.GetValueFromKey("foo") << std::endl;
std::cout << "bar: " << bi_map_no_dups.GetValueFromKey("bar") << std::endl;
std::cout << "foobar: " << bi_map_no_dups.GetValueFromKey("foobar") << std::endl;
// Test 2: Duplicates
std::cout << "**Duplicates test:**" << std::endl;
const BiMap<std::string, int> bi_map_dups("foo", 1, "bar", 2, "foobar", 1);
std::cout << "foo: " << bi_map_dups.GetValueFromKey("foo") << std::endl;
std::cout << "bar: " << bi_map_dups.GetValueFromKey("bar") << std::endl;
std::cout << "foobar: " << bi_map_dups.GetValueFromKey("foobar") << std::endl;
这样的输出是：
**No duplicates test:**
HasDuplicates: false
foo: 1
bar: 2
foobar: 3
**Duplicates test:**
HasDuplicates: true
main.cpp:22: BiMap<Key, Value>::BiMap(std::initializer_list<std::pair<_T1, _T2> >&&) [with Key = std::basic_string<char>; Value = int]: Assertion `!HasDuplicates(bimap_)' failed.
上述代码的工作示例可以在here找到。
问题：
如何评估std::map在编译时是否有重复值？
我尝试过的：
我已经尝试实现constexpr模板函数，如here：
template <typename K, typename V> constexpr bool has_duplicates(const std::map<K,V> *map)
std::map<V,K> value_key_map;
for(auto &kvp : map) value_key_map.emplace(map->second,map->first);
return map->size() == value_key_map.size();
int main()
// Cannot get this part to work
constexpr std::map<std::string, int> bimap("foo", 1, "bar", 2, "foobar", 1);
static_assert(!has_duplicates(&bimap));
return 0;
注意：我正在使用 C++11，我还不能声明 local 变量和 循环在 constexpr 函数内部，因此应该恢复为递归，如 here 所示。但是，对于这个例子，如果我能找到一个具有 C++14 的 constexpr 功能的合适解决方案，我会很高兴，并且稍后我会得到一个递归版本（如果可能的话）。
【问题讨论】：
std::map 和 std::string 不是 constexpr（std::string 可能仅在 C++20 后用于 constexpr 函数）。
如果你变成std::array<std::pair<const K, V>, N>（实际上是你自己的数组，因为在C++11中缺少constexpr），你可以在编译时进行检查。
@Jarod42 你是完全正确的。这似乎是不可能的。但是，我确实使用了您的 std::array 提案here，它是仅使用 GCC10.x 及更高版本的 C++11 和 C++14 的可行版本。
请注意，您实际上需要自定义函数来比较 C 字符串。 "FOO" == "FOO" 不保证是true。
@Jarod42，非常感谢。根据您的最后一条评论，我能够创建一个合适的 solution，它支持 GNU 4.8.5 和 C++11 以及 C++14 及更高版本的新编译器。
【参考方案1】：
如何评估 std::map 在编译时是否有重复值？
你不能。 std::map() 在编译时不可用。
您可以改为使用 https://github.com/serge-sans-paille/frozen 或 https://github.com/mapbox/eternal 进行检查（或其他一些 constexpr 结构）。
另一种方法（如果您想保持在 C++11 级别）是构建一个基于模板元编程的映射，例如 this answer。
【讨论】：
感谢您为我指明正确的方向。冰冻的和永恒的看起来都很有希望。不幸的是，我被 C++11 和 GCC 4.8.5 困住了，这使得两者在此时都不可行。我将尝试模板元编程选项，看看这是否能在我当前的限制下解决我的问题。【参考方案2】：在 comment 部分的帮助下，我能够为我的问题制定合适的解决方案。
重要提示：std::map 不是 constexpr，并且不能用于在编译时评估其内容。
但是，您可以使用std::array<std::pair<const K, V>, N> 来帮助在编译时从 C++14 评估内容，如下所示：
template<typename K, typename T, size_t N>
constexpr bool has_duplicates(const std::array<std::pair<K, T>, N> *arr)
for (int i = 0; i < N - 1; i++)
for (int j = i + 1; j < N; j++)
if (compare_equal((*arr)[i].second,(*arr)[j].second) ||
compare_equal((*arr)[i].first, (*arr)[j].first)) return true;
return false;
有用法：
constexpr std::array<std::pair<int, const char *>, 3> arrd 1, "foobar",
2, "bar",
3, "foobar";
static_assert(!has_duplicates(&arrd), "Duplicates Found!");
并且您需要以下额外的比较函数：
template<typename A, typename B>
constexpr bool compare_equal(A a, B b)
return a == b;
template <>
constexpr bool compare_equal(const char * a, const char * b)
return *a == *b && (*a == '\0' || compare_equal(a + 1, b + 1));
对于 C++11 支持，您需要将 has_duplicates 函数更改为 recursive 实现。这是两个版本的完整工作 example。
因此，您可以在您的类中使用它来在编译时检查重复值。
【讨论】：
在 std::map 中查找最接近或准确的键
】在std::map中查找最接近或准确的键【英文标题】：Findingtheclosestorexactkeyinastd::map【发布时间】：2015-02-0907:43:24【问题描述】：我需要创建一个将长度链接到时间间隔的查找表（两者都是双精度数据类型）。键在插入时线性递增... 查看详情
使用 lambda 函数在 std::unordered_map 中查找最小值
】使用lambda函数在std::unordered_map中查找最小值【英文标题】：Usinglambdafunctiontofindaminimumvalueinastd::unordered_map【发布时间】：2019-01-3023:55:21【问题描述】：我正在尝试在地图中找到具有最小值的元素。例如，如果我的地图有(1,12.3),(... 查看详情
使用类方法插入 std::map
...我搜索了很多关于这个问题，但没有找到任何东西，如果重复，请见谅。我在使用返回*this的类方法插入std::map时遇到问题。如果我尝试插入更多值，则实际上只插入第一个值。让我给你看我的代码：usingnamespacestd;classtestpublic:t 查看详情
线程安全std::map：锁定整个地图和各个值[重复](代码片段)
这个问题在这里已有答案： ThreadsafetyofC++stdContainers4个答案 structData...CRITICAL_SECTIONvalLock;std::map<int,Data>mp;CRITICAL_SECTIONmpLock;我目前正在使用两个关键部分来使这个线程安全。我必须锁定map和Data 查看详情
在 std::map 和 std::unordered_map 之间进行选择 [重复]
】在std::map和std::unordered_map之间进行选择[重复]【英文标题】：Choosingbetweenstd::mapandstd::unordered_map[duplicate]【发布时间】：2011-04-2314:11:32【问题描述】：既然std在unordered_map中有一个真正的哈希映射，为什么（或何时）我仍想在实际... 查看详情
C ++ std :: map：获取特定偏移量的密钥[重复]
】C++std::map：获取特定偏移量的密钥[重复]【英文标题】：C++std::map:getthekeyataspecificoffset[duplicate]【发布时间】：2018-04-1100:54:15【问题描述】：如果我的地图的键是动态生成的，有没有办法在特定的偏移量处获取一个键值，比如第... 查看详情
使用带有结构的地图作为键 - 值不会保存[重复]
...::map容器和结构作为键没有什么问题。我想使用map作为ipv6查找表的快速查找表。我有带有IP地址的文件，我想汇总它们。我的地图键是structmyipv6uint64_tMSB;uin 查看详情
优化查找和排序(代码片段)
...化查找和排序C++程序会进行许多查找操作。从编程语言的编译器到浏览器，从控制链表到数据库，许多反复进行的程序活动都会在某个内部的循环底层进行查找操作。就经验而言，查找操作通常会出现在热点函数的列表中。因此... 查看详情
内置类型的 std::map 默认值
...【问题描述】：最近，我对std::mapoperator[]函数感到困惑。在MSDN库中，它说：“如果未找到参数键值，则将其与数据类型的默认值一起插入。”我试图为这个问题寻找更准确的解释。例如这里：std::mapdefaultvalue在这个页面中，Michae... 查看详情
将 std::map 转换为有序的 std::vector
...时，什么都不会打印。到目前为止，我的代码是这样的，编译器没有发现任何错误：voidChampionship::orde 查看详情
使用 std::map 从数组中删除重复项
】使用std::map从数组中删除重复项【英文标题】：Removingduplicatesfromanarrayusingstd::map【发布时间】：2012-06-0922:48:06【问题描述】：我在5分钟内直接发布了我在collabedit上编写的代码（包括弄清楚算法），因此即使在效率方面完全取... 查看详情
c++map怎样根据索引的内容查找到key
c++的std::map有两种方式可以实现依据索引的内容查找对应的键值使用std::map的find接口。例子如下：std::map<std::string,int>mapTest;std::map<std::string,int>::iteratorit=mapTest.find("index");if(it!=mapTest.end())returnit->second;使用std::map... 查看详情
std::map 扩展初始值设定项列表是啥样的？
...合......好吧，我能想到的所有GCC4.4的组合，但都没有找到编译的结果。【问题讨论】： 查看详情
GTEST 中 std::map 和 dense_hash_map 的编译器错误
】GTEST中std::map和dense_hash_map的编译器错误【英文标题】：Compilererrorwithstd::mapanddense_hash_mapinGTEST【发布时间】：2016-10-2606:37:15【问题描述】：当我尝试在我的GOOGLE测试中使用我的项目/模块时遇到此错误。gcc.compile.c++bin/gcc-4.8.3/debug... 查看详情
clion无法解析类型std::unordered_map，即使它提示我包含标题和编译工作(代码片段)
...t+Enter的标题。在我包含#include<unordered_map>的标题后，编译也可以。我甚至可以按住Ctrl+单击include行来查找头文件，但我无法点击类型定义行（保持红色）。我不明白为什么IDE一直拒绝识别代码中的类型。实际上，它建议我加... 查看详情
使用 std::map 时，我应该为键类型重载 operator== 吗？
...布时间】：2013-11-2321:34:37【问题描述】：std::map不应该有重复的键，所以当我有自定义类型时它如何知道我有重复的键，我是否需要重载重载运算符==？还是会隐式创建？根据文档，我只需要操作符考虑这个例子：classMyTy 查看详情
c++11 使用 std::map 作为返回值
...）。但是写代码的时候有点不方便。所以我想如果我可以在c++11下使用返回值（如下面的funcVec1和funcMap1），因为它会调用移动构造函 查看详情
在 std::map 中搜索时堆栈溢出
】在std::map中搜索时堆栈溢出【英文标题】：stackoverflowwhensearchinginstd::map【发布时间】：2014-04-1314:11:48【问题描述】：这段代码在运行时由于某种原因导致堆栈溢出异常：neuralnetwork::CPerceptron::inputEvent(constneuralnetwork::IConnection*origi... 查看详情