小编Chr*_* A.的帖子

有没有人知道不同实现的预期运行时间和最坏情况运行时间std::nth_element？我几乎每天都使用这个算法.

我对最近的Microsoft编译器附带的STL版本特别感兴趣,但有关此主题的任何信息都很有帮助.

请注意,这不是此问题的副本.我理解存在哪些算法,但我对哪些实现使用哪种算法感兴趣.

对于背景,有众所周知的算法可以做到这一点.一个是O(n)平均情况和O(n log n)最坏情况,一个是O(n)最坏情况但实际上缓慢(中位数的中位数).还要注意,有一些有趣的实现策略可以让我们在实践中获得最快的O(n)运行时间.该标准表明,这必须是更糟糕的O(n)平均时间.

这是C++类实现中一次又一次出现的问题.我很好奇人们的想法在这里.您更喜欢哪种代码？为什么？

class A
{
public:
    /* Constructors, Destructors, Public interface functions, etc. */ 
    void publicCall(void);

private:
    void f(void);

    CMyClass m_Member1;
};

同

void A::publicCall(void)
{
    f();
}

void A::f(void)
{
    // do some stuff populating  m_Member1
}

或替代方案:

class A
{
public:
    /* Constructors, Destructors, Public interface functions, etc. */ 
    void publicCall(void);

private:
    void f(CMyClass &x);

    CMyClass m_Member1;
};

同

void A::publicCall(void)
{
    f(m_Member1);
}

void A::f(CMyClass &x)
{
    // do some stuff to populate x, 
    // locally masking the …

我最近遇到的最有趣的C++问题如下:

我们确定(通过分析)我们的算法在MS Visual Studio 2005中的调试模式中花费了大量时间,具有以下类型的函数:

MyClass f(void)
{
      MyClass retval;
      // some computation to populate retval

      return retval;
}

正如你们大多数人可能知道的那样,这里的返回调用一个拷贝构造函数来传递一个副本,retval然后传递析构函数retval.(注意:原因释放模式非常快,因为返回值优化.但是,我们希望在调试时关闭它,以便我们可以介入并很好地查看调试器IDE中的内容.)

所以,我们的一个人提出了一个很酷的(如果有点缺陷)解决方案,这就是创建转换运算符:

MyClass::MyClass(MyClass *t)
{
      // construct "*this" by transferring the contents of *t to *this   
      // the code goes something like this
      this->m_dataPtr = t->m_dataPtr;  

      // then clear the pointer in *t so that its destruction still works
      // but becomes 'trivial'
      t->m_dataPtr = 0;
}

并将上述功能更改为:

MyClass f(void)
{ …