/* * bag: T -> N bag * (C) Porkolab Zoltan, ELTE, Budapest, Hungary * (C) 2001 */ // 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; }