3

C ++には、。という名前で並べ替えられたクラスがありstd::stringます。std::mapaまたは。のいずれかで一意の名前ごとに1つだけにしたいstd::set

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>を使用できますが、1つの追加ポインターが必要ですが、おそらくそれを知っていると思います。必要なものを取得するには、多少の工夫が必要です。

std :: setに明示的なKeyExtractorテンプレートパラメータが付属していなかったのは本当に苦痛だといつも思っていました。特に、これまでに見たすべての実装では、(multi )マップと(マルチ)セット。これは、「keyed_set」コンテナを作成するために、GNU標準C ++ライブラリのメカニズムの一部を公開する、完全ではない、迅速で汚いハックです。

// 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には名前があり、文字列のベクトルと、それぞれに関連付けられたdoubleがあります。(崇高な目的はありません。)

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使用できることを宣言しない場合。stringset::find

代わりに、ポインタを使用するようにクラスを変換することもできます...しかし、それはその内部セマンティクスを変更します:Directory&常に有効ですが、そうである必要はありDirectory*ません。set単にコンテナを好むという理由だけで、読者にセマンティクスをわかりにくくしたいかどうかを自問してください。

したがって、この場合、私の意見はかなり明確です...あなたには選択肢がmapあります。クラスを使用してクリーンに保つかset、他に何の役にも立たないサポートジャンクコードを少し使用して記述します。=)

于 2012-10-06T02:42:17.180 に答える
1

std::stringあなたの場合は、コンパイラがCOW(コピーオンライト)戦略を実装するのに十分古いかどうかを確認してください。これはC++11で変更されましたが、古いコンパイラバージョンはまだCOWです...これには、文字列をキーとして、値の一部としてマップを作成するのにほとんど費用がかからないという利点があります。ただし、これは将来変更される(またはすでに変更されている)ことに注意してください...

于 2012-10-06T02:34:31.243 に答える
1

このようなクラスは、キーのプロキシを介して実装します。たとえば、std :: stringの場合、lightweight_stringというクラスがあり、実装operator <して内部的にそれを指し、マップをstd::string使用mapする単純さと2を持たないパフォーマンスの両方を備えています。キーのバージョン。

于 2012-10-06T00:31:43.270 に答える