相关疑难解决方法(0)

的std::sort算法(及其同类std::partial_sort和std::nth_element从C++标准库)是在大多数实现的更基本的排序算法复杂和混合合并,如选择排序,插入排序,快速排序,归并排序,或堆排序.

这里和姐妹网站上有很多问题,例如https://codereview.stackexchange.com/,与错误,复杂性以及这些经典排序算法的实现的其他方面有关.大多数提供的实现包括原始循环,使用索引操作和具体类型,并且在正确性和效率方面分析通常是非常重要的.

问:如何使用现代C++实现上述经典排序算法？

• 没有原始循环,但结合了标准库的算法构建块<algorithm>
• 迭代器接口和模板的使用,而不是索引操作和具体类型
• C++ 14风格,包括完整的标准库,以及语法降噪器,如auto模板别名,透明比较器和多态lambda.

备注:

• 有关排序算法实现的进一步参考,请参阅Wikipedia,Rosetta Code或http://www.sorting-algorithms.com/
• 根据Sean Parent的惯例(幻灯片39),原始循环for比使用运算符的两个函数的组合更长.所以f(g(x));或f(x); g(x);或f(x) + g(x);不生循环,也不是在环路selection_sort和insertion_sort下方.
• 我遵循Scott Meyers的术语来表示当前的C++ 1y已经作为C++ 14,并且将C++ 98和C++ 03都表示为C++ 98,所以不要因此而激怒我.
• 正如@Mehrdad的评论中所建议的那样,我在答案的最后提供了四个实现作为实例:C++ 14,C++ 11,C++ 98和Boost and C++ 98.
• 答案本身仅以C++ 14的形式呈现.在相关的地方,我表示各种语言版本不同的语法和库差异.

我试图将一组整数中的项的默认顺序更改为lexicographic而不是numeric,并且我无法使用g ++进行以下编译:

file.cpp:

bool lex_compare(const int64_t &a, const int64_t &b) 
{
    stringstream s1,s2;
    s1 << a;
    s2 << b;
    return s1.str() < s2.str();
}

void foo()
{
    set<int64_t, lex_compare> s;
    s.insert(1);
    ...
}

我收到以下错误:

error: type/value mismatch at argument 2 in template parameter list for ‘template<class _Key, class _Compare, class _Alloc> class std::set’
error:   expected a type, got ‘lex_compare’

我究竟做错了什么？

以下两行有什么区别？

map<int, float> map_data;
map<const int, float> map_data;

我经常发现自己想写这样的代码:

class MyClass
{
public:
  void addObject(std::unique_ptr<Object>&& newObject);

  void removeObject(const Object* target);

private:
  std::set<std::unique_ptr<Object>> objects;
};

但是,很多std :: set接口对std :: unique_ptrs都没用,因为查找函数需要std :: unique_ptr参数(我显然没有这些参数,因为它们由集合本身拥有).

我可以想到两个主要的解决方案.

1. 创建临时unique_ptr以进行查找.例如,上面的removeObject()可以实现如下:

   void MyClass::removeObject(const Object* target)
   {
     std::unique_ptr<Object> targetSmartPtr(target);
     objects.erase(targetSmartPtr);
     targetSmartPtr.release();
   }
   

   Run Code Online (Sandbox Code Playgroud)

2. 将原始指针映射替换为unique_ptrs.

     // ...
     std::map<const Object*, std::unique_ptr<Object>> objects;
   };
   

   Run Code Online (Sandbox Code Playgroud)

然而,对我来说,两者似乎都有点愚蠢.在解决方案1中,erase()不是noexcept,因此临时unique_ptr可能会删除它实际上不拥有的对象,而2需要不必要地为容器存储两倍.

我知道Boost的指针容器,但与现代C++ 11标准库容器相比,它们目前的功能有限.

我最近在阅读有关C++ 14的内容,并且遇到了"将异构比较查找添加到关联容器".但是形成我对它的理解,查找类型必须与键类型相当,但原始指针不能与unique_ptrs相比.

任何人都知道更优雅的解决方案或即将添加的C++解决了这个问题？

#include <set>
#include <string>
#include <string_view>

using namespace std;

int main()
{
    string_view key = "hello";

    set<string> coll1;
    coll1.find(key); // error

    set<string, less<>> coll2;
    coll2.find(key); // ok since C++14
}

那么,它应该是一个规则:

总是喜欢 set<T, less<>> 对 set<T> ,因为C++ 14？

以下代码无法在最近的编译器上构建(g ++ - 5.3,clang ++ - 3.7).

#include <map>
#include <functional>
#include <experimental/string_view>

void f()
{
    using namespace std;
    using namespace std::experimental;
    map<string, int> m;
    string s = "foo";
    string_view sv(s);
    m.find(sv);
}

clang返回的错误:

error: no matching member function for call to 'find'
    m.find(sv);
    ~~^~~~

但是不find应该能够使用类似的类型？Cppreference提到了以下重载:

template< class K > iterator find( const K& x );

发生同样的错误boost::string_ref.

在C++ 0x中有没有可用的替代Boost的bimap？

我想避免使用Boost,但完全接受C++ 11.如果有必要的话,在我的程序中,Boost的bimap的精简版本对我有用(我需要一个恒定的bimap来在枚举和相应的字符串之间切换).地图将是编译时常量,因此即使两个手动维护的地图也不是最佳解决方案.

谢谢!

更新:我在代码项目中找到了这个,但似乎许可可能是一个问题:http://www.codeproject.com/KB/stl/bimap.aspx？ fid = 12042&df = 90&mpp = 25&noise = 3&sort = Position&view = Quick&fr = 151#xx0xx

我只是在寻找一个干净简单的解决方案(一个标题/源文件或一点额外,因为在我的情况下两个镜像地图同样好).

STL仿函数的实现方式如下:

template<class T>
struct less{
  bool operator()(T const& lhs, T const& rhs){
    return lhs < rhs;
  }
};

这使我们每次创建这样的仿函数时都会提到(可能很长)类型.为什么它们没有如下所示实现？有什么原因？

struct less{
  template<class T>
  bool operator()(T const& lhs, T const& rhs){
    return lhs < rhs;
  }
};

这将使它们可用而不提及(可能很长)类型.

我有以下问题:

std::map<A*,double> map;

void getColor(A const * obj){
    double d = map[obj]; // does not compile wihtout const_cast<A*>(obj)
    // do something
}

我有一个地图std::map(某处)存储指向对象的指针A.我有一个不操纵对象的函数getColor, 因此将指针 作为输入.Aconst A

如果getColor不使用const_cast ,函数将无法编译.

const cast是一个设计问题,但如果我不想在map const中创建键,我不知道如何规避它.

任何帮助赞赏.

环顾cppreference,我发现从"等效键" std::unordered_map 获得高效的查找功能.

我认为这意味着等效键必须具有相同的哈希值.我如何为字符串文字提供相同的哈希值,而std::hash<std::string>不是临时构造一个std::string,从而使得关于等价键的全部观点为无效？