Лучше std :: find для набора указателей и сравнения разыменованного значения с константным ссылочным значением - PullRequest
Новая
       35

Лучше std :: find для набора указателей и сравнения разыменованного значения с константным ссылочным значением

0 голосов
/ 05 января 2012

Первоначально у меня был член, который был std::vector<Point> с методом, который сделал это: 

bool Spline::Intersects(const Point& point) const {
    return std::find(this->_result_points.begin(), _result_points.end(), point) != _result_points.end();
}

Дизайн изменился и std::vector<Point> стал std::vector<Point*>, и предыдущий метод больше не работал, и мне пришлось изменить его на: 

bool Spline::Intersects(const Point& point) const {
    for(std::vector<Point*>::const_iterator _iter = _result_points.begin(); _iter != _result_points.end(); ++_iter) {
        if(*(*_iter) == point) return true;
    }
    return false;
}

std::find выполняет тот же линейный поиск? Если да, то есть ли более быстрый / лучший / менее грубый способ сделать это (особенно двойная обратная ссылка итератора)?

В коде есть и другие места, где выполняется std::find(this->_result_points.begin(), _result_points.end(), point) != _result_points.end(); (или аналогичные, но противоположные результаты), и я бы не стал использовать этот медленный линейный цикл for.

1 Ответ

3 голосов
/ 05 января 2012

Да, find выполняет тот же линейный поиск.

Вы можете скрыть цикл и двойную косвенность, используя find_if с подходящим предикатом: bool operator()(Point* ptr) { return *ptr == point; }

Если вы хотите избежать линейного поиска, вам нужно изменить способ хранения данных. Например, сохранение отсортированного вектора позволило бы std::binary_search, что быстрее, чем std::find. Это отсортировано по значению, указанному, , а не , отсортированному по значению указателя, поэтому вам нужно будет передать компаратор в std::sort и т. Д. Или вы можете использовать совершенно другой контейнер: возможно, один из (unordered_)(multi)set .

...