Welche container zum speichern von eindeutigen Werten?

Ich werde meinen Hals auf den block hier und vorschlagen, dass die Vektor-route ist wohl am effizientesten, wenn die Größe 100 und die Objekte, die gespeichert werden Integrale Werte. Der einfache Grund HIERFÜR ist, dass set und unordered_set Speicher für jedes insert in der Erwägung, dass der Vektor braucht nicht mehr als einmal.

Können Sie erhöhen suchen performance dramatisch halten Sie die vector bestellt, da dann alle durchsucht werden können, die binäre Suche und daher vollständig in log2N Zeit.

Der Nachteil ist, dass die Einsätze nehmen einen winzigen Bruchteil mehr durch die Erinnerung bewegt, aber es klingt so, als ob es viel mehr sucht als Beilagen, und bewegen (Durchschnitt) 50 zusammenhängenden Speicher Worten ist eine fast sofortige operation.

Letzte Wort:
Schreiben Sie die richtige Logik. Sorgen über die performance, wenn sich die Benutzer beschweren.

BEARBEITEN:
Denn ich konnte mir nicht helfen, hier ist eine einigermaßen vollständige Umsetzung:

template<typename T>
struct vector_set
{
    using vec_type = std::vector<T>;
    using const_iterator = typename vec_type::const_iterator;
    using iterator = typename vec_type::iterator;

    vector_set(size_t max_size)
    : _max_size { max_size }
    {
        _v.reserve(_max_size);
    }

    ///@returns: pair of iterator, bool
    ///If the value has been inserted, the bool will be true
    ///the iterator will point to the value, or end if it wasn't
    ///inserted due to space exhaustion
    auto insert(const T& elem)
    -> std::pair<iterator, bool>
    {
        if (_v.size() < _max_size) {
            auto it = std::lower_bound(_v.begin(), _v.end(), elem);
            if (_v.end() == it || *it != elem) {
                return make_pair(_v.insert(it, elem), true);
            }
            return make_pair(it, false);
        }
        else {
            return make_pair(_v.end(), false);
        }
    }

    auto find(const T& elem) const
    -> const_iterator
    {
        auto vend = _v.end();
        auto it = std::lower_bound(_v.begin(), vend, elem);
        if (it != vend && *it != elem)
            it = vend;
        return it;
    }

    bool contains(const T& elem) const {
        return find(elem) != _v.end();
    }

    const_iterator begin() const {
        return _v.begin();
    }

    const_iterator end() const {
        return _v.end();
    }


private:
    vec_type _v;
    size_t _max_size;
};

using namespace std;


BOOST_AUTO_TEST_CASE(play_unique_vector)
{
    vector_set<int> v(100);

    for (size_t i = 0 ; i < 1000000 ; ++i) {
        v.insert(int(random() % 200));
    }

    cout << "unique integers:" << endl;
    copy(begin(v), end(v), ostream_iterator<int>(cout, ","));
    cout << endl;

    cout << "contains 100: " << v.contains(100) << endl;
    cout << "contains 101: " << v.contains(101) << endl;
    cout << "contains 102: " << v.contains(102) << endl;
    cout << "contains 103: " << v.contains(103) << endl;
}

InformationsquelleAutor Richard Hodges

Als Sie sagten, Sie haben viele Einfüge-und nur eine-traversal, würde ich empfehlen ein Vektor, und drücken Sie auf die Elemente, unabhängig davon, ob Sie sind einzigartig in dem Vektor. Dies geschieht in O(1).

Nur, wenn Sie müssen gehen Sie durch den Vektor, dann Sortieren Sie und entfernen Sie doppelte Elemente. Ich glaube, dass dies getan werden kann, in O(n) wie Sie sind begrenzt Ganzzahlen.

BEARBEITEN: Sortieren in linearer Zeit durch zählen, Sortieren präsentiert in dieses video. Wenn nicht machbar, dann sind Sie wieder zu O(n lg(n)).

Haben Sie sehr wenig cache-miss, weil die Kontiguität des Vektors im Speicher, und nur sehr wenige Zuweisungen (vor allem, wenn Sie reservieren, genügend Arbeitsspeicher in den Vektor).

InformationsquelleAutor qdii