在C++中按值排序的元素中的元素的序数位置是什么算法或代码?

if (traverse to left subtree)
  index = index_on_previous_stage;
if (traverse to right subtree)
  index = index_on_previous_stage + left_subtree_size + 1;
if (found)
  return index + left_subtree_size;

这将需要O(logn)时间,就像插入一样。

我想你可以 std::set 在这里它提供排序行为,还返回迭代器插入值的位置。从这个位置可以得到索引。例如:

std::set<int> s;
std::pair<std::set<int>::iterator, bool> aPair = s.insert(5);
size_t index = std::distance(s.begin(), aPair.first) ;

请注意,std::list insert(it,value)成员函数将迭代器返回给新插入的元素。也许能帮上忙?

近似 您可以根据已有的值范围来估计这一点-您只需在固定时间内读取集合中的第一个和最后一个值,如下所示:

multiset<int> values;

values.insert(value);
int ordinal = values.size() * (value - values.front()) /
                              (values.back()-values.front());

class SortedValues : public multiset<int>
{
public:
    SortedValues() : sum(0), sum2(0) {}

    int insert(int value)
    {
        // Insert the value and update the running totals
        multiset<int>::insert(value);
        sum += value;
        sum2 += value*value;

        // Calculate the mean and deviation.
        const float mean = float(sum) / size();
        const float deviation = sqrt(mean*mean - float(sum2)/size());

        // This function is left as an exercise for the reader.
        return size() * EstimatePercentile(value, mean, deviation);
    }

private:
    int sum;
    int sum2;
};

如果需要序号位置,则需要一个对 RandomAccessContainer 概念。。。基本上是 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::下界 std::上界 和 std::等_范围 有一个O(1)复杂度,所以那里的一切都非常有效。。。

编辑 :如评论中强调的>&燃气轮机;插入实际上是O(n),因为必须移动元素。

简单地将元素附加到向量,排序,然后使用二进制搜索来查找序号位置可能更好,但这取决于您真正想要实现的目标

如果您拥有该项的迭代器(如dtrosset所建议的),则可以使用 std::distance

如果有一个迭代器要查找其索引,请使用std::distance,

正如其他人所说,这一点为什么有用还不是很明显?