Блог

Мне нужно сохранить идентификаторы между (0,100) в некоторых структурах данных, там будет не более 100 идентификаторов, и мне нужен простой и быстрый способ найти минимальное число в структуре данных и простой способ вставить и удалить определенное число в структуре данных, например, если это будет list, поэтому list.append(1) , list.append(2) list.append(99) , list.remove(2) a = list.min() . Я немного новичок в c и не уверен, какая структура данных его эффективно поддерживает.

вы можете использовать std::set , которое обычно реализуется в виде двоичного дерева поиска.

Его методы insert() , erase() и find() имеют логарифмический размер, но могут работать лучше, если дана подсказка. Логарифмическая сложность относится к набору деревьев Java.

Я думаю, вас должно заинтересовать std::lower_bound , которое возвращает итератор к нижней границе, и std::upper_bound , которое возвращает итератор к верхней границе.

Для этого запроса существует специальная структура данных: куча 🙂

 std::vector<std::uint32_t> vInts = { 25,10,35,30,5,15 };

//converts to min heap
std::make_heap(vInts.begin(), vInts.end(), std::greater<std::uint32_t>());

//5
std::cout << *vInts.begin() << std::endl;

//pop 5
std::pop_heap(vInts.begin(), vInts.end(), std::greater<std::uint32_t>());
vInts.pop_back();
std::cout << *vInts.begin() << std::endl; //10

//pop 10
std::pop_heap(vInts.begin(), vInts.end(), std::greater<std::uint32_t>());
vInts.pop_back();

//push 20. min will be still 15
vInts.push_back(20);
std::push_heap(vInts.begin(), vInts.end(), std::greater<std::uint32_t>());
std::cout << *vInts.begin() << std::endl; //15

//pop 15
std::pop_heap(vInts.begin(), vInts.end(), std::greater<std::uint32_t>());
vInts.pop_back();

std::cout << *vInts.begin() << std::endl; //20
  

Простой:

 std::vector<int> container;
container.reserve(100);
// ... put stuff in container ...
const auto min_elem =
    std::min_element(container.begin(), 
        container.end());