Associative containers


Types defined in Map


template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class std::map {
public:
    // types:

    typedef Key key_type;
    typedef T mapped_type;

    typedef pair<const Key, T> value_type;

    typedef Cmp key_compare;
    typedef A allocator_type;

    typedef typename A::reference reference;
    typedef typename A::const_reference const_reference;

    typedef implementation_defined1 iterator;
    typedef implementation_defined2 const_iterator;

    typedef typename A::size_type size_type;
    typedef typename A::difference_type difference_type;

    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    // ...
};


/*
 *  Iterators of map
 *
 */

template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > > class map {
public:
    // ...
    // iterators:

    iterator begin();
    const_iterator begin() const;

    iterator end();
    const_iterator end() const;

    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;

    reverse_iterator rend();
    const_reverse_iterator rend() const;

    // ...
};


/*
 *  Usage of map
 *
 */

void f(map<string,number>& phone_book)
{
    typedef map<string,number>::const_iterator CI;
    for (CI p = phone_book.begin(); p!=phone_book.end(); ++p)
        cout << p->first << '\et' << p->second << '\en';
}


/*
 *  Pair
 *
 */

template <class T1, class T2> struct std::pair {
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;

    pair() :first(T1()), second(T2()) { }
    pair(const T1& x, const T2& y) :first(x), second(y) { }
    template<class U, class V>
        pair(const pair<U, V>& p) :first(p.first), second(p.second) { }
};


template <class Key, class T, class Cmp =less<Key>,
        class A =allocator<pair<const Key,T> > >
class map {
public:
    // ...
    // construct/copy/destroy:

    explicit map(const Cmp& = Cmp(), const A& = A());
    template <class In> map(In first, In last, const Cmp& = Cmp(), const A& = A());
    map(const map&);

    ~map();

    map& operator=(const map&);

    // ...
};


//  Using compare for associative containers

template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...

    typedef Cmp key_compare;

    class value_compare : public binary_function<value_type,value_type,bool>
    {
    friend class map;
    protected:
    Cmp cmp;
        value_compare(Cmp c) : cmp(c) {}
    public:
    bool operator()(const value_type& x, const value_type& y) const
        { return cmp(x.first, y.first); }
    };

    key_compare key_comp() const;
    value_compare value_comp() const;
    // ...
};


/*
 *  Usage of comparison
 *
 */

map<string,int> m1;
map<string,int,Nocase> m2;      // specify comparison type (_cont.comp_)
map<string,int,String_cmp> m3;  // specify comparison type (_cont.comp_)
map<string,int,String_cmp> m4(String_cmp(literary));// pass comparison object


void f(map<string,int>& m)
{
    map<string,int> mm;         // compare using < by default
    map<string,int> mmm(m.key_comp());  // compare the way m does
    // ...
}


template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...
    mapped_type& operator[](const key_type& k); // access element with key k
    // ...
};


void f()
{
    map<string,int> m;  // map starting out empty
    int x = m["Henry"]; // create new entry for "Henry", initialize to 0, return 0
    m["Harry"] = 7;     // create new entry for "Harry", initialize to 0, and assign 7
    int y = m["Henry"]; // return the value from "Henry"'s entry
    m["Harry"] = 9;     // change the value from "Harry"'s entry to 9
}


template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...
    // list operations:

    pair<iterator, bool> insert(const value_type& val);     // insert (key,value) pair
    iterator insert(iterator pos, const value_type& val);   // pos is just a hint
    template <class In> void insert(In first, In last);     // insert elements from sequence

    void erase(iterator pos);           // erase the element pointed to
    size_type erase(const key_type& k); // erase element with key k (if present)
    void erase(iterator first, iterator last);  // erase range
    void clear();               // Erase all elements

    // ...
};


void f(map<string,int>& m)
{
    pair<string,int> p99("Paul",99);

    pair<map<string,int>::iterator,bool> p = m.insert(p99);
    if (p.second) {
        // "Paul" was inserted
    }
    else {
        // "Paul" was there already
    }
    map<string,int>::iterator i = p.first;  // points to m["Paul"]
    // ...
}

template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...
    // map operations:

    iterator find(const key_type& k);           // find element with key k
    const_iterator find(const key_type& k) const;

    size_type count(const key_type& k) const;   // find number of elements with key k

    iterator lower_bound(const key_type& k);    // find first element with key k
    const_iterator lower_bound(const key_type& k) const;
    iterator upper_bound(const key_type& k);    // find first element with key greater than k
    const_iterator upper_bound(const key_type& k) const;

    pair<iterator,iterator> equal_range(const key_type& k);
    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;

    // ...
};

void f(map<string,int>& m)
{
    map<string,int>::iterator p = m.find("Gold");
    if (p!=m.end()) {               // if "Gold" was found
        // ...
    }
    else if (m.find("Silver")!=m.end()) {   // look for "Silver"
    // ...
    }
    // ...
}

void f(multimap<string,int>& m)
{
    multimap<string,int>::iterator lb = m.lower_bound("Gold");
    multimap<string,int>::iterator ub = m.upper_bound("Gold");

    for (multimap<string,int>::iterator p = lb; p!=ub; ++p) {
        // ...
    }
}