fork download
copy 
  1. // Playground for https://stackoverflow.com/a/56253629/11458991
  2.  
  3.  
  4. #include<initializer_list>
  5. #include<iostream>
  6. #include<vector>
  7.  
  8.  
  9. // Declarations:
  10.  
  11. // Stores a collection of numbers in the form radix*RADIX_MULTIPLIER + suffix,
  12. // where 0 <= suffix < RADIX_MULTIPLIER.
  13. class Block {
  14. public:
  15. 	using SUFFIX_VECTOR_T = std::vector<unsigned short>;
  16.  
  17. 	constexpr static unsigned int RADIX_MULTIPLIER = 100;
  18.  
  19. private:
  20. 	const unsigned short radix;
  21.  
  22. 	// Contains all the suffixes associated with this radix.
  23. 	SUFFIX_VECTOR_T suffixes;
  24.  
  25. public:
  26. 	Block(unsigned short radix);
  27. 	unsigned short getRadix() const;
  28. 	void pushSuffix(const unsigned short suffix);
  29. 	std::size_t size() const;
  30. 	unsigned int operator[](std::size_t idx) const;
  31. 	SUFFIX_VECTOR_T::const_iterator begin() const;
  32. 	SUFFIX_VECTOR_T::const_iterator cbegin() const;
  33. 	SUFFIX_VECTOR_T::const_iterator end() const;
  34. 	SUFFIX_VECTOR_T::const_iterator cend() const;
  35. };
  36.  
  37. using DATA_VECTOR_T = std::vector<Block>;
  38.  
  39. class MyIterator :
  40. 	public std::iterator<std::input_iterator_tag, unsigned int> {
  41. 	const DATA_VECTOR_T& data;
  42. 	DATA_VECTOR_T::const_iterator block_it;
  43.  
  44. 	Block::SUFFIX_VECTOR_T::const_iterator suffix_it;
  45.  
  46. public:
  47. 	MyIterator(
  48. 		const DATA_VECTOR_T& data,
  49. 		const DATA_VECTOR_T::const_iterator start_block_it);
  50. 	MyIterator& operator++();
  51. 	MyIterator operator++(int);
  52. 	bool operator==(const MyIterator& rhs) const;
  53. 	bool operator!=(const MyIterator& rhs) const;
  54. 	unsigned int operator*() const;
  55. };
  56.  
  57. // Read-only container which stores a sorted collection of numbers
  58. // memory-efficiently in Blocks.
  59. class MyContainer {
  60. public:
  61. 	using const_iterator = MyIterator;
  62.  
  63. private:
  64. 	DATA_VECTOR_T data;
  65.  
  66. public:
  67. 	// The initializer list must be sorted in non-descending order.
  68. 	MyContainer(std::initializer_list<unsigned int> il);
  69. 	unsigned int operator[](std::size_t idx) const;
  70. 	MyContainer::const_iterator begin() const;
  71. 	MyContainer::const_iterator cbegin() const;
  72. 	MyContainer::const_iterator end() const;
  73. 	MyContainer::const_iterator cend() const;
  74. };
  75.  
  76.  
  77. // Definitions:
  78.  
  79. // class Block
  80. Block::Block(unsigned short radix): radix(radix) {}
  81.  
  82. unsigned short Block::getRadix() const {
  83. 	return radix;
  84. }
  85.  
  86. void Block::pushSuffix(const unsigned short suffix) {
  87. 	suffixes.push_back(suffix);
  88. }
  89.  
  90. std::size_t Block::size() const {
  91. 	return suffixes.size();
  92. }
  93.  
  94. unsigned int Block::operator[](std::size_t idx) const {
  95. 	return
  96. 		(unsigned int)(radix)*RADIX_MULTIPLIER +
  97. 		(unsigned int)(suffixes[idx]);
  98. }
  99.  
  100. Block::SUFFIX_VECTOR_T::const_iterator Block::begin() const {
  101. 	return suffixes.begin();
  102. }
  103.  
  104. Block::SUFFIX_VECTOR_T::const_iterator Block::cbegin() const {
  105. 	return begin();
  106. }
  107.  
  108. Block::SUFFIX_VECTOR_T::const_iterator Block::end() const {
  109. 	return suffixes.end();
  110. }
  111.  
  112. Block::SUFFIX_VECTOR_T::const_iterator Block::cend() const {
  113. 	return end();
  114. }
  115.  
  116. // class MyContainer
  117. // The initializer list must be sorted in non-descending order.
  118. MyContainer::MyContainer(std::initializer_list<unsigned int> il) {
  119. 	if (il.size() == 0) {
  120. 		return;
  121. 	}
  122.  
  123. 	unsigned short radix = *il.begin() / Block::RADIX_MULTIPLIER;
  124. 	data.push_back(Block(radix));
  125. 	for (const auto x : il) {
  126. 		radix = x / Block::RADIX_MULTIPLIER;
  127. 		if (data.back().getRadix() != radix) {
  128. 			data.push_back(Block(radix));
  129. 		}
  130.  
  131. 		unsigned short suffix = x % Block::RADIX_MULTIPLIER;
  132. 		data.back().pushSuffix(suffix);
  133. 	}
  134. }
  135.  
  136. unsigned int MyContainer::operator[](std::size_t idx) const {
  137. 	auto data_it = data.begin();
  138.  
  139. 	// Similarly to std::vector::operator[], if idx is out of bounds of the
  140. 	// container, the behavior is undefined.
  141. 	while (idx >= data_it->size()) {
  142. 		idx -= data_it->size();
  143. 		++data_it;
  144. 	}
  145.  
  146. 	return (*data_it)[idx];
  147. }
  148.  
  149. MyContainer::const_iterator MyContainer::begin() const {
  150. 	return MyIterator(data, data.cbegin());
  151. }
  152.  
  153. MyContainer::const_iterator MyContainer::cbegin() const {
  154. 	return begin();
  155. }
  156.  
  157. MyContainer::const_iterator MyContainer::end() const {
  158. 	return MyIterator(data, data.end());
  159. }
  160.  
  161. MyContainer::const_iterator MyContainer::cend() const {
  162. 	return end();
  163. }
  164.  
  165. // class MyIterator
  166. MyIterator::MyIterator(
  167. 		const DATA_VECTOR_T& data,
  168. 		const DATA_VECTOR_T::const_iterator start_block_it):
  169. 		data(data), block_it(start_block_it) {
  170. 	if (data.cend() != block_it) {
  171. 		suffix_it = block_it->cbegin();
  172. 	}
  173. }
  174.  
  175. MyIterator& MyIterator::operator++() {
  176. 	if (data.cend() == block_it) {
  177. 		return *this;
  178. 	}
  179.  
  180. 	++suffix_it;
  181.  
  182. 	if (block_it->cend() == suffix_it) {
  183. 		++block_it;
  184.  
  185. 		if (data.cend() != block_it) {
  186. 			suffix_it = block_it->cbegin();
  187. 		}
  188. 	}
  189.  
  190. 	return *this;
  191. }
  192.  
  193. MyIterator MyIterator::operator++(int) {
  194. 	MyIterator tmp = *this;
  195. 	operator++();
  196. 	return tmp;
  197. }
  198.  
  199. bool MyIterator::operator==(const MyIterator& rhs) const {
  200. 	// If this iterator has reached the end:
  201. 	if (data.cend() == block_it) {
  202. 		// Only return true if both iterators point to the end of the same
  203. 		// object.
  204. 		return data.cend() == rhs.block_it;
  205. 	}
  206.  
  207. 	return block_it == rhs.block_it
  208. 		&& suffix_it == rhs.suffix_it;
  209. }
  210.  
  211. bool MyIterator::operator!=(const MyIterator& rhs) const {
  212. 	return !(*this == rhs);
  213. }
  214.  
  215. unsigned int MyIterator::operator*() const {
  216. 	const std::size_t idx = suffix_it - block_it->cbegin();
  217. 	return (*block_it)[idx];
  218. }
  219.  
  220.  
  221. // Entry point:
  222.  
  223. int main() {
  224. 	std::vector<unsigned int> v = {
  225. 		1234, 1254, 1264, 1265, 1267, 1268, 1271, 1819, 1832, 1856, 1867, 1892,
  226. 		3210, 3214, 3256, 3289
  227. 	};
  228.  
  229. 	// Print the entire vector.
  230. 	for (const auto x: v) {
  231. 		std::cout << x << "\t";
  232. 	}
  233. 	std::cout << std::endl;
  234.  
  235. 	// Print a randomly accessed element from the vector.
  236. 	std::cout << v[10] << std::endl;
  237.  
  238.  
  239. 	MyContainer c = {
  240. 		1234, 1254, 1264, 1265, 1267, 1268, 1271, 1819, 1832, 1856, 1867, 1892,
  241. 		3210, 3214, 3256, 3289
  242. 	};
  243.  
  244. 	// Print the entire container.
  245. 	for (const auto x: c) {
  246. 		std::cout << x << "\t";
  247. 	}
  248. 	std::cout << std::endl;
  249.  
  250. 	// Print a randomly accessed element from the container.
  251. 	std::cout << c[10] << std::endl;
  252.  
  253. 	return 0;
  254. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1234	1254	1264	1265	1267	1268	1271	1819	1832	1856	1867	1892	3210	3214	3256	3289	
1867
1234	1254	1264	1265	1267	1268	1271	1819	1832	1856	1867	1892	3210	3214	3256	3289	
1867
https://ideone.com/eeAKYN
language:
C++14 (gcc 8.3)
created:
6 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!