Должен ли я использовать карту или набор, если мой ключ является частью моего значения?
В 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;
};
Решение
Я думаю, потому что Node требуется ссылка на Directory во время построения создание фиктивного узла для поиска вашего набора по имени сделает Node класс более загроможден.
Использовать set вам, вероятно, нужно сделать статический Directory где-нибудь, и использовать это как фиктивную ссылку в новом фиктивном конструкторе Node(const std::string&), Если вы не заявите, что explicit Вы можете использовать string прямо в вашем звонке set::find,
Вместо этого вы можете преобразовать класс для использования указателей … Но это изменит его внутреннюю семантику: Directory& всегда действует, тогда как Directory* не должно быть Спросите себя, хотите ли вы сделать семантику менее понятной для читателя просто из-за того, что вы предпочитаете set контейнер.
Так что мое мнение довольно ясно в этом случае … У вас есть выбор: либо использовать map и держать ваш класс в чистоте, или использовать set и написать немного вспомогательного кода, который бесполезен ни для чего другого. знак равно
Другие решения
На самом деле, вы можете просто использовать карту<станд :: строка&Узел>, за счет одного дополнительного указателя, но я думаю, что вы, вероятно, знали это, и для того, чтобы получить то, что вам нужно, нужно немного позабавиться.
Я всегда думал, что это настоящая боль, что 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;
}
Я реализую такие классы через прокси для ключа, например, в случае std :: string у меня есть класс с именем lightweight_string, который реализует operator < и внутренне это указывает на std::string тогда я использую map и иметь как простоту использования карты, так и производительность, не имея 2 версии ключа.
Для вашего случая убедитесь, что ваш компилятор достаточно стар, чтобы все еще реализовать std::string с COW (копирование на запись) стратегии. Это изменилось в C ++ 11, но старые версии компилятора все еще являются COWs … Это имеет то преимущество, что вам почти ничего не будет стоить иметь карту со строкой в качестве ключа и как часть значения. Но знайте, что это изменится в будущем (или уже изменилось) …