c – 正确测试容器是否实现.at()成员访问/ std :: sort兼容的方法

前端之家收集整理的这篇文章主要介绍了c – 正确测试容器是否实现.at()成员访问/ std :: sort兼容的方法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我正在寻找最佳/正确的方法来确定容器是否通过.at()实现随机元素访问.
在不同(stl)容器相对于彼此进行排序的场景中(比如对容器std :: vector< int>进行排序,相对于std :: vector< double>),我做了以下事情:
  1. std::sort(toOrder.begin(),toOrder.end(),[&orderBy](int i,int j) -> bool {
  2. return orderBy.at(i) > orderBy.at(j);
  3. });

哪里

  1. std::vector<int> toOrder;
  2. std::vector<double> orderBy

我可以将它包装在模板函数中,但不确定限制或测试具有随机访问迭代器/ .at()的容器的最佳方法(当它们没有时,需要做一些昂贵的事情).

我有这个

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <unordered_set>
  5.  
  6. template <typename T,typename U>
  7. void sorty(T& a,U const x) {
  8. std::sort(a.begin(),a.end(),[&x](int i,int j) -> bool { return x.at(i) > x.at(j); });
  9. }
  10.  
  11. int main() {
  12.  
  13. std::vector<int> toOrder(10);
  14. std::iota(toOrder.begin(),0);
  15. std::vector<double> orderBy{0.2,9.8,4.0,0.01,15.1,3.3,9.01,9.11,100.1,2.03};
  16.  
  17. std::unordered_set<double> orderBy_s(orderBy.begin(),orderBy.end()); // no .at()
  18.  
  19. sorty(toOrder,orderBy);
  20.  
  21. for (auto i : toOrder) {
  22. std::cout << i << "\t";
  23. }
  24.  
  25. return 0;
  26. }

演示代码here

更新:我匆匆发布,没有编辑标题.我关注任何容器类型,而不仅仅是STL.我的例子使用了STL容器以方便和重现.

解决方法

基本上,这不是应该实施通用 algorithms的正确方法.通常,可以使用 iteratorsstd::iterator_traits来确定基础类型和允许的操作.如果要根据容器提供的接口(随机访问,非随机访问)执行不同的算法(具有不同的复杂性),则应执行以下操作.

首先,您的通用算法应该在范围而不是容器上运行.也就是说,这应该看起来像< algorithm>的任何函数

  1. template <typename Iterator>
  2. void sorty(Iterator first,Iterator last);

其次,您应该编写应用不同排序方法的辅助函数,以尽可能多地利用容器的接口,从而以最有效的方式工作:

  1. // O(N*lgN) complexity sorting
  2. template <typename Iterator>
  3. void sorty_helper(Iterator first,Iterator last,std::random_access_iterator_tag);
  4.  
  5. // O(N*N) complexity sorting
  6. template <typename Iterator>
  7. void sorty_helper(Iterator first,std::forward_iterator_tag);

现在,您的原始sorty函数实际上应该只根据通过std :: iterator_traits获得的迭代器的类型将迭代器转发到适当的辅助函数

  1. template <typename Iterator>
  2. void sorty(Iterator first,Iterator last)
  3. {
  4. sorty_helper(first,last,typename std::iterator_traits<Iterator>::iterator_category());
  5. }

DEMO 1

另一种方法是使用SFINAE技术启用/禁用功能模板:

  1. #include <iterator>
  2. #include <type_traits>
  3.  
  4. template <typename Iterator>
  5. typename std::enable_if<
  6. std::is_same<typename std::iterator_traits<Iterator>::iterator_category,std::random_access_iterator_tag>::value
  7. >::type
  8. sorty(Iterator first,Iterator last)
  9. {
  10. // O(N*lgN) complexity sorting
  11. }
  12.  
  13. template <typename T> struct AlwaysFalse : std::false_type {};
  14.  
  15. template <typename Iterator>
  16. typename std::enable_if<
  17. !std::is_same<typename std::iterator_traits<Iterator>::iterator_category,Iterator last)
  18. {
  19. // other sorting algorithm or print out a user-friendly error
  20. static_assert(AlwaysFalse<Iterator>{},"Iterator must be a random-access iterator!");
  21. }

DEMO 2

其中enable_if和is_same是C 11的类型特征,C 03中的特征可以定义如下:

  1. template <bool b,typename T = void>
  2. struct enable_if {};
  3. template <typename T>
  4. struct enable_if<true,T> { typedef T type; };
  5. template <typename T,typename U>
  6. struct is_same { static const bool value = false; };
  7. template <typename T,typename U>
  8. const bool is_same<T,U>::value;
  9. template <typename T>
  10. struct is_same<T,T> { static const bool value = true; };
  11. template <typename T>
  12. const bool is_same<T,T>::value;

另一方面,如果您只想检查at成员函数的存在,并根据它做出编译时决策,您可能希望使用表达式SFINAE技术:

  1. template <typename Container>
  2. auto sorty_helper(Container&& container,int)
  3. -> decltype(void(std::forward<Container>(container).at(0)))
  4. {
  5. // O(N*lgN) complexity sorting
  6. }
  7.  
  8. template <typename Container>
  9. void sorty_helper(Container&& container,void*)
  10. {
  11. // O(N*N) complexity sorting
  12. }
  13.  
  14. template <typename Container>
  15. void sorty(Container&& container)
  16. {
  17. sorty_helper(std::forward<Container>(container),0);
  18. }

DEMO 3

在C 03中,验证给定签名的成员函数的存在需要手写特征:

  1. template <typename T>
  2. struct has_at
  3. {
  4. typedef char (&yes)[1];
  5. typedef char (&no)[2];
  6.  
  7. template <typename U,U u>
  8. struct SFINAE {};
  9.  
  10. template <typename U>
  11. static yes test(SFINAE<typename U::reference(U::*)(std::size_t),&U::at>*);
  12.  
  13. template <typename U>
  14. static no test(...);
  15.  
  16. static const bool value = sizeof(test<T>(0)) == sizeof(yes);
  17. };

可以与enable_if结合使用:

  1. template <bool b,typename T = void>
  2. struct enable_if {};
  3.  
  4. template <typename T>
  5. struct enable_if<true,T> { typedef T type; };
  6.  
  7. template <typename Container>
  8. typename enable_if<has_at<Container>::value>::type
  9. sorty(Container& container)
  10. {
  11. // O(N*lgN) complexity sorting
  12. }
  13.  
  14. template <typename Container>
  15. typename enable_if<!has_at<Container>::value>::type
  16. sorty(Container& container)
  17. {
  18. // O(N*N) complexity sorting
  19. }

DEMO 4

猜你在找的C&C++相关文章