Если вам нужна порядковая позиция, вам нужен контейнер, который моделирует концепцию RandomAccessContainer ... в основном, std::vector.
Операции сортировки на std::vector относительно быстрые, и вы можете добраться до желаемой позиции, используя std::lower_bound или std::upper_bound, вы можете самостоятельно решить, хотите ли вы использовать несколько значений одновременно, чтобы получить все равные хорошим способом является использование std::equal_range, которое в основном дает тот же результат, что и применение границ lower и upper, но с большей сложностью.
Теперь, для порядкового положения, большие новости в том, что std::distance как сложность O (1) на моделях RandomAccessIterator.
typedef std::vector<int> ints_t;
typedef ints_t::iterator iterator;
ints_t myInts;
for (iterator it = another.begin(), end = another.end(); it != end; ++it)
{
int myValue = *it;
iterator search = std::lower_bound(myInts.begin(), myInts.end(), myValue);
myInts.insert(search, myValue);
std::cout << "Inserted " << myValue << " at "
<< std::distance(myInts.begin(), search) << "\n";
// Not necessary to flush there, that would slow things down
}
// Find all values equal to 50
std::pair<iterator,iterator> myPair =
std::equal_range(myInts.begin(), myInts.end(), 50);
std::cout << "There are " << std::distance(myPair.first,myPair.second)
<< " values '50' in the vector, starting at index "
<< std::distance(myInts.begin(), myPair.first) << std::endl;
Легко, не правда ли?
std::lower_bound, std::upper_bound и std::equal_range имеют сложность O (log (n)), а std::distance имеет сложность O (1), поэтому все там достаточно эффективно ...
РЕДАКТИРОВАТЬ : как подчеркнуто в комментариях >> вставка на самом деле O (n), так как вы должны перемещать элементы вокруг.