#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <iomanip>
/*
This program demonstrates how to find the 3 products with the lowest cost
from a list of product–price pairs.
We use:
- std::vector for storage
- std::partial_sort for efficient selection of the smallest 3 items
- clear helper functions
- detailed comments explaining each step
*/
// A simple struct to hold product data
struct Product {
std::string name;
int price; // price in dollars
};
// Generate random products with prices between 1 and 20
std::vector<Product> generateProducts(int total_products) {
std::vector<Product> products;
products.reserve(total_products);
// Random engine setup
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dist(1, 20);
// Create p1, p2, ..., total_products
for (int i = 1; i <= total_products; i++) {
products.push_back(Product{"p" + std::to_string(i), dist(gen)});
}
return products;
}
// Print all products
void printProducts(const std::vector<Product>& products) {
std::cout << "All products:\n";
for (const auto& p : products) {
std::cout << " " << std::setw(3) << p.name << " $" << p.price << "\n";
}
std::cout << "\n";
}
// Find the 3 cheapest products using partial_sort
std::vector<Product> findThreeCheapest(std::vector<Product> products) {
/*
partial_sort rearranges the first k elements into sorted order,
and ensures they are the k smallest elements overall.
This is more efficient than sorting the entire array when we only
need a small subset.
*/
const std::size_t k = 3;
std::partial_sort(
products.begin(),
products.begin() + k,
products.end(),
[](const Product& a, const Product& b) {
return a.price < b.price; // sort by price ascending
}
);
// Return only the first 3 items
return {products.begin(), products.begin() + k};
}
int main() {
// Generate random products
auto products = generateProducts(10);
// Display all products
printProducts(products);
// Find the 3 cheapest
auto cheapest = findThreeCheapest(products);
// Display the result
std::cout << "Three cheapest products:\n";
for (const auto& p : cheapest) {
std::cout << " " << std::setw(3) << p.name << " $" << p.price << "\n";
}
}
/*
run:
All products:
p1 $11
p2 $2
p3 $7
p4 $1
p5 $18
p6 $16
p7 $20
p8 $17
p9 $15
p10 $9
Three cheapest products:
p4 $1
p2 $2
p3 $7
*/