1

我需要实现一个 C++ 类来支持以下内容

数据：

键 - 字符串

子键 - 字符串/双精度

值 - 字符串/双精度

键和子键一起唯一标识行。

例如：

[ "key", "subkey", "value" ]

[ "cse", "a", 100 ]

[ "cse", "b", 120 ]

[ "cse", 100, 10 ]

操作：

1）给定一个键和返回值

2）给定一个键返回一个数组[ "subkey", "value" ]

我面临的问题是子键和值可以是双精度和字符串。解决这个问题的一种方法是拥有一个能够存储双精度类型和字符串类型的包装类。

第一级地图将有一个字符串作为键，值将是一个地图。

第二级映射将键作为新的包装类，值也是一个新的包装类。

这种方法对吗？还是有更好的方法来做到这一点？

4

2 回答 2

2

我使用 Boost.Variant 和 C++11 破解了一个解决方案unordered_map。该代码是 C++11 的一个很好的例子。

您需要特别注意在 的专业化中两个哈希的组合std::hash<key>::operator()，它会对哈希的质量产生很大的影响。要获得更好的实现，请查看boost::hash_combine，遗憾的是尚未标准化。

一般来说，代码的作用是：定义一个特殊的键类型，即 EqualityComparable 和 Hashable，然后在 std::unordered_map. 您可以仅使用 Boost 构建所有这些，而根本不需要 C++11。如果您既没有 Boost 也没有 C++11，那么您就处于困境中。没有对此进行真正的测试。

#include <boost/variant.hpp>
#include <string>
#include <functional>
#include <unordered_map>
#include <iostream>

struct key {
  std::string primary;
  boost::variant<std::string, double> secondary;
  friend bool operator==(const key& x, const key& y)
  { return x.primary == y.primary && x.secondary == y.secondary; }
};

namespace std {
template<>
struct hash<key> {
  std::size_t operator()(const key& k) const
  { 
    std::size_t first = std::hash<std::string>()(k.primary);
    std::size_t second;

    // check for the more likely case first
    if(const std::string* s = boost::get<std::string>(&(k.secondary))) {
      second = std::hash<std::string>()(*s);
    } else {
      const double* d = boost::get<double>(&(k.secondary));
      second = std::hash<double>()(*d);
    }
    return first ^ ( second << 1 ); // not so fancy hash_combine
  }
};

} // std


int main()
{
  typedef std::unordered_map<key, boost::variant<std::string, double>> MyMap;
  MyMap m = {
    {{"foo", "bar"}, "foobar"},
    {{"foo", 23.0}, "foo23"},
    {{"nothing", 23.0}, 23.0}
  };

  std::cout << m[{"foo", "bar"}] << std::endl;
  std::cout << m[{"foo", 23.0}] << std::endl;
  std::cout << m[{"nothing", 23.0}] << std::endl;

  return 0;
}
于 2013-05-01T15:57:35.560 回答
1

以下每个键会浪费一点空间，但具有简单的优点：

struct Key
{
    Key(string primary, string subkey)
        : primary(primary)
        , is_double(false)
        , string_subkey(subkey)
    {}

    Key(string primary, double subkey)
        : primary(primary)
        , is_double(true)
        , double_subkey(subkey)
    {}

    string primary;
    bool is_double;
    double double_subkey;
    string string_subkey;
}

您需要实现适当的比较操作和/或哈希函数。

于 2013-05-01T15:58:36.793 回答