| 446 | |
| 447 | protected: |
| 448 | void Run(CppBenchmark::Context& context) override |
| 449 | { |
| 450 | // Generate items to sort |
| 451 | std::generate(items.begin(), items.end(), rand); |
| 452 | |
| 453 | // Cache radix queue for all digits |
| 454 | std::queue<int> radix_queue[10]; |
| 455 | |
| 456 | // Initial radix base |
| 457 | size_t n = 1; |
| 458 | |
| 459 | bool found; |
| 460 | do |
| 461 | { |
| 462 | // Reset found flag |
| 463 | found = false; |
| 464 | |
| 465 | // Try to put all items into the radix queue |
| 466 | for (size_t i = 0; i < items.size(); ++i) |
| 467 | { |
| 468 | // Get the base item value |
| 469 | size_t base = items[i] / n; |
| 470 | |
| 471 | // Update found flag |
| 472 | found |= base > 0; |
| 473 | |
| 474 | // Get the item index in the radix queue |
| 475 | size_t index = base % 10; |
| 476 | |
| 477 | // Add the item into the radix queue |
| 478 | radix_queue[index].push(items[i]); |
| 479 | } |
| 480 | |
| 481 | // Back items from the radix list |
| 482 | if (found) |
| 483 | { |
| 484 | size_t index = 0; |
| 485 | for (size_t i = 0; i < sizeof(radix_queue) / sizeof(radix_queue[0]); ++i) |
| 486 | { |
| 487 | // Get all items from the corresponding radix queue |
| 488 | while (!radix_queue[i].empty()) |
| 489 | { |
| 490 | items[index++] = radix_queue[i].front(); |
| 491 | radix_queue[i].pop(); |
| 492 | } |
| 493 | } |
| 494 | } |
| 495 | |
| 496 | // Increase the current radix base |
| 497 | n *= 10; |
| 498 | } while (found); |
| 499 | context.metrics().AddItems(items.size()); |
| 500 | } |
| 501 | }; |
| 502 | |
| 503 | class StdSort : public CppBenchmark::Benchmark, public SortFixture |