Архитектурный вопрос C ++ / STL об использовании итератора для удаления списка O (1) внешними системами

Question

Это довольно простой архитектурный вопрос, однако он мучает меня целую вечность.

Весь смысл использования списка, для меня в любом случае, заключается в том, что это O (1) вставка / удаление.Единственный способ удалить O (1) - это создать итератор для erase ().Единственный способ получить итератор - удержать его в исходной операции insert () или найти его путем итерации.

Итак, что обойти;Итератор или указатель?

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

Вот типичный сокращенный пример:

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

Тогда у нас есть FooManger, который содержит список shared_ptr, FooPtr.Менеджер отвечает за время жизни объекта после его передачи.

Теперь, что вернуть из addFoo ()?Если я верну FooPtr, то я никогда не смогу удалить его из списка в O (1), потому что мне придется найти его в списке.Если я возвращаю std :: list :: iterator, FooPtrListIterator, то везде, где мне нужно удалить FooPtr, я могу, просто разыменовав итератор.

В этом примере у меня есть надуманный пример Foo, который можетубить себя при некоторых обстоятельствах, Foo :: killWhenConditionMet ().

Представьте себе некоторый Foo, у которого таймер сбрасывается до 0, после чего ему необходимо попросить менеджера удалить себя.Проблема в том, что «this» - это пустой Foo *, поэтому единственный способ удалить себя - это вызвать FooManager :: eraseFoo () с необработанным указателем.Теперь менеджеру приходится искать указатель объекта, чтобы получить итератор, чтобы его можно было удалить из списка и уничтожить.

Единственный способ сохранить итератор в объекте.то есть Foo имеет FooPtrListIterator в качестве переменной-члена.

struct Foo;

typedef boost::shared_ptr<Foo> FooPtr;
typedef std::list<FooPtr> FooPtrList;
typedef FooPtrList::iterator FooPtrListIterator;

struct FooManager
{
    FooPtrList l;

    FooPtrListIterator addFoo(Foo *foo) {
        return l.insert(l.begin(), FooPtr(foo));
    }
    void eraseFoo(FooPtrListIterator foo) {
        l.erase(foo);
    }
    void eraseFoo(Foo *foo) {
        for (FooPtrListIterator it=l.begin(), ite=l.end(); it!=ite; ++it) {
            if ((*it).get()==foo){
                eraseFoo(it);
                return;
            }
        }
        assert("foo not found!");
    }
};

FooManager g_fm;

struct Foo
{
    int _v;

    Foo(int v):_v(v) {
    }
    ~Foo() {
        printf("~Foo %d\n", _v);
    }
    void print() {
        printf("%d\n", _v);
    }
    void killWhenConditionMet() {
        // Do something that will eventually kill this object, like a timer
        g_fm.eraseFoo(this);
    }
};

void printList(FooPtrList &l)
{
    printf("-\n");
    for (FooPtrListIterator it=l.begin(), ite=l.end(); it!=ite; ++it) {
        (*it)->print();
    }
}   

void test2()
{
    FooPtrListIterator it1=g_fm.addFoo(new Foo(1));
    printList(g_fm.l);
    FooPtrListIterator it2=g_fm.addFoo(new Foo(2));
    printList(g_fm.l);
    FooPtrListIterator it3=g_fm.addFoo(new Foo(3));
    printList(g_fm.l);

    (*it2)->killWhenConditionMet();

    printList(g_fm.l);
}

Итак, у меня есть следующие вопросы: 1. Если объект должен удалить себя, или какая-либо другая система удаляет его, в O (1)я должен хранить итератор для объекта, внутри объекта?Если да, есть ли какие-либо ошибки, связанные с тем, что итераторы становятся недействительными из-за других итераций контейнера?

Есть ли просто другой способ сделать это?

В качестве дополнительного вопроса, кто-нибудь знает, почему и из-за операций контейнера push * stl не возвращаютсярезультирующий итератор, означающий, что нужно прибегнуть к 'insert *'.

Пожалуйста, никаких ответов, которые говорят "не предварительно оптимизировать", это сводит меня с ума.;) Это архитектурный вопрос.

Answer 1

Стандарт

C ++ в разделе [list.modifiers] говорит, что любая операция вставки списка «не влияет на достоверность итераторов и ссылок», а любая операция удаления «делает недействительными только итераторы и ссылки на стертые элементы ". Поэтому хранение итераторов будет безопасным .

Хранение итераторов внутри объектов также кажется вменяемым . Особенно, если вы не называете их итераторами, а просто называете их как FooManagerHandlers, которые обрабатываются функцией удаления непрозрачным способом. Действительно, вы не храните «итераторы», вы храните « представителей » объектов в организованной структуре. Эти представители используются для определения положения объекта внутри этой структуры. Это отдельная, довольно высокоуровневая концепция, и в ее реализации нет ничего нелогичного.

Однако смысл использования списков заключается не только в O (1) вставке / удалении, но также в сохранении элементов в порядке . Если вам не нужен какой-либо порядок, вы, вероятно, найдете хеш-таблицы более полезными.

Answer 2

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

Причина, по которой push * не возвращает итератор, заключается в том, что он является обратным к pop *, что позволяет вам рассматривать ваш контейнер как стек, очередь или очередь.