Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Оптимизация нахождения элементов в векторе

Автор: Paspartu 26.9.2008, 09:35

Доброго времени суток.

Помогите сделать оптимизацию.

Есть следующие классы:

Код


class A
{
    //....
    int nID;
    POINT ptPos;
//....
};

class B
{
    //....
    vector <A*>pA_Vect;
    BOOL GetProperties(int nLevel, Properties* pPrp);
//....
};

struct Properties
{
    //....
    int nStart;
    int nEnd;
//....
};

//.....

BOOL B::GetProperties(int nLevel, Properties* pPrp)
{
    //...
    pPrp-> nStart = -1;
    pPrp-> nEnd  = -1;

    int nSize = this->pA_Vec.size();
    for(int n = 0; n < nSize; n++)
{
    if(this->pA_Vec[n]-> ptPos.y == nLevel)
    {
        (pPrp-> nStart == -1)? pPrp-> nStart = n:NULL;
        pPrp-> nEnd  = n;
    }
}
    //...
}

Вопрос такой надо в векторе находить элементы по заданному критерию, в данном случае те у которых this->pA_Vec[n]-> ptPos.y == nLevel (т.к. эти элементы обязательно стоят по порядку, то находить индекс первого и последнего элемента удовлетворяющих критерию) затем с этими элементами производится ряд других действий.
Кроме как сделать структуру Properties и в дальнейшем работать с ней я больше ничего не придумал...
Так как эта функция вызывается очень много раз то возник вопрос ее оптимизации.
Возможно ли использовать итераторы? На много ли это повысит производительность?

P.S. Пишу по памяти, возможны синтактические ошибки.

Автор: Alek86 26.9.2008, 09:55

Paspartu, может, лучше использовать set или multiset?

Автор: georain 26.9.2008, 14:59

Paspartu, если элементы в векторе изменяются очень редко, то при каждом добавлении вместо push_back() можно делать insert() в нужную позицию, чтобы вектор всегда был отсортированным. Тогда можно будет сказать что все элементы после заданного больше (меньше или какой критерий сортировки) этого и твой алгоритм будет работать. Ну и соответственно у элементов вектора изменять нельзя данные-критерий сортировки (у тебя это ptPos.y), для этого придётся этот элемент выдернуть и вставить на новое место. По быстродействию все будет идеально пока элементы вектора будут изменяться очень редко.
Если они изменяются достаточно часто используй set, multiset, map или multimap. Там используются автоматическая сортировка при вставке, но для их использования нужно будет использовать итераторы. При частом изменении элементов эти контейнеры в твоей задаче будут работать более эффективно.

Автор: Earnest 26.9.2008, 16:10

Цитата(Paspartu @ 26.9.2008, 10:35

)

т.к. эти элементы обязательно стоят по порядку

Это означает, что элементы отсортированы по y? Если да, то используй equal_range и соответствующий предикат.