Сортировка массива структур в C++

Question

Я использую библиотеку физики частиц, написанную на C++ для игры.

Для того, чтобы привлечь частицы я должен получить массив всех своих позиций, как так ..

b2Vec2* particlePositionBuffer = world->GetParticlePositionBuffer(); 

Это возвращает массив объектов b2Vec2 (которые представляют 2 мерные векторы в физическом движке).
Также я могу получить и установить их цвет, используя

b2ParticleColor* particleColourBuffer = world->GetParticleColorBuffer(); 

Я хотел бы получить 10% частиц с высокими значениями Y (а затем изменить их цвет)

Моя идея ..
1. Сделайте массив структур равным размеру массива particlePositionBuffer, структура просто содержит int (индекс частиц в массиве particlePositionBuffer) и float (положение y частиц)
2. Затем я сортирую массив по позиции y.
3. Затем я использую int в структуре из 10 лучших структур в моем массиве struct, чтобы делать материал своим цветом в массиве particleColourBuffer.

Может ли кто-нибудь показать мне, как сортировать и массивы таких структур, как в C++?
Как вы думаете, это достойный способ обойти это? Мне нужно сделать это только один раз (не каждый кадр)

Answer 1

После может помочь:

// Functor to compare indices according to Y value. 
struct comp 
{ 
    explicit comp(b2Vec2* particlePositionBuffer) : 
     particlePositionBuffer(particlePositionBuffer) 
    {} 
    operator (int lhs, int rhs) const 
    { 
     // How do you get Y coord ? 
     // note that I do rhs < lhs to have higher value first. 
     return particlePositionBuffer[rhs].getY() < particlePositionBuffer[lhs].getY(); 
    } 
    b2Vec2* particlePositionBuffer; 
}; 

void foo() 
{ 
    const std::size_t size = world->GetParticleCount(); // How do you get Count ? 
    const std::size_t subsize = size/10; // check for not zero ? 

    std::vector<std::size_t> indices(size); 

    for (std::size_t i = 0; i != size; ++i) { 
     indices[i] = i; 
    } 
    std::nth_element(indices.begin(), indices.begin() + subsize, indices.end(), 
     comp(world->GetParticlePositionBuffer())); 

    b2ParticleColor* particleColourBuffer = world->GetParticleColorBuffer(); 
    for (std::size_t i = 0; i != subsize; ++i) { 
     changeColor(particleColourBuffer[i]) 
    } 
} 

Answer 2

Если ваш счетчик частиц низок, это не имеет большого значения в любом случае, и сначала их сортировка с помощью простой процедуры сортировки stl будет прекрасной.

Если число было большим, я бы создал двоичное дерево поиска, максимальный размер которого составлял 10% от числа ваших частиц. Тогда я бы сохранил minY, фактически сохраненный в дереве, для быстрого отклонения. Тогда этот алгоритм должен сделать это:

• Прогулка через исходный массив и добавлять элементы к дереву, пока он не заполнится (10%)
• Обновите MinY
• Для остальных элементов в исходном массиве
  • Если item.y меньше MinY, перейдите к следующему пункту (быстрое отбраковки)
  • в противном случае
    • Извлеките наименьшее значение Y из дерева
    • Добавьте больше Y элемент в дереве
    • Update MinY

Двоичное дерево имеет хорошее преимущество быстрой вставки, быстрый поиск, и поддерживать порядок. Если вы хотите быть FAST, это лучше, чем полная сортировка по всему массиву.