LINUX.ORG.RU

Существует ли такой контейнер?

 


0

4

Контейнер хранит уникальные объекты (указатели на объекты), но при этом они должны быть отсортированны по определённому критерию. Если критерии для двух объектов равны, то добавленный позднее объект должен находится последним.

Я завелосипедил свой класс, но, может быть, есть что получше (т.к. здесь, например, при изменении значения по итератеру поломается порядок).

template <typename T, class Comp>
class ordered_set
{
public:
    ordered_set()
    {
    }

    template <typename _T>
    void insert(_T&& elem)
    {
        erase(elem);
        Comp comp;
        auto it = std::find_if(m_elems.begin(), m_elems.end(),
                               [&](const auto& e) { return comp(elem, e); });
        m_elems.insert(it, std::forward<_T>(elem));
    }

    template <typename ...Args>
    void emplace(Args&&... args)
    {
        insert(T{std::forward<Args>(args)...});
    }

    auto erase(typename std::deque<T>::const_iterator it)
    {
        return m_elems.erase(it);
    }

    size_t erase(const T& elem)
    {
        size_t old_size = size();
        m_elems.erase(std::remove_if(m_elems.begin(), m_elems.end(),
                                     [&](const auto& e) { return e == elem; }),
                      m_elems.end());
        return size() - old_size;
    }

    auto find(const T& elem)
    {
        return std::find_if(m_elems.begin(), m_elems.end(),
                            [&](const auto& e) { return e == elem; });
    }

    void clear()
    {
        m_elems.clear();
    }

    auto size() const
    {
        return m_elems.size();
    }

    auto begin()
    {
        return m_elems.begin();
    }

    auto end()
    {
        return m_elems.end();
    }

    auto elements() const
    {
        return m_elems;
    }

private:
    std::deque<T> m_elems;
};

например, при изменении значения по итератеру поломается порядок

Для этого достаточно отдавать только константные итераторы в begin/end.

E ★★★
()
Ответ на: комментарий от E

Не подходит, т.к. конейнер может хранить объекты с равными критериями, а set — нет.

В случае set'а к объектам необходимо добавить какое-то поле типа id, чего хотелось бы избежать.

anatoly
() автор топика

Я из твоего описания совершенно не понял, какой интерфейс должен предоставлять твой контейнер, с какой скоростью различные операции должны производиться, и так далее.

hlebushek ★★
()
Ответ на: комментарий от anatoly

Ты в ОПе пишешь, что значения у тебя уникальные, а теперь говоришь, что объекты могут быть с равными критериями. Как определяется уникальность?

E ★★★
()
Ответ на: комментарий от anatoly

Кажется, я понял, чего ты хочешь.

Добавлять id к объектам не нужно. Можно сделать структуру-обёртку на твоим объектом с дополнительным полем time_t, и конструктор преобразования из объекта, который будет устанавливать текущее время (читай: время добавления). Компаратор пусть сравнивает эти структуры по твоему критерию, а если они равны - по времени создания.

E ★★★
()
Ответ на: комментарий от E

Значения уникальные — поскольку указатели. Но объекты по указателям могут быть равными.

anatoly
() автор топика
Ответ на: комментарий от mashina

Да, вроде бы оно. Только насчёт того, есть ли там гарантии того, что добавленный позднее элемент будет последним, пока не понял.

anatoly
() автор топика
Ответ на: комментарий от E

time_t не подходит, поскольку за секунду может быть создано более, чем один объект.

anatoly
() автор топика

В общем только что понял, что и решение из верхнего поста тоже не подходит, поскольку объекты, указатели на которые хранит контейнер, являются перемещаемыми (поддерживают move-семантику). В момент перемещения они удаляются из контейнера и добавляются заново. И чтобы корректно хранить порядок там в любом случае нужно, чтобы у объектов было дополнительное поле id. А если есть поле id, то и обычного set'а будет достаточно.

anatoly
() автор топика
Последнее исправление: anatoly (всего исправлений: 1)
Ответ на: комментарий от anatoly

Есть:

23.2.4/4: Associative containers
An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. The set and map classes support unique keys; the multiset and multimap classes support equivalent keys. For multiset and multimap, insert, emplace, and erase preserve the relative ordering of equivalent elements.

Table 102 – Associative container requirements
a_eq.insert(t)
Requires: If t is a non-const rvalue expression, value_type shall be MoveInsertable into X; otherwise, value_type shall be CopyInsertable into X.
Effects: Inserts t and returns the iterator pointing to the newly inserted element. If a range containing elements equivalent to t exists in a_eq, t is inserted at the end of that range.

ilammy ★★★
()
Ответ на: комментарий от anatoly

Не подходит, т.к. конейнер может хранить объекты с равными критериями, а set — нет.

На самом деле достаточно задать компаратор less_equal.

Но, лучше использовать таки multiset

pon4ik ★★★★★
()
Последнее исправление: pon4ik (всего исправлений: 2)
9 ноября 2017 г.
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.