fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <utility>
  5. #include <string>
  6. #include <map>
  7. using namespace std;
  8.  
  9.  
  10. void PrintPair(const std::pair<int, std::string>& thePair)
  11. {
  12. 	std::cout << thePair.first << ", " << thePair.second << std::endl;
  13. }
  14.  
  15. int main() {
  16. 	// create our vector
  17. 	std::vector<std::pair<int, std::string>> myVector{
  18. 		std::make_pair(10,"bcd"),
  19. 		std::make_pair(2, "abc"),
  20. 		std::make_pair(30, "def"),
  21. 		std::make_pair(2, "xyz"),
  22. 		std::make_pair(50, "mn")
  23. 	};
  24.  
  25.  
  26. 	// print vector before sorting
  27. 	std::cout << "vector before sorting:\n";
  28. 	for (auto&& nextPair : myVector)
  29. 	{
  30. 		std::cout << nextPair.first << ", " << nextPair.second << std::endl;
  31. 	}
  32.  
  33. 	// sort it on the ints in the pairs
  34. 	std::stable_sort(std::begin(myVector),std::end(myVector), [](const std::pair<int,std::string>& lhs, const std::pair<int,std::string>& rhs){return lhs.first < rhs.first;});
  35.  
  36. 	// print vector after sorting
  37. 	std::cout << "\nvector after sorting\n";
  38. 	for (auto&& nextPair : myVector)
  39. 	{
  40. 		std::cout << nextPair.first << ", " << nextPair.second << std::endl;
  41. 	}
  42.  
  43. 	std::map<int, decltype(myVector)> myBuckets;
  44. 	for (auto&& nextElement : myVector)
  45. 	{
  46. 		if (myBuckets.find(nextElement.first) == myBuckets.end())
  47. 			myBuckets[nextElement.first] = decltype(myVector){nextElement};
  48. 		else
  49. 			myBuckets[nextElement.first].emplace_back(nextElement);
  50. 	}
  51.  
  52. 	//needs at least a 2 element vector to work
  53. 	cout << "\nFinal output:\n";
  54. 	// create buckets for each value, internally each bucket is stable sorted
  55. 	// the buckets are sorted on map value
  56. 	// print out each element in a bucket before moving onto the next bucket
  57. 	auto bucketsBegin = myBuckets.begin();
  58. 	auto bucketsEnd = myBuckets.end();
  59. 	--bucketsEnd;
  60. 	auto nextEndElement = bucketsEnd->second.begin();
  61. 	auto nextBeginElement = bucketsBegin->second.begin();
  62. 	while(bucketsBegin != myBuckets.end() && bucketsBegin != bucketsEnd)
  63. 	{
  64. 		if (bucketsEnd != bucketsBegin)
  65. 		{
  66. 			PrintPair(*nextEndElement);
  67. 			++nextEndElement;
  68. 			if (nextEndElement == bucketsEnd->second.end())
  69. 			{
  70. 				bucketsEnd--;
  71. 				nextEndElement = bucketsEnd->second.begin();
  72. 			}
  73. 		}
  74. 		PrintPair(*nextBeginElement);
  75. 		++nextBeginElement;
  76. 		if (nextBeginElement == bucketsBegin->second.end())
  77. 		{
  78. 			bucketsBegin++;
  79. 			if (bucketsBegin != myBuckets.end())
  80. 				nextBeginElement = bucketsBegin->second.begin();
  81. 		}
  82. 	}
  83. 	 //print remainder
  84. 	 while(nextBeginElement != bucketsBegin->second.end())
  85. 	 {
  86. 	 	PrintPair(*nextBeginElement);
  87. 	 	++nextBeginElement;
  88. 	 }
  89.  
  90.  
  91.  
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 3240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
vector before sorting:
10, bcd
2, abc
30, def
2, xyz
50, mn

vector after sorting
2, abc
2, xyz
10, bcd
30, def
50, mn

Final output:
50, mn
2, abc
30, def
2, xyz
10, bcd
https://ideone.com/rY9rMk
language:
C++14 (gcc 8.3)
created:
10 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!