fork download 
  1. #ifndef _STL_VECTOR_HPP_
  2. #define _STL_VECTOR_HPP_
  3.  
  4. #include <stl/algorithm.hpp>
  5. #include <stl/allocator.hpp>
  6. #include <stl/iterator.hpp>
  7. #include <stl/memory.hpp>
  8.  
  9. namespace stl
  10. {
  11.     /*
  12. 	 * class base_vector
  13. 	 * Base class for the vector container. All memory allocation and
  14. 	 * deallocation is performed in this class.
  15. 	 * */
  16. 	template <
  17. 		class ValueTy,
  18. 		class AllocatorTy>
  19. 	class base_vector : public traits<ValueTy, ValueTy*>
  20. 	{
  21. 	private:
  22. 		typedef base_vector<ValueTy,AllocatorTy> this_type;
  23. 		const size_type __mMaxSize;
  24. 	public:
  25. 		typedef AllocatorTy allocator_type;
  26. 	protected:
  27. 		allocator_type _mAllocator;
  28. 		pointer_type   _mBegin;
  29. 		pointer_type   _mEnd;
  30. 		pointer_type   _mCapacity;
  31.  
  32. 		void _do_assign(const size_type, const_reference_type);
  33. 		pointer_type _do_create_copy();
  34.         void _do_destroy_values(pointer_type, pointer_type);
  35. 		void _do_reallocate(const size_type);
  36. 		void _do_remove(const size_type, const size_type);
  37. 		void _do_resize(const size_type);
  38. 	public:
  39. 		base_vector();
  40. 		~base_vector();
  41.  
  42. 		bool empty() const;
  43. 		size_type capacity() const;
  44. 		size_type size() const;
  45. 		size_type max_size() const;
  46.  
  47.         allocator_type get_allocator() const;
  48. 	};
  49.  
  50. 	/*
  51. 	 * Constructor
  52. 	 * Input:
  53. 	     * nothing
  54. 	 * */
  55. 	template <class ValueTy, class AllocatorTy>
  56. 	base_vector<ValueTy, AllocatorTy>::base_vector()
  57. 		: __mMaxSize(stl::npos / this_type::base_size),
  58. 		  _mBegin(NULL),
  59. 		  _mEnd(NULL),
  60. 		  _mCapacity(NULL)
  61. 	{}
  62.  
  63.     /*
  64. 	 * Destructor
  65. 	 * */
  66. 	template <class ValueTy, class AllocatorTy>
  67. 	base_vector<ValueTy, AllocatorTy>::~base_vector()
  68. 	{
  69. 		const size_type currentSize = this->size();
  70. 		for (size_type i = 0; i < currentSize; ++i) {
  71. 			_mAllocator.destroy(_mBegin+i);
  72. 		}
  73. 		_mAllocator.deallocate(_mBegin);
  74. 	}
  75.  
  76. 	/*
  77. 	 * _do_assign() returns nothing
  78. 	 * Input:
  79. 	     * size_type             The index of the element to assign to.
  80. 	     * const_reference_type  The value to assign.
  81. 	 * */
  82. 	template <class ValueTy, class AllocatorTy>
  83. 	void
  84. 	base_vector<ValueTy, AllocatorTy>::_do_assign(const size_type index, const_reference_type val)
  85. 	{
  86. 		if (index >= this->size()) {
  87. 			this->_do_resize(index+1);
  88. 		}
  89. 		_mBegin[index] = val;
  90. 	}
  91.  
  92. 	/*
  93. 	 * _do_create_copy() returns pointer_type
  94. 	 * Input:
  95. 	     * nothing
  96. 	 *
  97. 	 * Creates a full copy of the data allocated by the vector.
  98. 	 * Returns a pointer to said copy. Will return NULL if vector is empty.
  99. 	 * */
  100. 	template <class ValueTy, class AllocatorTy>
  101. 	typename base_vector<ValueTy, AllocatorTy>::pointer_type
  102. 	base_vector<ValueTy, AllocatorTy>::_do_create_copy()
  103. 	{
  104. 		const size_type len = this->size();
  105. 		pointer_type result = NULL;
  106.  
  107. 		if (len > 0)
  108. 		{
  109. 			result = _mAllocator.allocate(len);
  110. 			memcpy(result, _mBegin, len * this_type::base_size);
  111. 		}
  112.  
  113. 		return result;
  114. 	}
  115.  
  116.     template <class ValueTy, class AllocatorTy>
  117. 	typename base_vector<ValueTy, AllocatorTy>::pointer_type
  118. 	base_vector<ValueTy, AllocatorTy>::_do_destroy_values(pointer_type first, pointer_type last)
  119. 	{
  120.         for (; first != last; ++first) {
  121.             first->~value_type();
  122.         }
  123.     }
  124.  
  125. 	template <class ValueTy, class AllocatorTy>
  126. 	void
  127. 	base_vector<ValueTy, AllocatorTy>::_do_reallocate(const size_type newDesiredCapacity)
  128. 	{
  129. 		if (newDesiredCapacity > this->capacity())
  130. 		{
  131. 			size_type newCapacity = 1;
  132. 			while (newCapacity < newDesiredCapacity) {
  133. 				newCapacity *= 2;
  134. 			}
  135. 			const size_type previousSize = this->size();
  136. 			pointer_type backup = _do_create_copy();
  137.  
  138. 			_mAllocator.deallocate(_mBegin);
  139. 			_mBegin = _mAllocator.allocate(newCapacity);
  140. 			_mEnd = _mBegin + previousSize;
  141. 			_mCapacity = _mBegin + newCapacity;
  142.  
  143. 			if (backup != NULL)
  144. 			{
  145. 				memcpy(_mBegin, backup, previousSize * this_type::base_size);
  146. 				_mAllocator.deallocate(backup);
  147. 			}
  148. 		}
  149. 	}
  150.  
  151. 	template <class ValueTy, class AllocatorTy>
  152. 	void
  153. 	base_vector<ValueTy, AllocatorTy>::_do_remove(const size_type start, const size_type len)
  154. 	{
  155. 		if (start != stl::npos)
  156. 		{
  157. 			pointer_type ptr = (_mBegin + start);
  158. 			pointer_type ptrEnd = (ptr + len);
  159.  
  160. 			if (ptrEnd <= _mEnd)
  161. 			{
  162. 				while (ptr != ptrEnd) {
  163. 					_mAllocator.destroy(ptr++);
  164. 				}
  165. 				_mEnd -= len;
  166.  
  167. 				if (ptrEnd != _mEnd) {
  168. 					memmove((_mBegin+start), ptrEnd, len * this_type::base_size);
  169. 				}
  170. 			}
  171. 		}
  172. 	}
  173.  
  174. 	template <class ValueTy, class AllocatorTy>
  175. 	inline void
  176. 	base_vector<ValueTy, AllocatorTy>::_do_resize(const size_type newSize)
  177. 	{
  178. 		this->_do_reallocate(newSize);
  179. 		_mEnd = (_mBegin + newSize);
  180. 	}
  181.  
  182. 	/*
  183. 	 * empty() returns bool
  184. 	 * Input:
  185. 	     * nothing
  186. 	 * */
  187. 	template <class ValueTy, class AllocatorTy>
  188. 	inline bool
  189. 	base_vector<ValueTy, AllocatorTy>::empty() const
  190. 	{
  191. 		return (_mBegin == _mEnd);
  192. 	}
  193.  
  194. 	/*
  195. 	 * capacity() returns size_type
  196. 	 * Input:
  197. 	     * nothing
  198. 	 * */
  199. 	template <class ValueTy, class AllocatorTy>
  200. 	inline typename base_vector<ValueTy, AllocatorTy>::size_type
  201. 	base_vector<ValueTy, AllocatorTy>::capacity() const
  202. 	{
  203. 		return (_mCapacity - _mBegin);
  204. 	}
  205.  
  206. 	/*
  207. 	 * size() returns size_type
  208. 	 * Input:
  209. 	     * nothing
  210. 	 * */
  211. 	template <class ValueTy, class AllocatorTy>
  212. 	inline typename base_vector<ValueTy, AllocatorTy>::size_type
  213. 	base_vector<ValueTy, AllocatorTy>::size() const
  214. 	{
  215. 		return (_mEnd - _mBegin);
  216. 	}
  217.  
  218. 	/*
  219. 	 * max_size() returns size_type
  220. 	 * Input:
  221. 	     * nothing
  222. 	 * */
  223. 	template <class ValueTy, class AllocatorTy>
  224. 	inline typename base_vector<ValueTy, AllocatorTy>::size_type
  225. 	base_vector<ValueTy, AllocatorTy>::max_size() const
  226. 	{
  227. 		return __mMaxSize;
  228. 	}
  229.  
  230. 	/*
  231. 	 * class vector
  232. 	 * 
  233. 	 * */
  234. 	template <
  235. 		class ValueTy,
  236. 		class AllocatorTy=allocator<ValueTy>>
  237. 	class vector : public base_vector<ValueTy, AllocatorTy>
  238. 	{
  239. 	private:
  240. 		typedef vector<ValueTy,AllocatorTy>           this_type;
  241. 		typedef base_vector<ValueTy,AllocatorTy>      base_type;
  242. 	public:
  243. 		typedef pointer_type                          iterator;
  244. 		typedef const_pointer_type                    const_iterator;
  245. 		typedef stl::reverse_iterator<iterator>       reverse_iterator;
  246. 		typedef stl::reverse_iterator<const_iterator> const_reverse_iterator;
  247.  
  248. 		vector();
  249. 		vector(const size_type);
  250. 		vector(const size_type, const_reference_type);
  251.  
  252. 		reference_type          operator [] (const size_type);
  253. 		const_reference_type    operator [] (const size_type) const;
  254.  
  255. 		reference_type          at(const size_type);
  256. 		const_reference_type    at(const size_type) const;
  257.  
  258.         reference_type          front();
  259.         reference_type          back();
  260.         const_reference_type    front() const;
  261.         const_reference_type    back() const;
  262.  
  263. 		iterator                begin();
  264. 		iterator                end();
  265. 		const_iterator          begin() const;
  266. 		const_iterator          end() const;
  267.  
  268. 		reverse_iterator        rbegin();
  269. 		reverse_iterator        rend();
  270. 		const_reverse_iterator  rbegin() const;
  271. 		const_reverse_iterator  rend() const;
  272.  
  273. 		void                    push_back(const_reference_type);
  274. 		void                    pop_back();
  275.  
  276. 		void                    reserve(const size_type);
  277. 		void                    resize(const size_type);
  278. 		void                    resize(const size_type, const_reference_type);
  279.  
  280.         void                    assign(iterator, iterator);
  281.         void                    assign(size_type, const_reference_type);
  282. 		iterator                erase(iterator);
  283. 		iterator                erase(iterator, iterator);
  284. 		iterator                insert(iterator, const_reference_type);
  285. 		void                    insert(iterator, size_type, const_reference_type);
  286. 		template <class InputIteratorTy>
  287. 		void                    insert(iterator, InputIteratorTy, InputIteratorTy);
  288.  
  289. 		void                    clear();
  290. 		void                    swap(this_type&);
  291. 	};
  292.  
  293. 	/*
  294. 	 * operator [] returns reference_type
  295. 	 * Input:
  296. 	     * size_type  The index position of the element to return.
  297. 	 * */
  298. 	template <class Ty, class AllocatorTy>
  299. 	inline typename vector<Ty, AllocatorTy>::reference_type
  300. 	vector<Ty, AllocatorTy>::operator [] (const size_type index)
  301. 	{
  302. 		return _mBegin[index];
  303. 	}
  304.  
  305. 	/*
  306. 	 * operator [] returns const_reference_type
  307. 	 * Input:
  308. 	     * size_type  The index position of the element to return.
  309. 	 * */
  310. 	template <class Ty, class AllocatorTy>
  311. 	inline typename vector<Ty, AllocatorTy>::const_reference_type
  312. 	vector<Ty, AllocatorTy>::operator [] (const size_type index) const
  313. 	{
  314. 		return _mBegin[index];
  315. 	}
  316.  
  317. 	/*
  318. 	 * Constructor
  319. 	 * */
  320. 	template <class ValueTy, class AllocatorTy>
  321. 	vector<ValueTy, AllocatorTy>::vector()
  322. 	{
  323. 		/* Intentionally left blank. */
  324. 	}
  325.  
  326. 	/*
  327. 	 * Constructor
  328. 	 * */
  329. 	template <class ValueTy, class AllocatorTy>
  330. 	vector<ValueTy, AllocatorTy>::vector(const size_type num)
  331. 	{
  332. 		this->resize(num, value_type());
  333. 	}
  334.  
  335. 	/*
  336. 	 * Constructor
  337. 	 * */
  338. 	template <class ValueTy, class AllocatorTy>
  339. 	vector<ValueTy, AllocatorTy>::vector(const size_type num, const_reference_type val)
  340. 	{
  341. 		this->resize(num, val);
  342. 	}
  343.  
  344. 	/*
  345. 	 * at() returns reference_type
  346. 	 * Input:
  347. 	     * size_type  The index of the element to return.
  348. 	 * */
  349. 	template <class ValueTy, class AllocatorTy>
  350. 	inline typename vector<ValueTy, AllocatorTy>::reference_type
  351. 	vector<ValueTy, AllocatorTy>::at(const size_type index)
  352. 	{
  353. 		return _mBegin[index];
  354. 	}
  355.  
  356. 	/*
  357. 	 * at() const returns const_reference_type
  358. 	 * Input:
  359. 	     * size_type  The index of the element to return.
  360. 	 * */
  361. 	template <class ValueTy, class AllocatorTy>
  362. 	inline typename vector<ValueTy, AllocatorTy>::const_reference_type
  363. 	vector<ValueTy, AllocatorTy>::at(const size_type index) const
  364. 	{
  365. 		return _mBegin[index];
  366. 	}
  367.  
  368.     /*
  369. 	 * front() returns reference_type
  370. 	 * Input:
  371. 	     * nothing
  372. 	 * */
  373. 	template <class ValueTy, class AllocatorTy>
  374. 	inline typename vector<ValueTy, AllocatorTy>::reference_type
  375. 	vector<ValueTy, AllocatorTy>::front()
  376. 	{
  377. 		return *_mBegin;
  378. 	}
  379.  
  380.     /*
  381. 	 * back() returns reference_type
  382. 	 * Input:
  383. 	     * nothing
  384. 	 * */
  385. 	template <class ValueTy, class AllocatorTy>
  386. 	inline typename vector<ValueTy, AllocatorTy>::reference_type
  387. 	vector<ValueTy, AllocatorTy>::back()
  388. 	{
  389. 		return *_mEnd;
  390. 	}
  391.  
  392.     /*
  393. 	 * front() const returns const_reference_type
  394. 	 * Input:
  395. 	     * nothing
  396. 	 * */
  397. 	template <class ValueTy, class AllocatorTy>
  398. 	inline typename vector<ValueTy, AllocatorTy>::const_reference_type
  399. 	vector<ValueTy, AllocatorTy>::front() const
  400. 	{
  401. 		return *_mBegin;
  402. 	}
  403.  
  404.     /*
  405. 	 * back() const returns const_reference_type
  406. 	 * Input:
  407. 	     * nothing
  408. 	 * */
  409. 	template <class ValueTy, class AllocatorTy>
  410. 	inline typename vector<ValueTy, AllocatorTy>::const_reference_type
  411. 	vector<ValueTy, AllocatorTy>::back() const
  412. 	{
  413. 		return *_mEnd;
  414. 	}
  415.  
  416. 	/*
  417. 	 * begin() returns iterator
  418. 	 * Input:
  419. 	     * nothing
  420. 	 * */
  421. 	template <class ValueTy, class AllocatorTy>
  422. 	inline typename vector<ValueTy, AllocatorTy>::iterator
  423. 	vector<ValueTy, AllocatorTy>::begin()
  424. 	{
  425. 		return iterator(_mBegin);
  426. 	}
  427.  
  428. 	/*
  429. 	 * end() returns iterator
  430. 	 * Input:
  431. 	     * nothing
  432. 	 * */
  433. 	template <class ValueTy, class AllocatorTy>
  434. 	inline typename vector<ValueTy, AllocatorTy>::iterator
  435. 	vector<ValueTy, AllocatorTy>::end()
  436. 	{
  437. 		return iterator(_mEnd);
  438. 	}
  439.  
  440. 	/*
  441. 	 * begin() const returns iterator
  442. 	 * Input:
  443. 	     * nothing
  444. 	 * */
  445. 	template <class ValueTy, class AllocatorTy>
  446. 	inline typename vector<ValueTy, AllocatorTy>::const_iterator
  447. 	vector<ValueTy, AllocatorTy>::begin() const
  448. 	{
  449. 		return const_iterator(_mBegin);
  450. 	}
  451.  
  452. 	/*
  453. 	 * end() const returns iterator
  454. 	 * Input:
  455. 	     * nothing
  456. 	 * */
  457. 	template <class ValueTy, class AllocatorTy>
  458. 	inline typename vector<ValueTy, AllocatorTy>::const_iterator
  459. 	vector<ValueTy, AllocatorTy>::end() const
  460. 	{
  461. 		return const_iterator(_mEnd);
  462. 	}
  463.  
  464.     template <class ValueTy, class AllocatorTy>
  465. 	inline typename vector<ValueTy, AllocatorTy>::reverse_iterator
  466. 	vector<ValueTy, AllocatorTy>::rbegin()
  467. 	{
  468. 		return reverse_iterator(_mEnd);
  469. 	}
  470.  
  471.     template <class ValueTy, class AllocatorTy>
  472. 	inline typename vector<ValueTy, AllocatorTy>::reverse_iterator
  473. 	vector<ValueTy, AllocatorTy>::rend()
  474. 	{
  475. 		return reverse_iterator(_mBegin);
  476. 	}
  477.  
  478.     template <class ValueTy, class AllocatorTy>
  479. 	inline typename vector<ValueTy, AllocatorTy>::const_reverse_iterator
  480. 	vector<ValueTy, AllocatorTy>::rbegin() const
  481. 	{
  482. 		return const_reverse_iterator(_mEnd);
  483. 	}
  484.  
  485.     template <class ValueTy, class AllocatorTy>
  486. 	inline typename vector<ValueTy, AllocatorTy>::const_reverse_iterator
  487. 	vector<ValueTy, AllocatorTy>::rend() const
  488. 	{
  489. 		return const_reverse_iterator(_mBegin);
  490. 	}
  491.  
  492. 	/*
  493. 	 * push_back() returns nothing
  494. 	 * Input:
  495. 	     * const_reference_type  The value to push.
  496. 	 *
  497. 	 * Pushes the passed value onto the end of the vector.
  498. 	 * */
  499. 	template <class ValueTy, class AllocatorTy>
  500. 	inline void
  501. 	vector<ValueTy, AllocatorTy>::push_back(const_reference_type val)
  502. 	{
  503. 		this->_do_assign(this->size(), val);
  504. 	}
  505.  
  506. 	/*
  507. 	 * pop_back() returns nothing
  508. 	 * Input:
  509. 	     * nothing
  510. 	 * */
  511. 	template <class ValueTy, class AllocatorTy>
  512. 	inline void
  513. 	vector<ValueTy, AllocatorTy>::pop_back()
  514. 	{
  515. 		this->_do_remove(this->size()-1, 1);
  516. 	}
  517.  
  518. 	/*
  519. 	 * reserve() returns nothing
  520. 	 * Input:
  521. 	     * size_type  The new capacity.
  522. 	 *
  523. 	 * This function is a public alias for basic_vector::_do_reallocate.
  524. 	 * */
  525. 	template <class ValueTy, class AllocatorTy>
  526. 	inline void
  527. 	vector<ValueTy, AllocatorTy>::reserve(const size_type newCapacity)
  528. 	{
  529. 		this->_do_reallocate(newCapacity);
  530. 	}
  531.  
  532. 	/*
  533. 	 * resize() returns nothing
  534. 	 * Input:
  535. 	     * size_type  The new size.
  536. 	 * */
  537. 	template <class ValueTy, class AllocatorTy>
  538. 	inline void
  539. 	vector<ValueTy, AllocatorTy>::resize(const size_type newSize)
  540. 	{
  541.         if (newSize > this->size()) {
  542. 		    this->_do_resize(newSize);
  543.         } else {
  544.             this->erase(_mBegin + newSize, _mEnd);
  545.         }
  546. 	}
  547.  
  548. 	/*
  549. 	 * resize() returns nothing
  550. 	 * Input:
  551. 	     * size_type             The new size.
  552. 	     * const_reference_type  The value to assign the each element.
  553. 	 * */
  554. 	template <class ValueTy, class AllocatorTy>
  555. 	void
  556. 	vector<ValueTy, AllocatorTy>::resize(const size_type newSize, const_reference_type val)
  557. 	{
  558. 		this->_do_resize(newSize);
  559. 		for (iterator itr = begin(); itr != end(); ++itr) {
  560. 			*itr = val;
  561. 		}
  562. 	}
  563.  
  564.     /*
  565. 	 * assign() returns nothing
  566. 	 * Input:
  567. 	     * size_type             The number of elements to assign.
  568. 	     * const_reference_type  The value to assign the each element.
  569. 	 * */
  570.     template <class ValueTy, class AllocatorTy>
  571.     void
  572.     vector<ValueTy, AllocatorTy>::assign(size_type n, const_reference_type source)
  573.     {
  574.         if (n > this->size()) {
  575.             this->resize(n, source);
  576.         } else {
  577.             while (n-- > 0) {
  578.                 _mBegin[n] = source;
  579.             }
  580.         }
  581.     }
  582.  
  583.     /*
  584. 	 * erase() returns iterator
  585. 	 * Input:
  586. 	     * iterator  The position of the element to be removed.
  587. 	 *
  588. 	 * Removes the element at the position defined by the passed iterator.
  589. 	 * The returned iterator will be equal to the element one past the
  590. 	 * element defined by the passed iterator.
  591. 	 * For example:
  592. 	     * vector<int> vec(3);
  593. 	     * vec[0]=1; vec[1]=2; vec[2]=3;
  594.          * 
  595.          * int n = *(vec.erase(vec.begin()+1)); // 3
  596. 	 * */
  597.     template <class ValueTy, class AllocatorTy>
  598.     typename vector<ValueTy, AllocatorTy>::iterator
  599.     vector<ValueTy, AllocatorTy>::erase(iterator itr)
  600.     {
  601.         iterator result = this->end();
  602.  
  603.         if (this->empty() == false)
  604.         {
  605.             if (this->size() > 1)
  606.             {
  607.                 result = &*itr;
  608.                 memmove(&*itr, &*itr+1, (this->size()-(&*itr-_mBegin)) * sizeof value_type);
  609.             }
  610.  
  611.             --_mEnd;
  612.         }
  613.  
  614.         return result;
  615.     }
  616.  
  617.     template <class ValueTy, class AllocatorTy>
  618.     typename vector<ValueTy, AllocatorTy>::iterator
  619.     vector<ValueTy, AllocatorTy>::erase(iterator first, iterator last)
  620.     {
  621.         iterator result = this->end();
  622.  
  623.         if (this->empty() == false)
  624.         {
  625.             const difference_type len = (&*last - &*first);
  626.  
  627.             if (len == 0)
  628.             {
  629.                 result = this->erase(first);
  630.                 --_mEnd;
  631.             }
  632.             else
  633.             {
  634.                 result = &*last;
  635.                 _mEnd -= len;
  636.                 memmove(&*first, &*last+1, (this->size()-len) * sizeof value_type);
  637.             }
  638.         }
  639.  
  640.         return result;
  641.     }
  642.  
  643. 	/*
  644. 	 * clear() returns nothing
  645. 	 * Input:
  646. 	     * nothing
  647. 	 * */
  648. 	template <class ValueTy, class AllocatorTy>
  649. 	inline void
  650. 	vector<ValueTy, AllocatorTy>::clear()
  651. 	{
  652.         _do_destroy_values(_mBegin, _mEnd);
  653. 		_mEnd = _mBegin;
  654. 	}
  655.  
  656. 	/*
  657. 	 * swap() returns nothing
  658. 	 * Input:
  659. 	     * this_type&  A reference to the vector to swap with.
  660. 	 * */
  661. 	template <class ValueTy, class AllocatorTy>
  662. 	inline void
  663. 	vector<ValueTy, AllocatorTy>::swap(this_type& source)
  664. 	{
  665. 		memswap(this, &source, sizeof this_type);
  666. 	}
  667. }
  668.  
  669. #endif
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/H7ebNc
language:
C++ (gcc 8.3)
created:
13 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!