Bagaimana saya melakukan fungsi find() atau lower_bound() pada std::set menggunakan fungsi pembanding yang tidak bergantung pada kuncinya sehingga masih berjalan dalam waktu O(log N)?

Misalkan saya mendefinisikan tipe data foo dengan dua variabel x dan y dan memiliki std::set<foo> yang menggunakan x sebagai nilai kunci.

struct foo {
    int x, y;
    foo(int x, int y) : x(x), y(y) {}
};

struct xCompare {
    bool operator() (const foo& i, const foo& j) const {
        return i.x < j.x;
    }
};

// Within main()
std::set<foo, xCompare> fooSetX;

Apakah mungkin untuk melakukan pencarian biner menggunakan lower_bound() atau fungsi lain yang membandingkan nilai y?

Demi argumen ini, asumsikan bahwa x dan y adalah unik dan independen satu sama lain, dan diberikan dua variabel foo foo1 dan foo2, jika foo1.x < foo2.x, maka foo1.y < foo2.y. Ini berarti bahwa saya tidak dapat menyatakan y sebagai fungsi dari x, tetapi juga diurutkan oleh y dalam fooSetX.

Misalnya, jika diberikan tiga nilai foo(x,y) (2,5), (3,9) dan (5,10) dalam fooSet, lower_bound() yang menggunakan y = 7 sebagai istilah pencarian akan mengembalikan iterator yang menunjuk ke (3,9).

Saat ini, cara saya menyelesaikan ini adalah dengan memiliki dua std::set<foo>, masing-masing diurutkan oleh x dan y. Setiap kali saya perlu mencari berdasarkan y, saya menggunakan std::set kedua.

struct yCompare {
    bool operator() (const foo& i, const foo& j) const {
        return i.y < j.y;
    }
};

// Within main()
std::set<foo, yCompare> fooSetY;

// Inserting elements
fooSetX.insert(foo(2,5)); fooSetY.insert(foo(2,5));
fooSetX.insert(foo(3,9)); fooSetY.insert(foo(3,9));
fooSetX.insert(foo(5,10)); fooSetY.insert(foo(5,10));

// lower_bound() with y = 7
std::set<foo>::iterator it = fooSetY.lower_bound(foo(0,7)); // points to (3,9)
0
Muhammad Irham Rasyidi 17 Maret 2017, 14:42

2 jawaban

Jawaban Terbaik

Anda tidak dapat secara langsung meneruskan pembanding khusus ke std::set::lower_bound - Anda harus meneruskannya ke templat kelas itu sendiri, karena akan digunakan secara internal untuk mempertahankan urutan objek (akibatnya membuat std::set::lower_bound berfungsi).

Berikut cara mendefinisikan std::set template:

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

Compare adalah satu-satunya titik penyesuaian pemesanan yang memungkinkan Anda menyediakan objek fungsi yang akan membandingkan objek Anda seperti yang diinginkan sebagai pengganti std::less<Key>.

Tidak ada cara untuk menambahkan predikat pengurutan tambahan ke std::set.


Jika Anda menginginkan pengurutan tambahan pada objek Anda yang memungkinkan Anda mencapai pencarian O(log N), Anda dapat menggunakan struktur terurut lain yang tetap sinkron dengan yang asli. std::set pointer ke objek di set pertama yang menggunakan komparator berbeda bisa bekerja. Contoh:

class MySet
{
private:
    std::set<Item, Comparator0> _set0;
    std::set<decltype(_set0.begin()), Comparator1> _set1;

public:
    void insert(Item x) 
    {
        auto res = _set0.insert(x);
        assert(res.second);

        _set1.insert(res.first);
    }

    const auto& lookup0(Key0 x) { return _set0.lower_bound(x); }
    const auto& lookup1(Key1 x) { return *(_set1.lower_bound(x)); }
};
2
Vittorio Romeo 17 Maret 2017, 12:28

Tidak dengan std::set, seperti yang ditunjukkan oleh @Vittorio Romeo dalam jawabannya.

Ada struktur data boost yang dapat mencari oleh anggota yang tidak terkait, yang akan Anda definisikan seperti

struct foo {
    int x, y;
    foo(int x, int y) : x(x), y(y) {}
};

// helpers
struct x_tag {}; 
struct y_tag {};

boost::multi_index_container<
    foo,
    indexed_by<
        ordered_unique<tag<x_tag>, boost::multi_index::member<foo, int, &foo::x>>, // std::less<int> applied to foo::x
        ordered_unique<tag<y_tag>, boost::multi_index::member<foo, int, &foo::y>> // std::less<int> applied to foo::y
    >
> fooSet;

int an_x, an_y;
// lookup by x
fooSet.get<x_tag>().find(an_x);
fooSet.get<y_tag>().find(an_y);
1
Caleth 17 Maret 2017, 13:38