如何重载 std::swap()

How to overload std::swap()

提问人:Adam 提问时间:8/15/2008 最后编辑:sbiAdam 更新时间:10/12/2021 访问量:38026

问:

std::swap()在排序甚至赋值期间被许多 std 容器(例如 和 )使用。std::liststd::vector

但是 std 的实现非常通用,并且对于自定义类型来说效率相当低。swap()

因此,可以通过重载自定义类型特定的实现来获得效率。但是,您如何实现它,以便 std 容器使用它呢?std::swap()

C++ 性能 优化 STL C++-常见问题解答

评论

0赞 Andrew Keeton 11/30/2018
“可交换”页面移至 en.cppreference.com/w/cpp/named_req/Swappable

答:

56赞 Wilka 8/15/2008 #1

不允许(根据 C++ 标准)重载 std::swap,但明确允许将自己的类型的模板专用化添加到 std 命名空间。例如

namespace std
{
    template<>
    void swap(my_type& lhs, my_type& rhs)
    {
       // ... blah
    }
}

然后,STD 容器(以及其他任何地方)中的用法将选择您的专业化,而不是一般专业化。

另请注意,提供 swap 的基类实现对于派生类型来说还不够好。例如,如果您有

class Base
{
    // ... stuff ...
}
class Derived : public Base
{
    // ... stuff ...
}

namespace std
{
    template<>
    void swap(Base& lha, Base& rhs)
    {
       // ...
    }
}

这适用于基类,但如果您尝试交换两个派生对象,它将使用 std 中的泛型版本,因为模板化的交换是完全匹配的(并且它避免了仅交换派生对象的“基”部分的问题)。

注意:我已经更新了这个,以删除我上一个答案中的错误位。哎呀!(感谢 Puetzk 和 j_random_hacker 指出)

评论

14赞 Howard Hinnant 2/23/2011
投了反对票,因为自定义交换的正确方法是在你自己的命名空间中这样做(正如 Dave Abrahams 在另一个答案中指出的那样)。
0赞 Kos 7/28/2011
是否禁止重载(或其他任何内容),但在命名空间之外?std::swapstd::swap
16赞 voltrevo 12/8/2011
@HowardHinnant,戴夫·亚伯拉罕斯:我不同意。你根据什么声称你的替代方案是“正确”的方式?正如 puetzk 从标准中引用的那样,这是特别允许的。虽然我是这个问题的新手,但我真的不喜欢你提倡的方法,因为如果我定义 Foo 并以这种方式交换,使用我的代码的其他人可能会在 Foo 上使用 std::swap(a, b) 而不是 swap(a, b),它默默地使用低效的默认版本。
5赞 Howard Hinnant 12/9/2011
@Mozza314:评论区的空间和格式限制不允许我完全回复您。请参阅我添加的标题为“注意Mozza314”的答案。
1赞 codeshot 11/6/2016
@HowardHinnant,我认为这种技术也很容易违反单一定义规则,这是对的吗?如果翻译单元包含<算法>和类 Base 的前向声明;而另一个包含上面的标头,那么你有两个不同的 std::swap<Base> 实例。我记得这在符合标准的程序中是被禁止的,但使用这种技术意味着你必须成功地阻止你的类的用户编写一个正向声明 - 他们必须以某种方式被迫总是包含你的标头以实现他们的目标。事实证明,大规模实现这是不切实际的。
31赞 puetzk 9/21/2008 #2

虽然通常不应该向 std:: 命名空间添加内容是正确的,但明确允许为用户定义类型添加模板专用化。重载函数不是。这是一个微妙的区别:-)

17.4.3.1/1 C++ 程序添加声明或定义是未定义的 除非另有说明,否则 STD 命名空间或命名空间 std 的命名空间 指定。程序可以为任何 标准库模板到命名空间 std。这样的专业化 (完整或部分)标准库导致 undefined 行为,除非声明依赖于用户定义的名称 外部链接,除非模板专业化满足 原始模板的标准库要求。

std::swap 的专用化如下所示:

namespace std
{
    template<>
    void swap(myspace::mytype& a, myspace::mytype& b) { ... }
}

如果没有模板<>位,它将是未定义的重载,而不是允许的专用化。@Wilka建议的更改默认命名空间的方法可能适用于用户代码(由于 Koenig 查找更喜欢无命名空间版本),但不能保证,事实上也不应该这样做(STL 实现应该使用完全限定的 std::swap)。

comp.lang.c++.moderated 上有一个线程,对这个话题进行了长时间的讨论。不过,其中大部分是关于部分专业化(目前没有好的方法可以做到)。

评论

7赞 Dave Abrahams 2/25/2011
为此(或任何内容)使用函数模板专用化是错误的一个原因:它与重载的交互方式很糟糕,其中有许多用于交换。例如,如果将常规 std::swap 专用化为 std::vector<mytype>&,则不会选择您的专用化而不是标准的特定于矢量的交换,因为在重载解决期间不会考虑专用化。
4赞 jww 9/6/2011
这也是Meyers在Effective C++ 3ed(第25项,第106-112页)中的建议。
2赞 Davis Herring 3/13/2018
@DaveAbrahams:如果专用化(没有显式模板参数),则部分排序将导致它成为版本的专用化,并且将使用它vector
1赞 Dave Abrahams 3/15/2018
@DavisHerring实际上,不,当你这样做时,部分排序没有任何作用。问题不在于你根本不能调用它;这是在存在明显不太具体的交换重载的情况下发生的事情:wandbox.org/permlink/nck8BkG0WPlRtavV
2赞 Davis Herring 3/16/2018
@DaveAbrahams:部分排序是在显式专用化匹配多个函数模板时选择要专用化的函数模板。您添加的重载比 的重载更专用,因此它会捕获调用,并且与后者的专用化无关。我不确定这是一个实际问题(但我也不是说这是一个好主意!::swapstd::swapvector
152赞 Dave Abrahams 4/22/2010 #3

重载实现(又名专用化)的正确方法是将其编写在与要交换的内容相同的命名空间中,以便可以通过参数相关查找 (ADL) 找到它。一件特别容易做的事情是:std::swap

class X
{
    // ...
    friend void swap(X& a, X& b)
    {
        using std::swap; // bring in swap for built-in types

        swap(a.base1, b.base1);
        swap(a.base2, b.base2);
        // ...
        swap(a.member1, b.member1);
        swap(a.member2, b.member2);
        // ...
    }
};

评论

12赞 Dave Abrahams 6/1/2010
在 C++2003 中,它充其量是被低估的。大多数实现确实使用 ADL 来查找交换,但不,它不是强制的,所以你不能指望它。您可以将 std::swap 专门用于特定的具体类型,如 OP 所示;只是不要指望这种专业化被使用,例如用于该类型的派生类。
18赞 Howard Hinnant 2/23/2011
我会惊讶地发现实现仍然没有使用 ADL 来查找正确的交换。这是委员会的一个问题。如果实现不使用 ADL 查找交换,请提交 bug 报告。
5赞 JoeG 12/8/2011
@Mozza314:视情况而定。使用 ADL 交换元素的 A 不符合 C++03,但符合 C++11。另外,为什么 -1 是基于客户端可能使用非惯用代码这一事实的答案?std::sort
5赞 Dave Abrahams 7/25/2013
@curiousguy:如果阅读标准只是阅读标准的简单问题,那你是对的:-)。不幸的是,作者的意图很重要。因此,如果最初的意图是可以或应该使用 ADL,那么它就没有被低估了。如果不是,那么它只是 C++0x 的一个普通的旧中断性更改,这就是为什么我写“充其量”未指定的原因。
5赞 Paolo M 11/11/2015
@curiousguy 是的,他确实有消息来源!他就是戴夫·亚伯拉罕斯
80赞 Howard Hinnant 12/9/2011 #4

注意 Mozza314

这是对泛型调用效果的模拟,并让用户在命名空间 std 中提供他们的交换。由于这是一个实验,因此此模拟使用 .std::algorithmstd::swapnamespace expnamespace std

// simulate <algorithm>

#include <cstdio>

namespace exp
{

    template <class T>
    void
    swap(T& x, T& y)
    {
        printf("generic exp::swap\n");
        T tmp = x;
        x = y;
        y = tmp;
    }

    template <class T>
    void algorithm(T* begin, T* end)
    {
        if (end-begin >= 2)
            exp::swap(begin[0], begin[1]);
    }

}

// simulate user code which includes <algorithm>

struct A
{
};

namespace exp
{
    void swap(A&, A&)
    {
        printf("exp::swap(A, A)\n");
    }

}

// exercise simulation

int main()
{
    A a[2];
    exp::algorithm(a, a+2);
}

对我来说,这是打印出来的:

generic exp::swap

如果编译器打印出不同内容,则它没有正确实现模板的“两阶段查找”。

如果你的编译器符合(C++98/03/11中的任何一个),那么它将给出与我显示的相同的输出。在那种情况下,你所担心的会发生的事情,确实发生了。把你放到命名空间()并没有阻止它发生。swapstdexp

Dave和我都是委员会成员,并且已经在标准的这一领域工作了十年(并且并不总是彼此一致)。但这个问题已经解决了很长时间,我们都同意它是如何解决的。无视戴夫在这方面的专家意见/答案,后果自负。

这个问题是在 C++98 发布后曝光的。大约从2001年开始,Dave和我开始在这个领域工作。这是现代解决方案:

// simulate <algorithm>

#include <cstdio>

namespace exp
{

    template <class T>
    void
    swap(T& x, T& y)
    {
        printf("generic exp::swap\n");
        T tmp = x;
        x = y;
        y = tmp;
    }

    template <class T>
    void algorithm(T* begin, T* end)
    {
        if (end-begin >= 2)
            swap(begin[0], begin[1]);
    }

}

// simulate user code which includes <algorithm>

struct A
{
};

void swap(A&, A&)
{
    printf("swap(A, A)\n");
}

// exercise simulation

int main()
{
    A a[2];
    exp::algorithm(a, a+2);
}

输出为:

swap(A, A)

更新

有人观察到:

namespace exp
{    
    template <>
    void swap(A&, A&)
    {
        printf("exp::swap(A, A)\n");
    }

}

工程!那么为什么不使用它呢?

考虑 your 是类模板的情况:A

// simulate user code which includes <algorithm>

template <class T>
struct A
{
};

namespace exp
{

    template <class T>
    void swap(A<T>&, A<T>&)
    {
        printf("exp::swap(A, A)\n");
    }

}

// exercise simulation

int main()
{
    A<int> a[2];
    exp::algorithm(a, a+2);
}

现在它不再起作用了。:-(

因此,您可以放入命名空间 std 并让它工作。但是,当您有模板时,您需要记住将 的命名空间放入 : .而且,由于如果您将命名空间放入命名空间,这两种情况都有效,因此更容易记住(并教其他人)以一种方式执行此操作。swapswapAA<T>swapA

评论

4赞 voltrevo 12/9/2011
非常感谢您的详细回答。我显然对此了解较少,实际上想知道超载和专业化如何产生不同的行为。但是,我不是建议超载,而是建议专业化。当我输入您的第一个示例时,我从 gcc 获得输出。那么,为什么不选择专业化呢?template <>exp::swap(A, A)
3赞 Howard Hinnant 12/9/2011
课堂上的好友语法应该没问题。我会尝试将函数范围限制在您的标题中。是的,几乎是一个关键词。但是不,它不是一个关键词。因此,最好不要将其导出到所有命名空间,直到您真正需要。 很像.最大的区别是,甚至没有人想过使用限定的命名空间语法进行调用(这太难看了)。using std::swapswapswapoperator==operator==
16赞 Howard Hinnant 10/2/2013
@NielKirk:你所看到的复杂之处在于太多的错误答案。Dave Abrahams 的正确答案并不复杂:“重载交换的正确方法是将其编写在与要交换的内容相同的命名空间中,以便可以通过参数相关查找 (ADL) 找到它。
3赞 Howard Hinnant 8/23/2015
@codeshot:对不起。自 1998 年以来,Herb 一直试图传达这个信息: gotw.ca/publications/mill02.htm 他在这篇文章中没有提到交换。但这只是 Herb 界面原理的另一种应用。
2赞 Howard Hinnant 5/5/2018
Visual Studio 尚未正确实现 C++98 中引入的两阶段查找规则。这意味着在此示例中,VS 调用了错误的 .这增加了一个我以前没有考虑过的新皱纹:在 的情况下,将你的 放入命名空间会使你的代码不可移植。在 wandbox 上尝试您的示例,看看 gcc 和 clang 如何处理它。swaptemplate<class T> struct Aswapstd