3

在 C++ 中，我有一个按其名称排序的类，即std::string. 我希望在 astd::map或std::set.

我可以使用 a std::set，因为operator<它将按名称对我的实例进行排序，但是，我需要按名称查找实例。使用键是名称的映射是直截了当的，但是，我也可以使用一个集合并构造一个具有我希望查找的名称的类的虚拟实例，以在集合中定位给定类的实际实例姓名。

我想我应该只使用地图以使代码直截了当，但想知道是否有办法使用该集合，因为无论如何密钥实际上都是我的对象的一部分，从而避免了一些冗余。

有没有办法使用该集合并能够以干净的方式通过它们的键定位对象，或者我应该只使用地图并完成它？

这是要插入的类（以草稿形式），并且在每个目录中都有一组节点或节点映射，它们以节点名称为键：

class Node {
public:
  Node(Directory &parent, const std::string &name)
    : _name(name),
      _parent(&parent),
      _isRoot(false) {
    if (name.empty()) {
      throw InvalidNodeNameError(name);
    }
  }

protected:
  // This is only used for the root directory:
  Node()
    : _name(""),
      _parent(0),
      _isRoot(true) {
  }
  Node(const std::string &name)
    : _name(name),
      _parent(0),
      isRoot(false) {
  }

public:
  virtual ~Node() {
    if (parent()) {
      parent()->remove(*this);
    }
  }

  bool operator<(const Node &rhs) const {
    return _name < rhs._name;
  }

  Directory *parent() const {
    return _parent;
  }
  void setParent(Directory *parent) {
    _parent = parent;
  }

  const std::string &name() const {
    return _name;
  }

  bool isRoot() const {
    return _isRoot;
  }

  std::string pathname() const {
    std::ostringstream path;

    if (parent()) {
      path << parent()->pathname() << '/';
    } else {
      path << '/';
    }
    path << name();

    return path.str();
  }

private:
  // Not defined:
  Node(const Node &rhs);
  Node &operator=(const Node &rhs);

private:
  std::string  _name;
  Directory   *_parent;
  const bool   _isRoot;

};
4

4 回答 4

2

实际上，您可以只使用 map<std::string&, Node>，但要花费一个额外的指针，但我想您可能知道这一点，并且它需要一些混乱才能获得您想要的东西。

我一直认为 std::set 没有明确的 KeyExtractor 模板参数是一个真正的痛苦，特别是因为我看到的每个实现都使用其中一个，以便在（多）地图和（多）集。这是一个快速而肮脏的 hack，尚未完成，它公开了 GNU 标准 C++ 库的一些机制，以创建一个“keyed_set”容器：

// Deriving from the tree is probably not a good idea, but it was easy.

template<typename Key, typename Val, typename Extract,
         typename Compare = std::less<Key>, typename Alloc = std::allocator<Val>>
class keyed_set : public std::_Rb_tree<Key, Val, Extract, Compare, Alloc> {
  using Base = std::_Rb_tree<Key, Val, Extract, Compare, Alloc>;

  public:
    template<typename ...Args>
    auto insert(Args... args)
         ->decltype(Base()._M_insert_unique(std::declval<Args>()...)) {
      return this->_M_insert_unique(args...);
    }

    typename Base::iterator insert(typename Base::const_iterator i,
                                   const Val& val) {
      return this->_M_insert_unique_(i, val);
    }

    Val& operator[](const Key& key) {
      auto i = this->lower_bound(key);
      if (i == this->end() || this->key_comp()(key, Extract()(*i))) {
        i = this->_M_insert_unique_(i, Val(key));
      }
      return *i;
    }
};

要完成这项工作，您需要提供一个密钥提取器，如下所示：

template<class T>
struct KeyExtractor;

template<>
struct KeyExtractor<Node> {
  const std::string& operator()(const Node& n) { return n.name(); }
};

要使我的 operator[] 版本正常工作，您需要值类型具有一个构造函数，该构造函数将其键类型作为参数。

我遗漏了很多东西（例如擦除）；但是做一个简单的测试就足够了。

从 KeyExtractor 的返回类型中默认键类型可能会更好，但这会涉及以不同的顺序放置模板参数，而且我已经浪费了太多时间没有注意到 _M_insert_unique 和 _M_insert_unique_ 拼写不同（大概是为了避免模板实例化问题。）

这是我用来检查以确保有效的示例；MyKeyedClass 有一个名称，带有一个字符串向量，以及一个与每个字符串相关联的双精度值。（没有崇高的目的。）

int main(void) {
  keyed_set<std::string, MyKeyedClass, KeyExtractor<MyKeyedClass>> repo;
  for (std::string name, val; std::cin >> name >> val; ) {
    try {
      size_t end;
      double d = std::stod(val, &end);
      if (end != val.size())
        throw std::invalid_argument("trailing letters");
      repo[name].increment(d);
    } catch (std::invalid_argument(e)) {
      repo[name].push(val);
    } catch (std::out_of_range(e)) {
      std::cerr << "You managed to type an out of range double" << std::endl;
    }
  }
  std::for_each(repo.begin(), repo.end(),
                [](MyKeyedClass& c){ std::cout << c << std::endl; });
  return 0;
}
于 2012-10-06T02:48:38.273 回答
1

我认为因为在构造过程中Node需要引用Directory，所以创建一个虚拟节点来按名称搜索您的集合将使Node类更加混乱。

要使用set，您可能需要在Directory某处创建一个静态，并将其用作新的虚拟构造函数中的虚拟引用Node(const std::string&)。如果您不声明explicit可以string直接在调用set::find.

您可以改为将类转换为使用指针...但这会改变其内部语义：Directory&始终有效，而Directory*不必如此。问问自己，是否仅仅因为您对set容器的偏好而使读者对语义不太清楚。

所以我的观点在这种情况下很清楚......你有一个选择：要么使用map并保持你的类干净，要么使用set并编写一些对其他任何东西都没有用的支持垃圾代码。=)

于 2012-10-06T02:42:17.180 回答
1

我通过键的代理来实现这样的类，例如在 std::string 的情况下，我有一个名为轻量级字符串的类，它实现operator <并在内部指向我使用的std::string然后我使用map的并且具有使用 map 的简单性和没有 2 的性能密钥的版本。

于 2012-10-06T00:31:43.270 回答
1

对于您的情况，请检查您的编译器是否足够老，仍然std::string可以使用 COW（写入时复制）策略来实现。这在 C++11 中发生了变化，但旧的编译器版本仍然是 COW... 这有一个优点，即使用字符串作为键和作为值的一部分的映射几乎不会花费您任何成本。但请注意，这将在未来改变（或已经改变）......

于 2012-10-06T02:34:31.243 回答