Трябва ли да използвам карта или набор, ако моят ключ е част от моята стойност?

В C++ имам клас, който е подреден по името си, което е std::string. Искам да имам само по един за всяко уникално име в std::map или 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;

};

c++ key stdmap stdset
person WilliamKF    schedule 05.10.2012    source източник
comment
Зададох много подобен въпрос преди. Всъщност всички отговори бяха доста добри. Единствената разлика е, че вашият включва сравнения, а моят включва хеширане - map срещу unordered_map.   -  person Joseph Mansfield    schedule 06.10.2012
comment
Може да помогне да видите вашия клас.   -  person ThomasMcLeod    schedule 06.10.2012
comment
Мисля, че set често се имплементира като специален случай на map така или иначе, така че вероятно не си купувате много по отношение на производителността. Един подход може да бъде да се приложи по отношение на карта, но да се осигури интерфейс, който е ограничен да бъде по-скоро „подобен на набор“, просто не стигайки почти до самия набор. IMO, това би било по-лесно, отколкото да отидете наобратно и да се опитате да опаковате комплекта.   -  person WeirdlyCheezy    schedule 06.10.2012

Отговори (4)


arrow_upward
1
arrow_downward

Мисля, че тъй като Node изисква препратка към Directory по време на конструирането, създаването на фиктивен възел за търсене на вашия набор по име ще направи класа Node по-затрупан.

За да използвате set, вероятно ще трябва да направите статичен Directory някъде и да го използвате като фиктивна препратка в нов фиктивен конструктор Node(const std::string&). Ако не декларирате това explicit, можете да използвате string директно във вашето обаждане до set::find.

Вместо това бихте могли да преобразувате класа да използва указатели... Но това би променило вътрешната му семантика: Directory& винаги е валидно, докато Directory* не е задължително. Запитайте се дали искате да направите семантиката по-малко ясна за читателя просто поради предпочитанията си към контейнера set.

Така че моето мнение е доста ясно в този случай... Имате избор: Или използвайте map и поддържайте класа си чист, или използвайте set и напишете малко поддържащ нежелан код, който няма полза за нищо друго. =)

person paddy    schedule 06.10.2012

arrow_upward
2
arrow_downward

Всъщност, можете просто да използвате map‹std::string&, Node›, с цената на един допълнителен указател, но мисля, че вероятно сте го знаели, и това изисква известно изхвърляне, за да получите това, което искате.

Винаги съм смятал, че е истинска болка, че std::set не идва с изричен параметър на шаблона на KeyExtractor, особено след като всяка реализация, която съм виждал, използва един от тези под капака, за да не дублира код между (multi )карти и (мулти)множества. Ето един бърз и мръсен хак, който не е почти завършен, който разкрива някои от механизмите на стандартната C++ библиотека на GNU, за да се създаде контейнер "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;
    }
};

За да работи това, трябва да предоставите Key Extractor, като този:

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;
}
person rici    schedule 06.10.2012

arrow_upward
1
arrow_downward

Внедрявам такива класове чрез прокси за ключ, например в случай на std::string имам клас, наречен lightweight_string, който имплементира operator < и вътрешно сочи към std::string, след което използвам map и има както простота на използване на map, така и производителност на без 2 версии на ключа.

person BigBoss    schedule 06.10.2012

arrow_upward
1
arrow_downward

За вашия случай проверете дали вашият компилатор е достатъчно стар, за да все още прилага std::string със стратегия COW (копиране при запис). Това се промени в C++11, но старите версии на компилатора все още са крави... Това има предимството, че няма да ви струва почти нищо да имате map с низ като ключ и като част от стойността. Но имайте предвид, че това ще се промени в бъдеще (или вече е променено)...

person PiotrNycz    schedule 06.10.2012