SHARE
TWEET

Sorted Vector aka Flat Set

firdacz Sep 8th, 2014 230 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <algorithm>
  3. //############################################################### ptrvect
  4. /// Vector of Pointers
  5. template <class T, class base = std::vector<T*> >
  6.   class ptrvect: public base {
  7. public:
  8.     class iterator: public base::iterator {
  9.         friend class ptrvect;
  10.         iterator(const typename base::const_iterator& it):
  11.           base::iterator(const_cast<T**>(&*it)) {
  12.             return;
  13.         }
  14.     public:
  15.         iterator(const typename base::iterator& it):
  16.           base::iterator(it) {
  17.             return;
  18.         }
  19.         T* operator->() const {
  20.             return **this;
  21.         }
  22.     };
  23.     class const_iterator: public base::const_iterator {
  24.     public:
  25.         const_iterator(const typename base::const_iterator& it):
  26.           base::const_iterator(it) {
  27.             return;
  28.         }
  29.         const_iterator(const typename base::iterator& it):
  30.           base::const_iterator(it) {
  31.             return;
  32.         }
  33.         T* operator->() const {
  34.             return **this;
  35.         }
  36.     };
  37.     template <class It = iterator>
  38.       class condpair: public std::pair<It,bool> {
  39.     public:
  40.         condpair(It it, bool second):
  41.           std::pair<It,bool>(it, second) {
  42.             return;
  43.         }
  44.         T* operator->() const {
  45.             return *std::pair<It,bool>::first;
  46.         }
  47.     };
  48. public:
  49.     iterator begin() {
  50.         return iterator(base::begin());
  51.     }
  52.     iterator end() {
  53.         return iterator(base::end());
  54.     }
  55.     const_iterator begin() const {
  56.         return const_iterator(base::begin());
  57.     }
  58.     const_iterator end() const {
  59.         return const_iterator(base::end());
  60.     }
  61. public: // workarounds for pre-C++11 / bad C++11 implementation (should allow const_iterator)
  62.     iterator insert(const_iterator pos, T* value) {
  63.         return base::insert(iterator(pos), value);
  64.     }
  65.     iterator erase(const_iterator pos) {
  66.         return base::erase(iterator(pos));
  67.     }
  68. public: // addons
  69.     iterator find (T* key) {
  70.         return std::find(begin(), end(), key);
  71.     }
  72.     const_iterator find (T* key) const {
  73.         return std::find(begin(), end(), key);
  74.     }
  75.     bool contains (T* key) const {
  76.         return find(key) != end();
  77.     }
  78.     T* remove(T* key) {
  79.         auto it = find(key);
  80.         if (it == end()) return nullptr;
  81.         T* val = *it;
  82.         base::erase(it);
  83.         return val;
  84.     }
  85.     T* add(T* val) {
  86.         base::push_back(val);
  87.         return val;
  88.     }
  89.     void release() {
  90.         for (T* it : *this) delete it;
  91.         base::clear();
  92.     }
  93. };
  94. //###################################################### vset: comparator
  95. namespace detail { namespace vset {
  96. /// Get Key Functor for Vector-Set
  97. template <class T, class K>
  98.   struct get_key {
  99.     K operator() (T* it) const {
  100.         return (K)(*it);
  101.     }
  102. };
  103. template <class T>
  104.   struct get_key<T,T*> {
  105.     T* operator() (T* it) const {
  106.         return it;
  107.     }
  108. };
  109. /// Comparator Functor for Vector-Set
  110. template <class T, class K=T,
  111.   class Less = std::less<K>, class GetKey = get_key<T,K>>
  112.   class comparator: protected GetKey, protected Less {
  113. public:
  114.     const GetKey& get_key() const {
  115.         return static_cast<const GetKey&>(*this);
  116.     }
  117.     const Less& less() const {
  118.         return static_cast<const Less&>(*this);
  119.     }
  120.     K operator() (T* it) const {
  121.         return get_key()(it);
  122.     }
  123.     bool operator() (K x, K y) const {
  124.         return less()(x, y);
  125.     }
  126.     bool operator() (T* x, K y) const {
  127.         return less()(get_key()(x), y);
  128.     }
  129.     bool operator() (K x, T* y) const {
  130.         return less()(x, get_key()(y));
  131.     }
  132.     bool operator() (T* x, T* y) const {
  133.         return less()(get_key()(x), get_key()(y));
  134.     }
  135. };
  136. template <class T, class Less, class GetKey>
  137.   class comparator<T,T*,Less,GetKey>:
  138.   protected GetKey, protected Less {
  139. public:
  140.     const GetKey& get_key() const {
  141.         return static_cast<const GetKey&>(*this);
  142.     }
  143.     const Less& less() const {
  144.         return static_cast<const Less&>(*this);
  145.     }
  146.     T* operator() (T* it) const {
  147.         return get_key()(it);
  148.     }
  149.     bool operator() (T* x, T* y) const {
  150.         return less()(x, y);
  151.     }
  152. };
  153. //============================================================ vset: base
  154. /// Vector-Set Basic Implementation
  155. template <class T, class K=T,
  156.   class Less = std::less<K>,
  157.   class GetKey = get_key<T,K>>
  158.   class base: protected comparator<T,K,Less,GetKey>, protected ptrvect<T> {
  159.     typedef ptrvect<T> core;
  160. protected:
  161. //    disable polymorphic destruction by hiding non-virtual destructor
  162.     ~base() {
  163.         return;
  164.     }
  165.     const comparator<T,K,Less,GetKey>& comp() const {
  166.         return static_cast<const comparator<T,K,Less,GetKey>&>(*this);
  167.     }
  168. public:
  169. //    pointers cannot be changed -> iterator = const_iterator
  170.     typedef typename core::const_iterator iterator, const_iterator;
  171.     typedef typename core::template condpair<iterator> condpair;
  172.     typedef T *value_type;
  173.     typedef K key_type;
  174.     using core::size_type;
  175.     using core::size;
  176.     using core::empty;
  177.     iterator begin() const {
  178.         return core::begin();
  179.     }
  180.     iterator end() const {
  181.         return core::end();
  182.     }
  183. public:
  184.     iterator lower_bound(K key) const {
  185.         return std::lower_bound(begin(), end(), key, comp());
  186.     }
  187.     iterator upper_bound(K key) const {
  188.         return std::upper_bound(begin(), end(), key, comp());
  189.     }
  190.     std::pair<iterator, iterator> equal_range(K key) const {
  191.         return std::equal_range(begin(), end(), key, comp());
  192.     }
  193.     iterator find(K key) const {
  194.         iterator it = lower_bound(key);
  195.         return it == end() || comp()(key, *it) ? end() : it;
  196.     }
  197.     bool contains(K key) const {
  198.         iterator it = lower_bound(key);
  199.         return it != end() && !comp()(key, *it);
  200.     }
  201. public:
  202.     template<class... Args>
  203.       condpair emplace(K key, Args&& ...args) {
  204.           iterator it = lower_bound(key);
  205.         if (it == end() || comp()(key, *it)) {
  206.             return condpair(core::insert(it,
  207.               new T(key, std::forward<Args>(args)...)), true);
  208.         }
  209.         return condpair(it, false);
  210.     }
  211.     iterator erase(iterator at) {
  212.         return core::erase(at);
  213.     }
  214. public:
  215.     T* add(T* value) {
  216.         K key = comp()(value);
  217.         iterator it = lower_bound(key);
  218.         if (it == end() || comp()(key, *it)) {
  219.             core::insert(it, value);
  220.             return value;
  221.         }
  222.         return nullptr;
  223.     }
  224.     template<class... Args>
  225.       T* add(K key, Args&& ...args) {
  226.           iterator it = lower_bound(key);
  227.         if (it == end() || comp()(key, *it)) {
  228.             T* value = new T(key, std::forward<Args>(args)...);
  229.             core::insert(it, value);
  230.             return value;
  231.         }
  232.         return nullptr;
  233.     }
  234.     T* get(K key) const {
  235.         iterator it = find(key);
  236.         return it == end() ? nullptr : *it;
  237.     }
  238.     T* operator[](K key) const {
  239.         return *emplace(key).first;
  240.     }
  241.     T* remove(K key) {
  242.         iterator it = find(key);
  243.         if (it == end()) return nullptr;
  244.         T* value = *it;
  245.         core::erase(it);
  246.         return value;
  247.     }
  248.     void release() {
  249.         for (T* it : *this) {
  250.             delete it;
  251.         }
  252.         core::clear();
  253.     }
  254.     void clear() {
  255.         core::clear();
  256.     }
  257. };
  258. }}
  259. //================================================================== vset
  260. template <class T, class K=T,
  261.   class Less = std::less<K>,
  262.   class GetKey = detail::vset::get_key<T,K>>
  263.   class vset: public detail::vset::base<T,K,Less,GetKey> {
  264.     typedef detail::vset::base<T,K,Less,GetKey> base;
  265. protected:
  266.     using base::comp;
  267. public:
  268.     typedef typename base::iterator iterator;
  269.     using base::begin; using base::end; using base::remove; using base::find;
  270.     using base::lower_bound; using base::upper_bound; using base::equal_range;
  271.     T* remove(T* value) {
  272.         return remove(comp()(value));
  273.     }
  274.     iterator find(T* value) const {
  275.         K key = comp()(value);
  276.         iterator it = lower_bound(key);
  277.         return it == end() || comp()(key, *it) ? end() : it;
  278.     }
  279.     iterator lower_bound(T* value) const {
  280.         return std::lower_bound(begin(), end(), value, comp());
  281.     }
  282.     iterator upper_bound(T* value) const {
  283.         return std::upper_bound(begin(), end(), value, comp());
  284.     }
  285.     std::pair<iterator, iterator> equal_range(T* value) const {
  286.         return std::equal_range(begin(), end(), value, comp());
  287.     }
  288. };
  289. //============================================================ vset: K=T*
  290. template <class T, class Less, class GetKey>
  291.   class vset<T,T*,Less,GetKey>:
  292.   public detail::vset::base<T,T*,Less,GetKey> {};
  293. //############################################################### testing
  294. #include <iostream>
  295. #include <cstring>
  296. using std::cout; using std::endl; using std::string;
  297. class User {
  298.     string name_;
  299. public:
  300.     User(string name): name_(std::move(name)) {
  301.         return;
  302.     }
  303.     const char * name() const {
  304.         return name_.c_str();
  305.     }
  306.     struct get_key {
  307.         const char * operator() (User* u) const {
  308.             return u->name();
  309.         }
  310.     };
  311. };
  312. struct str_less {
  313.     bool operator() (const char *lhs, const char *rhs) const {
  314.         return std::strcmp(lhs, rhs) < 0;
  315.     }
  316. };
  317. int main() {
  318.     vset<User,const char*,str_less,User::get_key> users;
  319.     users.add("firda");
  320.     for (auto p : users) cout << p->name() << endl;
  321.     auto it = users.find("firda");
  322.     cout << it->name() << endl;
  323.     it = users.find(*it);
  324.     cout << it->name() << endl;
  325.  
  326.     vset<int,int*> ints;
  327.     int* i = ints.add(new int(1));
  328.     auto j = ints.find(i);
  329.     cout << **j << endl;
  330. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top