Вопрос по stl, std, c++, c++11 – Почему set :: find не шаблон?

6

С шаблонными функциями из<algorithm> ты можешь делать такие вещи

struct foo
{
    int bar, baz;
};

struct bar_less
{
    // compare foo with foo
    bool operator()(const foo& lh, const foo& rh) const
    {
        return lh.bar < rh.bar;
    }
    template<typename T>  // compare some T with foo
    bool operator()(T lh, const foo& rh) const
    {
        return lh < rh.bar;
    }
    template<typename T>  // compare foo with some T
    bool operator()(const foo& lh, T rh) const
    {
        return lh.bar < rh;
    }
};

int main()
{
    foo foos[] = { {1, 2}, {2, 3}, {4, 5} };
    bar_less cmp;
    int bar_value = 2;
    // find element {2, 3} using an int
    auto it = std::lower_bound(begin(foos), end(foos), bar_value, cmp);
    std::cout << it->baz;
}

Вstd::set методы, такие какfind Вы должны передать объект типаset::key_type что часто заставляет вас создавать фиктивный объект.

set<foo> foos;
foo search_dummy = {2,3};  // don't need a full foo object;
auto it = foos.find(search_dummy);

Было бы очень полезно, если бы можно было просто позвонитьfoos.find(2), Есть ли причина, почемуfind не может быть шаблоном, принимающим все, что может быть передано меньшему предикату. И если это просто отсутствует, почему это не в C ++ 11 (я думаю, что это не так).

Edit

Основной вопрос: ПОЧЕМУ это невозможно, и если это было возможно, ПОЧЕМУ решил, что стандарт не предусматривает этого? А второй вопрос вы можете предложить обходные пути :-) (boost::multi_index_container только что пришло мне в голову, что обеспечивает извлечение ключей из типов значений)

Другой пример с более дорогим для построения типом значения. Ключname является частью типа и не должен использоваться в качестве копии в ключе карты;

struct Person
{
    std::string name;
    std::string adress;
    std::string phone, email, fax, stackoferflowNickname;
    int age;
    std::vector<Person*> friends;
    std::vector<Relation> relations;
};

struct PersonOrder
{
    // assume that the full name is an unique identifier
    bool operator()(const Person& lh, const Person& rh) const
    {
        return lh.name < rh.name;
    }
};

class PersonRepository
{
public:

    const Person& FindPerson(const std::string& name) const
    {
        Person searchDummy;  // ouch
        searchDummy.name = name;
        return FindPerson(searchDummy);
    }

    const Person& FindPerson(const Person& person) const;

private:
    std::set<Person, PersonOrder> persons_;
    // what i want to avoid
    // std::map<std::string, Person> persons_;
    // Person searchDummyForReuseButNotThreadSafe;

};
Я думаю, можно утверждать, что если бы такие мелкозернистые были необходимы, то можно было бы использоватьstd::find с подходящим предикатом. juanchopanza
Нет, но найти яблоко в коллекции яблок просто, описав цвет яблока без описания всего этого. hansmaad
Имеет ли смысл найти яблоко среди коллекции груш? juanchopanza
Если вам нужно искать что-то, кромеfooпочему вы используетеset и неmap? В этом вся суть того, что они разных типов: вы ищете по ключу, а не по значению. Вы используете толькоset если ключ поискаis значение (или если вы просто хотите отсортированный набор элементов). Nicol Bolas
@NicolBolas Потому что это частьfoo, Если я хранюPersons однозначно индексируется по его полному имени иNameявляется собственностьюPerson Я хотел бы хранить их вset (или определитьmap::value_type вPerson и что-то вродеmap::key_extractorвPerson::Name) hansmaad

Ваш Ответ

5   ответов
2

Стандарт гласит, чтоstd::set::find имеет сложность логарифмического времени. На практике это достигается путем реализацииstd::set в виде двоичного дерева поиска, сстрогий слабый порядок сравнение используется в качестве критерия сортировки. Любой поиск, который не удовлетворял бы таким же строгим критериям слабого упорядочения, не удовлетворял бы логарифмической сложности. Так что это дизайнерское решение: если вы хотите логарифмической сложности, используйтеstd::set::find, Если вы можете обменять сложность на гибкость, используйтестанд :: find_if на съемочной площадке.

Мне не нужноfind_if, Я хочу предоставить критерии сортировки, которые могут сравнивать foo с int и int с foo. hansmaad
@hansmaad Проблема в том, что вам нужен двоичный предикат для построения набора. Это то, что используется для поиска, и нет никакого способа обойти это. Еслиfoo имел неявное преобразование из int (через неявный конструктор с одним параметром), тогда вы могли искать с использованием int, но неясно, работает ли это для ваших конкретных потребностей.
0

Потому что если вы хотите сделатьstd::find(2) Вы должны будете определить, какint будет сравнивать сfoo в дополнение к сравнению между двумяfoos. Но с тех порint а такжеfoo разные типы, вам понадобятся две дополнительные функции:

bool operator<(int, foo);
bool operator<(foo, int);

(или некоторая другая логическая эквивалентная пара).

Теперь, если выdo что вы на самом деле определяетеbijective function междуint а такжеfoo и вы могли бы просто использоватьstd::map<int, foo> и будет сделано.

Если вы все еще не хотитеstd::map но вам нужны преимущества сортированного поиска, тогда фиктивный объект - это самый простой способ.

Конечно, стандартstd::set может предоставить функцию-член, которой вы передаете функцию, которая получаетfoo и возвращают -1, 0, 1, если он меньше, равен или больше, чем искомый ... но это не так, как в C ++. И обратите внимание, что дажеbsearch() принимает два аргумента одного типа!

1

Они предоставили то, что вы хотите, но совсем не так, как вы думаете.

На самом деле, есть два разных способа: один - построить конструктор для содержащегося класса, который 1) может использоваться неявно, и 2) требует только подмножества элементов, которые вам действительно нужны для сравнения. С этим на месте, выcan сделать поискfoods.find(2);, Выwill в конечном итоге создание временного объекта из2затем найти этот временный объект,but это будет настоящий временный. Ваш код не должен иметь дело с ним явно (где угодно).

Изменить. То, о чем я здесь говорю, - это создание экземпляра того же типа, который вы сохраняете на карте, но (возможно) оставление любого поля, которое вы не используете в качестве «ключа». неинициализирован (или инициализирован чем-то, говорящим «не присутствует»). Например:

struct X { 
   int a; // will be treated as the key
   std:::string data;
   std::vector<int> more_data;
public:
   X(int a) : a(a) {} // the "key-only" ctor
   X(int a, std::string const &d, std::vector<int> const &m); // the normal ctor
};

std::set<X> s;

if (s.find(2)) { // will use X::X(int) to construct an `X`
    // we've found what we were looking for
}

Да, когда вы строите свойX (или то, что я в любом случае назвал X) с конструктором с одним аргументом, есть вероятность, что то, что вы создаете, не будет пригодно для чего-либо, кроме поиска.

конец редактирования]

Второе, для которого библиотека обеспечивает более прямую поддержку, часто немного проще: если вы действительно используете только некоторое подмножество элементов (возможно, только один) для поиска, то вы можете создатьstd::map вместоstd::set, Сstd::mapпоиск экземпляра того, что вы указали в качестве типа ключа, поддерживается явно / напрямую.

Можете ли вы объяснить 1-й способ более подробно. Вы имеете в виду имплицитный ctorfoo(int i):bar(i){}? Это позволяет мне писатьfind(2) но строит полныйfoo (который может быть очень дорогим в других случаях) или нет? hansmaad
@hansmaad: я отредактировал простой пример в ответе.
3

std::find_if работает на несортированном диапазоне. Таким образом, вы можете передать любой предикат, который вы хотите.

std::set<T> всегда используетComparator аргумент шаблона (std::less<T> по умолчанию) для поддержания порядка коллекции, а также для поиска элементов снова.

Так что еслиstd::set::find шаблон, это может потребовать, чтобы вы передавали только предикат, который наблюдает за общим порядком компаратора.

Тогда снова,std::lower_bound и все другие алгоритмы, которые работают на отсортированных диапазонах, уже требуют именно этого, так что это не будет новым или неожиданным требованием.

Итак, я полагаю, это просто упущение, что нетfind_if() (скажем) наstd::set, Предлагаю это для C ++ 17 :) (EDIT:: ВОСТОКуже есть этои они использовали гораздо лучшее имя, чем я:find_as).

Тем не менее, вы знаете, чтоВы не должны использоватьstd::set, вы? Сортированный вектор в большинстве случаев будет быстрее и даст вам ту гибкость, которой вам не хватает вstd::set.

EDIT: Как указывал Николь, в этой реализацииУвеличение а такжеLoki (как и везде, я уверен), но, видя, что вы не можете использовать их основное преимущество (встроенныйfind() метод), вы не потеряете много, используя голыйstd::vector.

Если вы собираетесь использовать отсортированныйvectorминимум, что вы могли бы сделать, это указать пользователю в направленииBoost.Container's flat sets/mapsпоэтому они не должны сами писать код.
@NicolBolas: reboost::container::flat_setСпасибо за предложение. Это действительно может сделать работу немного проще, но это не похоже на использование отсортированного вектора, это наука о ракетостроении, особенно когда OP не может использоватьflat_set::find (по той же причине, по которой он не может использоватьset::find).
Также,find_if не будет иметь никакого смысла вset, Время выполнения будет линейным, поскольку не будет гарантировано, что предикат будет основан на алгоритме сортировки. Log (n) времяfind работает только потому, что поиск основан на порядке сортировки. Это не недосмотр; если вы хотите выполнить линейный поиск чего-либо вsetВы могли бы просто использоватьstd::find_if наsetитераторы. Функции-члены предназначены для операций, которые вы не можете выполнятьwithout быть навязчивым Как в журнале (n) поиск элемента на основе порядка сортировки.
@NicolBolas: refind_ifКак вы правильно указали,set::find не нравитсяstd::find в том, что он выполняется в логарифмическом времени, а не линейно.set::find_ifто будет относиться кset::find какstd::find_if делает дляstd::find: Как «перегрузка» который принимает предикат вместо значения (_if суффикс, вызванный отсутствием поддержки перегрузки концепций), и это то, о чем просил OP. Особенно,set::find_if будет выполняться в логарифмическом времени тоже, потому что, какset::find, он использует бинарный поиск, независимо отfind Название и его коннотации.
Спасибо за ссылку наfind_as! Кажется, это был один из 14crazy idea for stdlib c++11, Жаль, что он не попал в стандарт. Плоский набор / совет Локи не имеет отношения к моему вопросу, я знаю, как выбирать между двоичным_поиском, деревьями или контейнерами на основе хеша. hansmaad
0

key_type is a member type defined in set containers as an alias of Key, which is the first template parameter and the type of the elements stored in the container.

Увидетьдокументация.

Для пользовательских типов нет никакой возможности узнать, какой тип ключа у библиотеки. Так получилось, чтоfor your particular use case тип ключаint, Если вы используетеset< int > s; ты можешь позвонитьs.find( 2 );, Тем не менее, вам нужно будет помочь компилятору, если вы хотите найтиset< foo > и хотите передать только целое число (подумайте, как будетsetработа заказа междуfoo иint).

Похожие вопросы