Problems, issues:


#include <map>

int main()
{
    std::map<float> fm1;
    std::map<float, std::less<float> >  fm2;

    return fm1 == fm2;
}
// pr1.cpp: In function `int main()':
// pr1.cpp:6: wrong number of template arguments (1, should be 4)
// /usr/include/g++/bits/stl_map.h:80: provided for `template<class _Key, class
//   _Tp, class _Compare, class _Alloc> class std::map'
// pr1.cpp:6: warning: ISO C++ forbids declaration of `fm1' with no type
// pr1.cpp:9: no match for `int& == std::map<float, std::less<float>,
//   std::less<float>, std::allocator<std::pair<const float, std::less<float> > > >&' operator




Adequate usage of STL:


#include <iostream>
#include <set>

using namespace std;

template <typename T>
class RuntimeCmp
{
public:
    enum cmp_mode { normal, reverse };

    RuntimeCmp( cmp_mode m = normal ) : mode(m) { }
    bool operator()(const T& t1, const T& t2) const {
        return mode == normal ? t1 < t2 : t2 < t1;
    }
    bool operator==( const RuntimeCmp& rhs) {
        return mode == rhs.mode;
    }
private:
    cmp_mode mode;
};

int main()
{
    set<int, RuntimeCmp<int> >  s1;          // set with normal sorting
    RuntimeCmp<int>     reverse(RuntimeCmp<int>::reverse);
    set<int, RuntimeCmp<int> >  s2(reverse); // set with reverse sorting

    cout << "Same sorting: " << (s1.value_comp() == s2.value_comp()) << endl;

    s2 = s1;    // copy with the sorting criteria
    cout << "Same sorting: " << (s1.value_comp() == s2.value_comp()) << endl;

    return 0;
}



// implementation with list

#include <list>
#include <algorithm>

template <class T>
class bag
{
public:
    void put( const T& t);
    bool remove( const T& t);
    bool remove_all( const T& t);
    int  mul( const T& t) const;
private:
    struct my_pair
    {
        my_pair(T f, int s) : first(f), second(s) { }
        T   first;
        int second;
        int operator==(const my_pair& x) const { return first == x.first; }
    };
    std::list<my_pair> lst;
};

template <class T>
int bag<T>::mul( const T& t) const
{
    my_pair mp(t,1);
    typename std::list<my_pair>::const_iterator ci =
                find(lst.begin(), lst.end(), mp);

    return  ci == lst.end() ? 0 : ci->second;
}

template <class T>
void bag<T>::put( const T& t)
{
    my_pair mp(t,1);
    typename std::list<my_pair>::iterator ci =
                find(lst.begin(), lst.end(), mp);

    if ( ci == lst.end() )
    {
        lst.push_back(mp);
    }
    else
    {
        ++ ci->second;
    }
}

template <class T>
bool bag<T>::remove( const T& t)
{
    my_pair mp(t,1);
    typename std::list<my_pair>::iterator ci =
                find(lst.begin(), lst.end(), mp);

    if ( ci != lst.end() )
    {
        if( 0  ==  -- ci->second )
            lst.erase(ci);
        return true;
    }
    return false;
}

template <class T>
bool bag<T>::remove_all( const T& t)
{
    my_pair mp(t,1);
    typename std::list<my_pair>::iterator ci =
                find(lst.begin(), lst.end(), mp);

    if ( ci != lst.end() )
    {
        lst.erase(ci);
        return true;
    }
    return false;
}



// implementation with map

#include <map>
#include <algorithm>

template <class T>
class bag
{
public:
    void put( const T& t);
    bool remove( const T& t);
    bool remove_all( const T& t);
    int  mul( const T& t) const;
private:
    std::map< T, int>  m_map;
};


template <class T>
int bag<T>::mul( const T& t) const
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);
    return  ci == m_map.end() ? 0 : ci->second;
}

template <class T>
void bag<T>::put( const T& t)
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci == m_map.end() )
        m_map[t] = 1;
    else
        ++ m_map[t];
}

template <class T>
bool bag<T>::remove( const T& t)
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci != m_map.end() )
    {
        if ( 0 == -- m_map[t] )
            m_map.erase(t);
        return true;
    }
    return false;
}

template <class T>
bool bag<T>::remove_all( const T& t)
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci != m_map.end() )
    {
        m_map.erase(t);
        return true;
    }
    return false;
}



// improvements

template <class T>
void bag<T>::put( const T& t)
{
    ++ m_map[t];
}

template <class T>
bool bag<T>::remove( const T& t)
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci != m_map.end() )
    {
        if ( 0 == -- ci->second )   // m_map[t]
            m_map.erase(ci);        // m_map.erase(t)
        return true;
    }
    return false;
}

template <class T>
bool bag<T>::remove_all( const T& t)
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci != m_map.end() )
    {
        m_map.erase(ci);
        return true;
    }
    return false;
}




Associative containers are not always better


#include <iostream>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

int main()
{
    /* create a string set
     * - initialized by all words from standard input
     */
    set<string> coll((istream_iterator<string>(cin)),
                     (istream_iterator<string>()));

    // print all elements
    copy (coll.begin(), coll.end(),
          ostream_iterator<string>(cout, "\n"));
}


// The following code example is taken from the book
// The C++ Standard Library - A Tutorial and Reference
// by Nicolai M. Josuttis, Addison-Wesley, 1999
// (C) Copyright Nicolai M. Josuttis 1999


#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    /* create a string vector
     * - initialized by all words from standard input
     */
    vector<string> coll((istream_iterator<string>(cin)),
                        (istream_iterator<string>()));

    // sort elements
    sort (coll.begin(), coll.end());

    // print all elements ignoring subsequent duplicates
    unique_copy (coll.begin(), coll.end(),
                 ostream_iterator<string>(cout, "\n"));
}



//  150.000 string:  vector solution is better with 10%
//       + reserve:                                 15%
// multiset + copy:                                 40%



Which container to use



                    vector    deque      list       set    multiset    map     multimap

typical internal    dynamic  array of    doubly    binary   binary    binary    binary
data structure      array     arrays   linked list  tree     tree      tree      tree

elements            value      value     value     value    value    key/value key/value

duplicates allowed   yes        yes       yes        no       yes       no        yes

random access        yes        yes       no         no       no      with key    no
iterator category   random    random   bidirect.  bidirect. bidirect. bidirect. bidirect.

search/find elem     slow      slow    very slow    fast      fast    fast(key) fast(key)

fast insert/remove  at end    at begin  abywhere     ---       ---       ---       ---
                              and end
inserting/removing
invalidates        on realloc  always     never     never     never     never     never
iterator, ptr, ref

frees memory         never    sometimes   always    always    always    always    always
for removed elems

allows memory         yes         no        ---       ---       ---        ---      ---
reservation

transaction safe  push_back() push_back()    all    all (except multiple element insert())
(success or       pop_back()  pop_back()   (except
 no effect)                   push_front()  sort())
                              pop_front()