Problems, issues:
#include <map>
int main()
{
std::map<float> fm1;
std::map<float, std::less<float> > fm2;
return fm1 == fm2;
}
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;
RuntimeCmp<int> reverse(RuntimeCmp<int>::reverse);
set<int, RuntimeCmp<int> > s2(reverse);
cout << "Same sorting: " << (s1.value_comp() == s2.value_comp()) << endl;
s2 = s1;
cout << "Same sorting: " << (s1.value_comp() == s2.value_comp()) << endl;
return 0;
}
#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;
}
#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;
}
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.erase(ci);
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()
{
set<string> coll((istream_iterator<string>(cin)),
(istream_iterator<string>()));
copy (coll.begin(), coll.end(),
ostream_iterator<string>(cout, "\n"));
}
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<string> coll((istream_iterator<string>(cin)),
(istream_iterator<string>()));
sort (coll.begin(), coll.end());
unique_copy (coll.begin(), coll.end(),
ostream_iterator<string>(cout, "\n"));
}
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()
vector:
dynamic array, random access,
iterator invalidates:
when realloc
deque:
array of arrays, random access
iterator invalidates:
insertion, and deletion other than front() and back()
deleting front() or back() invalidates only iterators referring them
it is possible that iterators are invalidated but pointers not
list:
bidirectional linked list, linear access
iterator invalidates:
only referring to deleted items
associative:
(typically) red-black tree, logarithmical access
iterator invalidates:
only referring to deleted items