Атомно std :: vector :: push_back () и возвращаемый индекс

Question

Мне нужно создать функцию, которая добавляет значение к вектору и возвращает индекс только что добавленного значения.

Пример:

int append(std::vector<int>& numbers, int number){
  int retval = numbers.size();
  // what if some other thread calls push_back(number) in between these calls?
  numbers.push_back(number);
  return retval;
}

Я хотел бы сделать это атомарно, чтобы возвращаемый индекс всегда был корректным, даже если к вектору могут добавляться значения нескольких потоков. Было бы легко, если бы push_back вернул индекс только что добавленного элемента. Как я могу гарантировать, что возвращается правильный индекс?

Answer 1

std::vector не имеет встроенной поддержки потоков.Вы можете использовать boost::mutex для его расширения:

int append(std::vector<int>& numbers, int number){
  boost::mutex::scoped_lock slock( my_lock );
  int retval = numbers.size();
  numbers.push_back(number);
  return retval;
}

Таким способом вам необходимо защитить любую операцию чтения / записи.Другой способ - создать класс-оболочку для std::vector, который расширит его поддержкой потоков.Проверьте этот вопрос для деталей.

Answer 2

Контейнеры

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

Answer 3

В Visual Studio 2010 для этого можно использовать concurrent_vector , он предлагает синхронизированную функциональность роста. В этом разделе перечислены все одновременные контейнеры.

Обратите внимание, что они также доступны в TBB Intel с идентичным синтаксисом + семантикой и, как таковые, доступны кроссплатформенными.

Answer 4

Самое надежное решение - заблокировать весь вектор для всех таких операций (что означает управление каждой операцией из любого места в коде, что действительно означает создание синхронизированного вектора).

Может быть, что-то простое, как это будет делать для ваших целей:

int append(std::vector<int>& numbers, int number){
  int retval = numbers.size();
  // what if some other thread calls push_back(number) in between these calls?
  numbers.push_back(number);
  int newSize = numbers.size();
  //this bit is as a short-cut in common, easy, cases
  if(newSize = retval + 1) //no need for further complication
    return retval;
  while(++retval < newSize)
    if(numbers[retval] == number)
      return retval;
  //If we get this far, numbers have been deleted, not added. More discussion below.
}

Одна вещь об этом заключается в том, что если потоки выдвигают 3, 3, 3, 3, то возвращаемый индекс будет неправильным, хотя все равно будет индексом до 3. Это нормально или нет, зависит от ваших целей.

Другое - это то, что если вектор тем временем всплывает или иным образом укорачивается, то в лучшем случае мы добираемся до точки, в которой я просто помещаю комментарий в приведенном выше коде, в худшем случае - ошибки (так как они появляются снова после того, как мы получаем newSize и затем доступ к [retval] становится недействительным). Вам нужно подумать, может ли это случиться (возможно, вы знаете из остальной части кода, что этого никогда не произойдет) и что делать, если это произойдет.

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

Answer 5

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