区分STL容器

Question

很多时候，我想为不同的STL容器专门设计一个函数。然而，我并不想逐个进行专门设计，因为其中一些共享大部分所需的接口，例如std::vector和std::deque。

在我的使用情况中，主要有三种类别（类似于向量、集合和映射）。 例如，我想实现类似以下的东西，

template <class T>
struct A {
    template <class Y, class... Z>
    void func( Y y , Z... z ){
        //hypothetical static_if
        static_if ( T is similar to vector, deque, or boost::stable_vector etc which have push_back ) {
            t.push_back(y);
        }
        else static_if ( T is similar to set, unordered_set or boost::flat_set etc which have emplace)    {
            t.emplace(y);
        }

        else static_if ( T is similar to map, unordered_map or boost::flat_map etc which has emplace) {
            t.emplace(y, z...);
        }

    }

    T t;  
};

我认为这似乎是不可能的，但我希望能有某种方法来解决这个问题。如果可以扩展到列表类型（std::list、std::forward_list等）或boost::heap等，那就更好了。但是实现这个目标似乎太难了。

- Sungmin

---

目标是什么？在哪些情况下可以互换使用向量、集合和映射？ - Fred Foo

这可以通过使用专业化和类型特征来完成，但似乎你正在重新发明轮子，因为许多功能都由具有通用接口的std算法提供。 - rerun

@rerun：那么我应该查看哪些功能以实现此目的？ - Sungmin

Scott Meyers的《Effective STL》一书专门有一整节内容告诉你不要这样做。 - djechlin

“vector-like” 意味着顺序随机访问。Map 和 set 是关联式容器。（请阅读 Meyers 的书。） - djechlin

Answer 1

不行，抱歉。Scott Meyers的Effective STL书中专门有一章讨论了这个问题。以下是一段摘录，以便让您了解其中存在的问题：

假设您希望编写可与最常见的序列容器vector、deque和list一起使用的代码。显然，您必须编程到它们能力的交集，这意味着不能使用reserve或capacity（参见第14项），因为deque和list没有这些函数。同时list的存在也意味着您放弃了operator[]，并且限制自己使用双向迭代器的功能。而这反过来又意味着，您必须避免使用需要随机访问迭代器的算法，包括sort、stable_sort、partial_sort和nth_element（参见第31项）。

另一方面，您希望支持vector，则无法使用push_front和pop_front，而vector和deque都不支持splice和sort的成员形式。考虑到上述限制，后一种禁令意味着您无法在“广义序列容器”上调用任何形式的sort。

这是显而易见的。如果您违反了任何这些限制，您的代码将无法与您想要使用的任何一个容器编译。可以编译的代码更加隐蔽。主要原因是不同序列容器的迭代器、指针和引用失效规则不同。为了编写可以在vector、deque和list上正确工作的代码，您必须假定任何使迭代器、指针或引用失效的操作都会使您使用的容器中的它们失效。因此，必须假定每次调用insert都会使所有东西失效，因为deque::insert使所有迭代器失效，并且由于无法调用capacity，所以必须假定vector::insert会使所有指针和引用无效。（第1项解释了deque在有时使其迭代器失效而不使其指针和引用失效是独特的。）类似的推理导致结论：每次调用erase都必须假定使所有内容失效。

还想知道更多吗？（是的，这个条目会继续下去，下去，下去。）

- djechlin

Answer 2

这是一个用于容器的粗糙类型特征库。

template<typename Container>
struct container_traits;

template<bool b=true>
struct has_emplace_back { typedef std::integral_constant<bool, b> emplace_back; };
template<bool b=true>
struct has_emplace { typedef std::integral_constant<bool, b> emplace; };

template<typename T, typename A>
struct container_traits< std::vector<T,A> > : has_emplace_back<>, has_emplace<> {};
// etc
template<typename T, typename A>
struct container_traits< std::set<T,A> > : has_emplace_back<false>, has_emplace<> {};
// etc

template<typename T>
using HasEmplaceBack = typename container_traits<T>::has_emplace_back;
template<typename T>
using HasEmplace = typename container_traits<T>::has_emplace;

template<int> struct enum_enum { enum class type {}; };
template<int index> using UniqueEnum = typename enum_enum<index>::type;

template<bool b, int index=1>
using EnableIf = typename std::enable_if< UniqueEnum<index> >::type;
template<bool b, int index=1>
using DisableIf = EnableIf< b, -index >;

template<typename Container, typename... Args, EnableIf< HasEmplace<Container>::value && !HasEmplaceBack<Container>::value, 1 >... >
void emplace_in( Container&& c, Args&&... args ) {
  std::forward<Container>(c).emplace( std::forward<Args>(args)... );
}
template<typename Container, typename... Args, EnableIf< HasEmplaceBack<Container>::value, 2 >... >
void emplace_in( Container&& c, Args&&... args ) {
  std::forward<Container>(c).emplace_back( std::forward<Args>(args)... );
}

< p > EnableIf<>... 技术在 clang 中不起作用，我没有编译它，所以可能需要一些调试来修复。

- Yakk - Adam Nevraumont

---

谢谢。实际上，我无法完全理解你的代码，特别是UniqueEnum部分。不过，我猜测std::vector既有emplace函数也有emplace_back函数。 - Sungmin

@Sungmin 很好的观点 - 虽然 emplace 是不同的。 "具有无位置的 emplace" 太啰嗦了。 UniqueEnum<x> 对于每个 x 都是一个独特的空 enum class 类型，EnableIf 和 DisableIf 在 bool 为 true 时会求其值为这样的 UniqueEnum 类型。 我传递这些 UniqueEnum 的(空)可变参数包作为类型参数到 emplace_in 中，以确保这两个模板具有不同的模板签名。我将微调容器特性使假情况工作... - Yakk - Adam Nevraumont

谢谢。这个技巧看起来相当不错。:) 所以，我必须将所有可能的容器枚举为“container_trait”的模板参数，对吗？ - Sungmin

@sungmin 无参数的 emplace 无法被检测到。带参数的 emplace 可以被检测到。因此，可以编写一个名为 can_emplace_back_with<T,Args...> 的 trait，以及 can_emplace_nakedly。这有点危险，因为如果 Args... 恰好是 2 或更长，并且第一个参数可以转换为 iterator，则可能会在 vector 上意外地使用 emplace。 - Yakk - Adam Nevraumont

Answer 3

这并非不可能，只是实现起来不太方便或琐碎。实际上，需要一个 container_traits 库。

可以使用SFINAE 来检测某个类型的 Container 是否包含满足各种 STL Container Concepts 要求的必要特性。

例如，is_associative_container 可以使用 SFINAE 来检查 Container 类型是否具有 key_type 和 mapped_type typedef，以及 value_type 为 std::pair<const key_type, map_type> 等符合实现 AssociativeContainer 概念的对象所需的所有其他要求。

总之，这确实需要作为一个完整的库来实现。它不容易实现，如果您只有简单的一次性需求，最好在 Iterator 级别进行抽象。

- Charles Salvia

---

那么，难道没有一个著名的库类似于 is_associative_container 吗？ - Sungmin

不需要一个container_traits库。它的不存在在某种程度上阻止了糟糕的设计，比如所提出的设计。 - djechlin

Answer 4

我一周前尝试了复杂的特性，但为了更好的可读性而放弃了。

所以这里看一个例子：有没有更好的方法来检查STL容器是否是多*容器

- Felix Petriconi

---

谢谢，所以您建议我必须专门化所有可能的类吗？我想这似乎是最干净的方式。 - Sungmin

这取决于你要选择哪些特征。在我的情况下，我必须区分集合(set)、映射(map)和多重映射(multi-map)。 - Felix Petriconi