Здравствуйте, Дмитрий Наумов, Вы писали:

В смысле аналогично стеку. Типа Push/pop.

Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, BioUnit, Вы писали:

BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь.

J>Вот и воспользуйся очередью (std:deque)

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

Здравствуйте, BioUnit, Вы писали:

BU>Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.

кстати, о векторах. Для очереди не самый удачный выбор ввиду кривости операции извлечения из головы (точнее отсутсвия таковой операции). Поэтому ИМХО самый оптимальный вариант — std::queue + CRITICAL_SECTION

Здравствуйте, BioUnit, Вы писали:

BU>Вопрос не в том, чем воспользоваться, можно и списком и очередью, а в том, как синхронизировать доступ. В STL это ложиться на плечи программера.

В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)

Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)

Что то не понятно. А зачем в очереди лочить что либо кроме хвоста и головы?

template<class T> class CSafeQueue
{
    std::queue<T> myQueue;
    CRITICAL_SECTION cs;
public:    
    CSafeQueue(){InitializeCriticalSection(&cs);}
    CSafeQueue(){DeleteCriticalSection(&cs);}
    void Push_back(const T& elem){
                   EnterCriticalSection(&cs);
                   myQueue.push(elem);
                   LeaveCriticalSection(&cs);
    }
    void Pop_front(T& elem){
                   EnterCriticalSection(&cs);
                   elem = myQueue.front();
                   myQueue.pop();
                   LeaveCriticalSection(&cs);
    }
};

Ну или типа того... Зачем остальные элементы лочить?

Здравствуйте, small_cat, Вы писали:

ДН>>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)

SC>Что то не понятно. А зачем в очереди лочить что либо кроме хвоста и головы? <...>
SC>Ну или типа того... Зачем остальные элементы лочить?

Я писал про вектор, с вектором ваш номер не пройдет

Здравствуйте, BioUnit, Вы писали:

B> как синхронизировать доступ. В STL это ложиться на плечи программера

В любом случае должна присутствовать внешняя синхронизация. См., например,
http://rsdn.ru/forum/Message.aspx?mid=104040

Автор: Павел Кузнецов
Дата: 22.09.02

Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В общем вы правы, но... немного связаны эти два вопроса — синхронизация и что использовать. Список (std::list) синхронизовать проще, я уже писал что надо лочить тока 3 элемента при изменении. С тем же вектором придется лочить намного больше (например при удалении элемента из середины)

И голова, и хвост списка (std::list) связаны с самим объектом-контейнером.
Так что для запихивания-выпихивания придется лочить контейнер как таковой.

Лочить внутреннее устройство контейнера — дело неблагодарное (не переписывать же STL, тем более, что у каждого поставщика он устроен по-разному).

Другое дело, что время запихивания-выпихивания у std::list и std::deque порядка O(1), а у std::vector — до O(N).

---

Можно, однако, сделать так: отдать права на модификацию очереди только пишущему потоку.
Читающий поток только отмечает, какие элементы он прочел. А пишущий, помимо заталкивания в очередь, периодически очищает ее.
Это даст рост производительности, но усложнит систему.

Здравствуйте, Кодт, Вы писали:

К>Лочить внутреннее устройство контейнера — дело неблагодарное (не переписывать же STL, тем более, что у каждого поставщика он устроен по-разному).
Если очень важна производительность да и только в одном контейнере, то это вполне оправдно.

Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.

Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.

Либо делать свой контейнер с известной структурой.

      CONTAINER
BeforeHead  AfterTail
L=null R=H  L=T R=null

item_0
L=BeforeHead
R=item_1

item_1
L=item_0
R=item_2

...

item_N
L=item_N1
R=AfterTail

Здравствуйте, Кодт, Вы писали:

К>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.

Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?

Здравствуйте, Дмитрий Наумов, Вы писали:

К>>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.

ДН>Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?

Но мы же говорили про очередь... Зачем работать с серединой списка?

Здравствуйте, Кодт, Вы писали:

TMH>Закрывать работу со списком мютексом надо ОБЯЗАТЕЛЬНО. Во избежание...

skip

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

Если все же подразумевалось использование списка (std::list) для организации очереди без доступа к середине, то я извиняюсь за то что не врубился и полез в тему.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Дмитрий Наумов, Вы писали:

К>>>Теперь осталось только вспомнить, что у двусвязного списка соседом и головы, и хвоста является фиктивный узел, принадлежащий контейнеру... А в реализации STL от Dinkumware — это один и тот же узел. И поймем, что лочить придется все одним махом.

ДН>>Почему? ИМХО, не во всех случаях. Если вставляет/удаляется элемент из/в середину то можно обойтись моим способом. Если же этот финт проделываем с первым/последним элементом то лочим (для первого элемента) соседа справа, сам первый элемент и последний элемент... Разве я не прав?

А что если вбить в начало списка фиктивный элемент, таким образом можно будет выбирать из псевдоголовы (где псевдоголова будет след. за фиктивным элементом) и добавлять в конец без взаимных локов, то есть одновременно. А?

Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>А что если вбить в начало списка фиктивный элемент, таким образом можно будет выбирать из псевдоголовы (где псевдоголова будет след. за фиктивным элементом) и добавлять в конец без взаимных локов, то есть одновременно. А?

Прикольный способ!
Однако остается возможность того, что следующий за (псевдо)головой элемент — это (псевдо)хвост.
Поэтому, либо у каждого элемента будет свой собственный мутекс, либо опять придется лочить всю систему.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>>А что если вбить в начало списка фиктивный элемент, таким образом можно будет выбирать из псевдоголовы (где псевдоголова будет след. за фиктивным элементом) и добавлять в конец без взаимных локов, то есть одновременно. А?

К>Прикольный способ!
К>Однако остается возможность того, что следующий за (псевдо)головой элемент — это (псевдо)хвост.
К>Поэтому, либо у каждого элемента будет свой собственный мутекс, либо опять придется лочить всю систему.

К>

Я бы не так сказал, весь список будет залочен (нужно лочить) в случае если очередь пуста, то есть след. элемент за псевдоголовой это хвост. В остальных же случаях будет лучше. ИМХО, это прикольней чем просто напрямую лочить одним мутексом( или whatever you choose) весь список.

Здравствуйте, BioUnit, Вы писали:

BU>Есть некоторый vector. Один поток добавляет элементы в его конец, а другой — выбирает из головы, т.е. своеобразная очередь. Понимаю, что вариантов синхронзации может быть множество, но среди этого разнообразия хотелось бы получить самый оптимальный, ведь задача то тривиальная.

А почему бы не воспользоватся очередью сообщений из Windows да и вдругих есть аналоги. Собственно проблема синхронизации там уже решена. Или пайпом или еще чем-нибудь. Способов достаточно. Или нужна именно мультиплатформенности и именно STL?

Здравствуйте, BioUnit, Вы писали:

BU>Да, действительно, список лучше.
BU>Но вот вопрос: когда в очереди одно задание, один поток начинает его выбирать, а другой поток в этот момент добавляет очередное задание. Не произойдет ли чего-нибудь непредвиденного?

Обязательно произойдет

Вообще в стандарте ничего не написано по поводу многопоточности STL
так что она НЕ многопоточная.

Надо смотреть конкретные реализации.
Но вот в STL Port например есть некая документация по этому поводу.
Заявляется что сколько угодно потоков могут читать из контейнера,
(использовать константные функции), но когда начинаешь его изменять
надо синхрогизировать.

Остальные реализации возможно так же возможно хуже.

Здравствуйте, Дмитрий Наумов, Вы писали:

ДН>В случае списка, во избежание падения перфоманса, можно лочить только три элемента — тот который удаляется/вставляется и два его соседа. К остальным элементам доступ на чтение в это время можно разрешать.

как это предполагается реализовать технически?