fork download
copy 
  1. #include <vector>
  2. #include <algorithm>
  3. //############################################################### ptrvect
  4. /// Vector of Pointers
  5. #line 4 "vecset.cpp.fi"
  6. template <class T, class base = std::vector<T*> >
  7.   class ptrvect: public base {
  8. public:
  9. 	class iterator: public base::iterator {
  10. 		friend class ptrvect;
  11. 		iterator(const typename base::const_iterator& it):
  12. 		  base::iterator(const_cast<T**>(&*it)) {
  13. 			return; }
  14. 	public:
  15. 		iterator(const typename base::iterator& it):
  16. 		  base::iterator(it) {
  17. 			return; }
  18. 		T* operator->() const {
  19. 			return **this; }};
  20. 	class const_iterator: public base::const_iterator {
  21. 	public:
  22. 		const_iterator(const typename base::const_iterator& it):
  23. 		  base::const_iterator(it) {
  24. 			return; }
  25. 		const_iterator(const typename base::iterator& it):
  26. 		  base::const_iterator(it) {
  27. 			return; }
  28. 		T* operator->() const {
  29. 			return **this; }};
  30. 	template <class It = iterator>
  31. 	  class condpair: public std::pair<It,bool> {
  32. 	public:
  33. 		condpair(It it, bool second):
  34. 		  std::pair<It,bool>(it, second) {
  35. 			return; }
  36. 		T* operator->() const {
  37. 			return *std::pair<It,bool>::first; }};
  38. public:
  39. 	iterator begin() {
  40. 		return iterator(base::begin()); }
  41. 	iterator end() {
  42. 		return iterator(base::end()); }
  43. 	const_iterator begin() const {
  44. 		return const_iterator(base::begin()); }
  45. 	const_iterator end() const {
  46. 		return const_iterator(base::end()); }
  47. public: // workarounds for pre-C++11 / bad C++11 implementation (should allow const_iterator)
  48. 	iterator insert(const_iterator pos, T* value) {
  49. 		return base::insert(iterator(pos), value); }
  50. 	iterator erase(const_iterator pos) {
  51. 		return base::erase(iterator(pos)); }
  52. public: // addons
  53. 	iterator find (T* key) {
  54. 		return std::find(begin(), end(), key); }
  55. 	const_iterator find (T* key) const {
  56. 		return std::find(begin(), end(), key); }
  57. 	bool contains (T* key) const {
  58. 		return find(key) != end(); }
  59. 	T* remove(T* key) {
  60. 		auto it = find(key);
  61. 		if (it == end()) return nullptr;
  62. 		T* val = *it;
  63. 		base::erase(it);
  64. 		return val; }
  65. 	T* add(T* val) {
  66. 		base::push_back(val);
  67. 		return val; }
  68. 	void release() {
  69. 		for (T* it : *this) delete it;
  70. 		base::clear(); }};
  71. //###################################################### vset: comparator
  72. namespace detail { namespace vset {
  73. /// Get Key Functor for Vector-Set
  74. template <class T, class K>
  75.   struct get_key {
  76. 	K operator() (T* it) const {
  77. 		return (K)(*it); }};
  78. template <class T>
  79.   struct get_key<T,T*> {
  80. 	T* operator() (T* it) const {
  81. 		return it; }};
  82. /// Comparator Functor for Vector-Set
  83. template <class T, class K=T,
  84.   class Less = std::less<K>, class GetKey = get_key<T,K>>
  85.   class comparator: protected GetKey, protected Less {
  86. public:
  87. 	const GetKey& get_key() const {
  88. 		return static_cast<const GetKey&>(*this); }
  89. 	const Less& less() const {
  90. 		return static_cast<const Less&>(*this); }
  91. 	K operator() (T* it) const {
  92. 		return get_key()(it); }
  93. 	bool operator() (K x, K y) const {
  94. 		return less()(x, y); }
  95. 	bool operator() (T* x, K y) const {
  96. 		return less()(get_key()(x), y); }
  97. 	bool operator() (K x, T* y) const {
  98. 		return less()(x, get_key()(y)); }
  99. 	bool operator() (T* x, T* y) const {
  100. 		return less()(get_key()(x), get_key()(y)); }};
  101. template <class T, class Less, class GetKey>
  102.   class comparator<T,T*,Less,GetKey>:
  103.   protected GetKey, protected Less {
  104. public:
  105. 	const GetKey& get_key() const {
  106. 		return static_cast<const GetKey&>(*this); }
  107. 	const Less& less() const {
  108. 		return static_cast<const Less&>(*this); }
  109. 	T* operator() (T* it) const {
  110. 		return get_key()(it); }
  111. 	bool operator() (T* x, T* y) const {
  112. 		return less()(x, y); }};
  113. //============================================================ vset: base
  114. /// Vector-Set Basic Implementation
  115. template <class T, class K=T,
  116.   class Less = std::less<K>,
  117.   class GetKey = get_key<T,K>>
  118.   class base: protected comparator<T,K,Less,GetKey>, protected ptrvect<T> {
  119. 	typedef ptrvect<T> core;
  120. protected:
  121. //	disable polymorphic destruction by hiding non-virtual destructor
  122. 	~base() {
  123. 		return; }
  124. 	const comparator<T,K,Less,GetKey>& comp() const {
  125. 		return static_cast<const comparator<T,K,Less,GetKey>&>(*this); }
  126. public:
  127. //	pointers cannot be changed -> iterator = const_iterator
  128. 	typedef typename core::const_iterator iterator, const_iterator;
  129. 	typedef typename core::template condpair<iterator> condpair;
  130. 	typedef T *value_type;
  131. 	typedef K key_type;
  132. 	using core::size_type;
  133. 	using core::size;
  134. 	using core::empty;
  135. 	iterator begin() const {
  136. 		return core::begin(); }
  137. 	iterator end() const {
  138. 		return core::end(); }
  139. public:
  140. 	iterator lower_bound(K key) const {
  141. 		return std::lower_bound(begin(), end(), key, comp()); }
  142. 	iterator upper_bound(K key) const {
  143. 		return std::upper_bound(begin(), end(), key, comp()); }
  144. 	std::pair<iterator, iterator> equal_range(K key) const {
  145. 		return std::equal_range(begin(), end(), key, comp()); }
  146. 	iterator find(K key) const {
  147. 		iterator it = lower_bound(key);
  148. 		return it == end() || comp()(key, *it) ? end() : it; }
  149. 	bool contains(K key) const {
  150. 		iterator it = lower_bound(key);
  151. 		return it != end() && !comp()(key, *it); }
  152. public:
  153. 	template<class... Args>
  154. 	  condpair emplace(K key, Args&& ...args) {
  155. 	  	iterator it = lower_bound(key);
  156. 		if (it == end() || comp()(key, *it)) {
  157. 			return condpair(core::insert(it,
  158. 			  new T(key, std::forward<Args>(args)...)), true); }
  159. 		return condpair(it, false); }
  160. 	iterator erase(iterator at) {
  161. 		return core::erase(at); }
  162. public:
  163. 	T* add(T* value) {
  164. 		K key = comp()(value);
  165. 		iterator it = lower_bound(key);
  166. 		if (it == end() || comp()(key, *it)) {
  167. 			core::insert(it, value);
  168. 			return value; }
  169. 		return nullptr; }
  170. 	template<class... Args>
  171. 	  T* add(K key, Args&& ...args) {
  172. 	  	iterator it = lower_bound(key);
  173. 		if (it == end() || comp()(key, *it)) {
  174. 			T* value = new T(key, std::forward<Args>(args)...);
  175. 			core::insert(it, value);
  176. 			return value; }
  177. 		return nullptr; }
  178. 	T* get(K key) const {
  179. 		iterator it = find(key);
  180. 		return it == end() ? nullptr : *it; }
  181. 	T* operator[](K key) const {
  182. 		return *emplace(key).first; }
  183. 	T* remove(K key) {
  184. 		iterator it = find(key);
  185. 		if (it == end()) return nullptr;
  186. 		T* value = *it;
  187. 		core::erase(it);
  188. 		return value; }
  189. 	void release() {
  190. 		for (T* it : *this) {
  191. 			delete it; }
  192. 		core::clear(); }
  193. 	void clear() {
  194. 		core::clear(); }};
  195. //================================================================== vset
  196. }}
  197. template <class T, class K=T,
  198.   class Less = std::less<K>,
  199.   class GetKey = detail::vset::get_key<T,K>>
  200.   class vset: public detail::vset::base<T,K,Less,GetKey> {
  201. 	typedef detail::vset::base<T,K,Less,GetKey> base;
  202. protected:
  203. 	using base::comp;
  204. public:
  205. 	typedef typename base::iterator iterator;
  206. 	using base::begin; using base::end; using base::remove; using base::find;
  207. 	using base::lower_bound; using base::upper_bound; using base::equal_range;
  208. 	T* remove(T* value) {
  209. 		return remove(comp()(value)); }
  210. 	iterator find(T* value) const {
  211. 		K key = comp()(value);
  212. 		iterator it = lower_bound(key);
  213. 		return it == end() || comp()(key, *it) ? end() : it; }
  214. 	iterator lower_bound(T* value) const {
  215. 		return std::lower_bound(begin(), end(), value, comp()); }
  216. 	iterator upper_bound(T* value) const {
  217. 		return std::upper_bound(begin(), end(), value, comp()); }
  218. 	std::pair<iterator, iterator> equal_range(T* value) const {
  219. 		return std::equal_range(begin(), end(), value, comp()); }};
  220. //============================================================ vset: K=T*
  221. template <class T, class Less, class GetKey>
  222.   class vset<T,T*,Less,GetKey>:
  223.   public detail::vset::base<T,T*,Less,GetKey> {};
  224. //############################################################### testing
  225. #include <iostream>
  226. #include <cstring>
  227. #line 224 "vecset.cpp.fi"
  228. using std::cout; using std::endl; using std::string;
  229. class User {
  230. 	string name_;
  231. public:
  232. 	User(string name): name_(std::move(name)) {
  233. 		return; }
  234. 	const char * name() const {
  235. 		return name_.c_str(); }
  236. 	struct get_key {
  237. 		const char * operator() (User* u) const {
  238. 			return u->name(); }};};
  239. struct str_less {
  240. 	bool operator() (const char *lhs, const char *rhs) const {
  241. 		return std::strcmp(lhs, rhs) < 0; }};
  242. int main() {
  243. 	vset<User,const char*,str_less,User::get_key> users;
  244. 	users.add("firda");
  245. 	for (auto p : users) cout << p->name() << endl;
  246. 	auto it = users.find("firda");
  247. 	cout << it->name() << endl;
  248. 	it = users.find(*it);
  249. 	cout << it->name() << endl;
  250.  
  251. 	vset<int,int*> ints;
  252. 	int* i = ints.add(new int(1));
  253. 	auto j = ints.find(i);
  254. 	cout << **j << endl; }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
firda
firda
firda
1
https://ideone.com/8zBJEe
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!