如果我的鑰匙是我的價值的一部分，我應該使用地圖還是集合？

Question

在C++中，我有一個按名稱排序的類，它是std::string。我希望在std::map或std::set中每個唯一名稱只有一個。

我可以使用std::set，因爲operator<將通過名稱排序我的實例，但是，我需要通過名稱來查找實例。然而，使用鍵是名字的映射是直接的，但是，我也可以使用一個集合並構造一個我的類的虛擬實例，其名稱是我希望查找的集合中定位給定類的實際實例名稱。

我想我應該隨地圖一起使代碼簡單直接，但不知道是否可能有一種方法去設置，因爲密鑰實際上是我的對象的一部分，從而避免了一些冗餘。

有沒有辦法使用該設置，並能夠通過他們的鍵以清晰的方式定位對象，或者我應該只使用一張地圖並完成它？

下面是要被插入（草稿形式）的類，並在每一個目錄中有任一鍵固定切斷節點名稱的集合或節點（S）的圖：

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; 

}; 

Answer 1

我認爲，因爲Node需要在施工期間Directory的引用，使得一個虛擬節點按名稱來搜索您所設定將使Node類比較凌亂。

要使用set，您可能需要在某處創建一個靜態的Directory，並將其用作新虛擬構造函數Node(const std::string&)中的虛擬引用。如果您不聲明explicit，則可以在致電set::find時直接使用string。

您可以改爲將類轉換爲使用指針......但是這會改變它的內部語義：Directory&總是有效的，而Directory*不一定是。問問自己，是否僅僅因爲您對set容器的偏好而讓讀者不清楚語義。

所以我的意見是在這種情況下，很清楚......你有一個選擇：要麼使用map並保持你的級潔淨，或使用set和寫一點支持有沒有使用別的垃圾代碼。 =）

Answer 2

我實現通過這樣的類一個密鑰的代理，例如在std :: string的情況下我有一個名爲lightweight_string的類，實現operator <，它在內部指向std::string，然後我使用map，並且具有使用map的簡單性和不具有2版本的性能鍵。

Answer 3

爲了您的實際情況，請檢查您的編譯器是否足夠大，以便仍然使用COW（寫入時複製）策略實施std::string。這在C++ 11中有所改變，但舊的編譯器版本仍然是COW ...這具有以下優點：將字符串作爲關鍵字和值的一部分進行映射幾乎不會花費任何代價。但要知道，這將在未來的（或已經改變）改變...

Answer 4

其實，你可以使用地圖<的std :: string &，節點>，在一個額外的指針的成本，但我想你可能知道，它需要一些瞎得到你想要的東西。

我一直認爲這是一個真正的痛苦，std :: set沒有帶有明確的KeyExtractor模板參數，特別是因爲我見過的每個實現都使用其中一個引擎蓋以避免重複（多）地圖和（多）集之間的代碼。這裏有一個快速和骯髒的黑客，而不是接近完成，這暴露出一些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有一個名稱，帶有一個字符串矢量，以及一個與每個字符串關聯的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; 
}