native_multimap.hpp [plain text]
#ifndef PB_DS_NATIVE_MULTIMAP_HPP
#define PB_DS_NATIVE_MULTIMAP_HPP
#include <map>
#include <string>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <native_type/assoc/native_tree_tag.hpp>
namespace pb_ds
{
namespace test
{
#define PB_DS_BASE_C_DEC \
std::multimap<Key, Data, Less_Fn, \
typename Allocator::template rebind<std::pair<const Key, Data> >::other>
template<typename Key, typename Data, class Less_Fn = std::less<Key>,
class Allocator = std::allocator<char> >
class native_multimap : public PB_DS_BASE_C_DEC
{
private:
typedef PB_DS_BASE_C_DEC base_type;
public:
typedef native_tree_tag container_category;
typedef Allocator allocator;
typedef
typename Allocator::template rebind<
std::pair<Key, Data> >::other::const_reference
const_reference;
typedef typename base_type::iterator iterator;
typedef typename base_type::const_iterator const_iterator;
native_multimap() { }
template<typename It>
native_multimap(It f, It l) : base_type(f, l)
{ }
inline void
insert(const_reference r_val)
{
typedef std::pair<iterator, iterator> eq_range_t;
eq_range_t f = base_type::equal_range(r_val.first);
iterator it = f.first;
while (it != f.second)
{
if (it->second == r_val.second)
return;
++it;
}
base_type::insert(r_val);
}
inline iterator
find(const_reference r_val)
{
typedef std::pair<iterator, iterator> eq_range_t;
eq_range_t f = base_type::equal_range(r_val.first);
iterator it = f.first;
while (it != f.second)
{
if (it->second == r_val.second)
return it;
++it;
}
return base_type::end();
}
inline const_iterator
find(const_reference r_val) const
{
typedef std::pair<const_iterator, const_iterator> eq_range_t;
eq_range_t f = base_type::equal_range(r_val.first);
const_iterator it = f.first;
while (it != f.second)
{
if (it->second == r_val.second)
return it;
++it;
}
return base_type::end();
}
static std::string
name()
{ return std::string("n_mmap"); }
static std::string
desc()
{ return make_xml_tag("type", "value", "std_multimap"); }
};
#undef PB_DS_BASE_C_DEC
}
}
#endif // #ifndef PB_DS_NATIVE_MULTIMAP_HPP