Реализация ориентированного на многопотоковое исполнение, универсального стека в C++ на Linux

Я бы добавил переменную условия, чтобы «попперс» мог ждать, не сжигая процессорное время.

// сложно, возвращает ссылку на последний элемент

Присваивание копирует последний элемент перед тем, как он выталкивается из вектора, так что все в порядке.

Как вы говорите, "наверх "бессмысленно. Вы можете получить размер вектора в любое время, когда захотите.

Вы должны всегда вызывать stack.empty () только с удерживаемой блокировкой, поскольку нет гарантии, что он будет выполнять атомарный доступ. Вы можете получить непоследовательный ответ, если вызовете его, когда другой поток находится в процессе обновления стека. Итак, ваша общедоступная функция IsEmpty должна принимать мьютекс, а это значит, что вы не хотите вызывать ее самостоятельно из другого места.

Но в любом случае IsEmpty не очень полезен в параллельном коде. Просто потому, что он ложен, когда вы вызываете его, не означает, что он все равно будет ложным через одну строку, когда вы будете Pop. Так что либо вы должны избавиться от него из общедоступного интерфейса, либо вы должны выставить блокировку, чтобы пользователи могли писать свои собственные атомарные операции. В этом случае у меня вообще не было бы никакой проверки потери значимости, кроме assert в режиме отладки. Но с другой стороны, я никогда не верил в глупых людей, которые доходят до режима выпуска, не прочитав документацию или не протестировав свой код.

[Edit: Как использовать RAII для блокировок

Когда люди говорят использовать RAII для блокировки, они не просто хотят убедиться, что мьютекс уничтожен. Они имеют в виду использовать его, чтобы убедиться, что мьютекс разблокирован. Дело в том, что если у вас есть код, который выглядит следующим образом:

lock();
doSomething();
unlock();

и doSomething () выдает исключение, вы не разблокируете мьютекс. Ой.

Итак, вот пример класса, вместе с его использованием:

class LockSession;
class Lock {
    friend class LockSession;
    public:
    Lock()        { pthread_mutex_init(&lock); }
    ~Lock()       { pthread_mutex_destroy(&lock); }

    private:
    void lock()   { pthread_mutex_lock(&lock); }
    void unlock() { pthread_mutex_unlock(&lock); }

    private:
    Lock(const Lock &);
    const Lock &operator=(const Lock &);

    private:
    pthread_mutex_t lock;
};

class LockSession {
    LockSession(Lock &l): lock(l) { lock.lock(); }
    ~LockSession()                { lock.unlock(); }
    private:
    LockSession(const LockSession &);
    LockSession &operator=(const LockSession &);

    private:
    Lock &lock;
};

Тогда где-нибудь в вашем коде будет блокировка, связанная с данными, которые вы хотите защитить, и он будет использовать его примерно так:

void doSomethingWithLock() {
    LockSession session(lock);
    doSomething();
}

или

void doSeveralThings() {
    int result = bigSlowComputation();  // no lock
    {
        LockSession s(lock);
        result = doSomething(result); // lock is held
    }
    doSomethingElse(result);     // no lock
}

Теперь не имеет значения, генерирует ли doSomething () исключение или нормально возвращает (ну, во втором примере doSomethingElse не произойдет при исключении, но я предполагаю это то, что не нужно делать в случае ошибки). В любом случае сеанс уничтожается, а его деструктор освобождает мьютекс. В частности, такие операции, как «push» в стеке, выделяют память и, следовательно, могут вызывать выбросы, и, следовательно, вам нужно справиться с этим.

RAII означает «получение ресурсов - это инициализация». В случае doSomethingWithLock () ресурс, который вы хотите получить, - это то, что вы хотите удерживать блокировку. Итак, вы пишете класс, который позволяет вам делать это путем инициализации объекта (LockSession). Когда объект разрушен, блокировка снимается. Таким образом, вы относитесь к «блокировке / разблокировке мьютекса» точно так же, как вы относитесь к «инициализации / деинициализации мьютекса», и таким же образом защищаете себя от утечки ресурсов.

Один немного раздражающий факт заключается в том, что этот код полностью сломанный и глючный, и вы должны быть уверены, что случайно не сделаете это, даже если для неосторожного взгляда это выглядит как правильный код:

void doSomethingWithLock() {
    LockSession(lock);
    doSomething();
}

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

Boost имеет шаблон класса scoped_lock , который выполняет то же, что и LockSession, и многое другое.]

Я бы сначала выбросил верх. Когда вам это не нужно, это просто пустая трата!

Маленький - красивый

Также, если вы хотите оптимизировать доступ к вектору: дублирующая обработка управляющей информации (здесь: длина стека) всегда подвержена ошибкам. Лучше надеяться, что этот вектор блестяще быстр (в большинстве случаев это STL), и поэтому empty () тоже.

Это не идиоматический C ++ и может не иметь никаких преимуществ, кроме новизны, рассматривали ли вы реализацию неизменяемого стека? Таким образом, он будет автоматически потокобезопасным.

Эрик Липперт выполнил реализацию C # . По общему признанию, код C ++ был бы более сложным.

Одна вещь, которую вы не рассмотрели, - это проблема отмены потока. STL ведет себя плохо, когда поток прерывается во время операции с контейнером stl. Вам нужно отключить отмену, когда вы работаете с вектором. Я узнал об этом на собственном горьком опыте. Это не весело, когда у вас тупик, и все потоки находятся в шаблонном stl-коде, и вы пытаетесь отладить, что именно произошло. Используйте pthread_setcancelstate, чтобы изменить состояние отмены потоков.

Нил, Onebyone:
Попытка использования RAII для блокировки мьютекса. Любые комментарии?

template<typename T> 
class MyStack
{
public:
//interface
bool Push(T elem);
bool Pop(T& elem);
bool IsEmpty();

//constructor
MyStack() {
//top = 0;
}

//destructor
~MyStack() {

}

private:
    class Locker {          //RAII
    public:
        Locker() {
            pthread_mutex_init(&lock);
        }
        ~Locker() {
            pthread_mutex_destroy(&lock);
        }
        void Lock() {
            pthread_mutex_lock(&lock);
        }
        void UnLock() {
            pthread_mutex_unlock(&lock);
        }
    private:
        pthread_mutex_t lock;
    };
Locker MyLock;
//int top;
stack<T> mystack;

bool MyStack::Push(T elem);
bool MyStack::PushElem(T elem);
bool MyStack::Pop(T& elem);
bool MyStack::PopElem(T& elem);
}; //end of MyStack

template<typename T>
bool MyStack<T>::Push(T elem)
{
    MyLock.Lock();
    PushElem(elem);
    MyLock.UnLock();
}

template<typename T>
bool MyStack<T>::Pop(T& elem)
{
    MyLock.Lock();
    PopElem(elem);
    MyLock.UnLock();
}