Atomically std::vector::push_back() and return index

Question

I need to create a function which appends a value to a vector and returns the index of the value that was just appended.

Example:

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;
}

I would like to do this atomically so that the returned index is always correct even when there may be multiple threads appending values to the vector. It would have been easy if push_back returned the index of the item just added. How can I guarantee that the correct index is returned?

Answer 1

STL containers are not thread-safe (even the call to push_back() alone), you'll have to solve this problem on your own - use some suitable synchronization primitives outside STL.

Answer 2

std::vector has no built in thread support. You could use boost::mutex to extend it:

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;
}

You need to protect any read/write operation in such way. Another way is to create wrapper class for std::vector that will extend it with thread support. Check this question for details.

Answer 3

You need to use a mutex to guarantee that the correct index is returned

Answer 4

The strongest-guarantee solution is to lock the entire vector on all such operations (which means controlling every operation from everywhere in the code, which really means creating a synchronised vector).

It may be that something as simple as this will do for your purposes:

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.
}

One thing about this is that if threads push 3, 3, 3, 3 then the index returned will be wrong, though it will still be an index to a 3. Whether that's okay or not depends on your purposes.

Another is that if the vector is popped or otherwise shortened in the meantime, then at best we get to the point where I just put a comment in the code above, at worse it errors (as they pop again after we obtain newSize, and then accessing [retval] becomes invalid). You need to consider if this case can happen (maybe you know from the rest of the code that it never will) and what to do if it does.

If the limitations of this are too great for your use case, then producing a fully synchronised vector is the best I can think of I'm afraid.

Answer 5

In Visual Studio 2010, you can use a concurrent_vector for this in , it offers synchronized grow functionality . This topic lists each of the concurrent containers.

Note that these are also available in Intel's TBB with identical syntax + semantics and as such are available cross platform.