#include <vector>
#include <algorithm>
//############################################################### ptrvect
/// Vector of Pointers
#line 4 "vecset.cpp.fi"
template <class T, class base = std::vector<T*> >
class ptrvect: public base {
public:
class iterator: public base::iterator {
friend class ptrvect;
iterator(const typename base::const_iterator& it):
base::iterator(const_cast<T**>(&*it)) {
return; }
public:
iterator(const typename base::iterator& it):
base::iterator(it) {
return; }
T* operator->() const {
return **this; }};
class const_iterator: public base::const_iterator {
public:
const_iterator(const typename base::const_iterator& it):
base::const_iterator(it) {
return; }
const_iterator(const typename base::iterator& it):
base::const_iterator(it) {
return; }
T* operator->() const {
return **this; }};
template <class It = iterator>
class condpair: public std::pair<It,bool> {
public:
condpair(It it, bool second):
std::pair<It,bool>(it, second) {
return; }
T* operator->() const {
return *std::pair<It,bool>::first; }};
public:
iterator begin() {
return iterator(base::begin()); }
iterator end() {
return iterator(base::end()); }
const_iterator begin() const {
return const_iterator(base::begin()); }
const_iterator end() const {
return const_iterator(base::end()); }
public: // workarounds for pre-C++11 / bad C++11 implementation (should allow const_iterator)
iterator insert(const_iterator pos, T* value) {
return base::insert(iterator(pos), value); }
iterator erase(const_iterator pos) {
return base::erase(iterator(pos)); }
public: // addons
iterator find (T* key) {
return std::find(begin(), end(), key); }
const_iterator find (T* key) const {
return std::find(begin(), end(), key); }
bool contains (T* key) const {
return find(key) != end(); }
T* remove(T* key) {
auto it = find(key);
if (it == end()) return nullptr;
T* val = *it;
base::erase(it);
return val; }
T* add(T* val) {
base::push_back(val);
return val; }
void release() {
for (T* it : *this) delete it;
base::clear(); }};
//###################################################### vset: comparator
namespace detail { namespace vset {
/// Get Key Functor for Vector-Set
template <class T, class K>
struct get_key {
K operator() (T* it) const {
return (K)(*it); }};
template <class T>
struct get_key<T,T*> {
T* operator() (T* it) const {
return it; }};
/// Comparator Functor for Vector-Set
template <class T, class K=T,
class Less = std::less<K>, class GetKey = get_key<T,K>>
class comparator: protected GetKey, protected Less {
public:
const GetKey& get_key() const {
return static_cast<const GetKey&>(*this); }
const Less& less() const {
return static_cast<const Less&>(*this); }
K operator() (T* it) const {
return get_key()(it); }
bool operator() (K x, K y) const {
return less()(x, y); }
bool operator() (T* x, K y) const {
return less()(get_key()(x), y); }
bool operator() (K x, T* y) const {
return less()(x, get_key()(y)); }
bool operator() (T* x, T* y) const {
return less()(get_key()(x), get_key()(y)); }};
template <class T, class Less, class GetKey>
class comparator<T,T*,Less,GetKey>:
protected GetKey, protected Less {
public:
const GetKey& get_key() const {
return static_cast<const GetKey&>(*this); }
const Less& less() const {
return static_cast<const Less&>(*this); }
T* operator() (T* it) const {
return get_key()(it); }
bool operator() (T* x, T* y) const {
return less()(x, y); }};
//============================================================ vset: base
/// Vector-Set Basic Implementation
template <class T, class K=T,
class Less = std::less<K>,
class GetKey = get_key<T,K>>
class base: protected comparator<T,K,Less,GetKey>, protected ptrvect<T> {
typedef ptrvect<T> core;
protected:
// disable polymorphic destruction by hiding non-virtual destructor
~base() {
return; }
const comparator<T,K,Less,GetKey>& comp() const {
return static_cast<const comparator<T,K,Less,GetKey>&>(*this); }
public:
// pointers cannot be changed -> iterator = const_iterator
typedef typename core::const_iterator iterator, const_iterator;
typedef typename core::template condpair<iterator> condpair;
typedef T *value_type;
typedef K key_type;
using core::size_type;
using core::size;
using core::empty;
iterator begin() const {
return core::begin(); }
iterator end() const {
return core::end(); }
public:
iterator lower_bound(K key) const {
return std::lower_bound(begin(), end(), key, comp()); }
iterator upper_bound(K key) const {
return std::upper_bound(begin(), end(), key, comp()); }
std::pair<iterator, iterator> equal_range(K key) const {
return std::equal_range(begin(), end(), key, comp()); }
iterator find(K key) const {
iterator it = lower_bound(key);
return it == end() || comp()(key, *it) ? end() : it; }
bool contains(K key) const {
iterator it = lower_bound(key);
return it != end() && !comp()(key, *it); }
public:
template<class... Args>
condpair emplace(K key, Args&& ...args) {
iterator it = lower_bound(key);
if (it == end() || comp()(key, *it)) {
return condpair(core::insert(it,
new T(key, std::forward<Args>(args)...)), true); }
return condpair(it, false); }
iterator erase(iterator at) {
return core::erase(at); }
public:
T* add(T* value) {
K key = comp()(value);
iterator it = lower_bound(key);
if (it == end() || comp()(key, *it)) {
core::insert(it, value);
return value; }
return nullptr; }
template<class... Args>
T* add(K key, Args&& ...args) {
iterator it = lower_bound(key);
if (it == end() || comp()(key, *it)) {
T* value = new T(key, std::forward<Args>(args)...);
core::insert(it, value);
return value; }
return nullptr; }
T* get(K key) const {
iterator it = find(key);
return it == end() ? nullptr : *it; }
T* operator[](K key) const {
return *emplace(key).first; }
T* remove(K key) {
iterator it = find(key);
if (it == end()) return nullptr;
T* value = *it;
core::erase(it);
return value; }
void release() {
for (T* it : *this) {
delete it; }
core::clear(); }
void clear() {
core::clear(); }};
//================================================================== vset
}}
template <class T, class K=T,
class Less = std::less<K>,
class GetKey = detail::vset::get_key<T,K>>
class vset: public detail::vset::base<T,K,Less,GetKey> {
typedef detail::vset::base<T,K,Less,GetKey> base;
protected:
using base::comp;
public:
typedef typename base::iterator iterator;
using base::begin; using base::end; using base::remove; using base::find;
using base::lower_bound; using base::upper_bound; using base::equal_range;
T* remove(T* value) {
return remove(comp()(value)); }
iterator find(T* value) const {
K key = comp()(value);
iterator it = lower_bound(key);
return it == end() || comp()(key, *it) ? end() : it; }
iterator lower_bound(T* value) const {
return std::lower_bound(begin(), end(), value, comp()); }
iterator upper_bound(T* value) const {
return std::upper_bound(begin(), end(), value, comp()); }
std::pair<iterator, iterator> equal_range(T* value) const {
return std::equal_range(begin(), end(), value, comp()); }};
//============================================================ vset: K=T*
template <class T, class Less, class GetKey>
class vset<T,T*,Less,GetKey>:
public detail::vset::base<T,T*,Less,GetKey> {};
//############################################################### testing
#include <iostream>
#include <cstring>
#line 224 "vecset.cpp.fi"
using std::cout; using std::endl; using std::string;
class User {
string name_;
public:
User(string name): name_(std::move(name)) {
return; }
const char * name() const {
return name_.c_str(); }
struct get_key {
const char * operator() (User* u) const {
return u->name(); }};};
struct str_less {
bool operator() (const char *lhs, const char *rhs) const {
return std::strcmp(lhs, rhs) < 0; }};
int main() {
vset<User,const char*,str_less,User::get_key> users;
users.add("firda");
for (auto p : users) cout << p->name() << endl;
auto it = users.find("firda");
cout << it->name() << endl;
it = users.find(*it);
cout << it->name() << endl;
vset<int,int*> ints;
int* i = ints.add(new int(1));
auto j = ints.find(i);
cout << **j << endl; }