重拾c++感触

发表于 2013-10-22 更新于 2015-03-11 分类于计算机界，编程语言 Waline：阅读次数：

很久不用c++了，最近重新拾起，确实是很多地方让人无语
下面这段代码，是用vector与heap实现PriorityQueue
本来想想觉得简单得不得了，写起来才发现各种小问题调了我一整天。

//
//  PriorityQueue.h
//
//  Created by 姜孟冯 on 13-10-19.
//  Copyright (c) 2013年 姜孟冯. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;

/********************************************************
*  class declaration
********************************************************/
template<class T, class COMP> class PriorityQueue;

/********************************************************
*  friend functions
********************************************************/

// print the content of the priority queue, not in class PriorityQueue
template<class T, class COMP>
ostream& operator<<(ostream& o, PriorityQueue<T, COMP>& pq);

/********************************************************
*  class defination
********************************************************/

/*
 * This PriorityQueue class represents a priority queue. Use T as a node type 
 * and COMP as its comparator.
 */
template<class T, class COMP=greater<T>>
class PriorityQueue {
protected:
   vector<T> _v;    // use <vector> and <algorithm>'s heap
                // function to build PriorityQueue
   COMP _cmp; // compare function

public:
   // changes the value of queue_element to new_element
   void change_prioirity(const T& queue_element, const T& new_element);

   // removes the top element of the queue.
   void pop();

   // does the queue contain queue_element.
   bool contains(const T& queue_element) const;

   // insert queue_element into queue
   void insert(const T& queue_element);

   // returns the top element of the queue.
   const T& top() const;

   // return the number of queue_elements.
   int size() const;

   PriorityQueue();
   ~PriorityQueue();

   // print the content of the priority queue
   friend ostream & operator<<<T, COMP>(ostream & o, PriorityQueue& pq);
};

//
//  PriorityQueue.cpp
//
//  Created by 姜孟冯 on 13-10-19.
//  Copyright (c) 2013年 姜孟冯. All rights reserved.
//

#include "PriorityQueue.h"
#include <algorithm>
#include <functional>

/********************************************************
*  friend functions
********************************************************/

// print the content of the priority queue
template<class T, typename COMP>
ostream& operator<<(ostream& o, PriorityQueue<T, COMP>& pq)
{
   for (typename vector<T>::iterator iter = pq._v.begin(); iter != pq._v.end();
        iter++)
   {
      if (iter != pq._v.begin())
      {
         o << ",";
      }
      o << *iter;
   }
   return o;
}


/********************************************************
*  class PriorityQueue methods
********************************************************/

// constructor
template<class T, typename COMP>
PriorityQueue<T, COMP>::PriorityQueue()
{
   make_heap(_v.begin(), _v.end(), _cmp);
}


// changes the priority (node value) of queue element.
// class T must implement method "T::set_value(V)"
template<class T, typename COMP>
void PriorityQueue<T, COMP>::change_prioirity(const T& queue_elemnt,
                                           const T&  new_element)
{
   if (this->contains(queue_elemnt))
   {
      typename vector<T>::iterator iter = find(_v.begin(),
                                               _v.end(), queue_elemnt);
      *iter=new_element;
   }
   make_heap(_v.begin(), _v.end(), _cmp);
}


// removes the top element of the queue.
template<class T, typename COMP>
void PriorityQueue<T, COMP>::pop()
{
   pop_heap(_v.begin(), _v.end(), _cmp);
   _v.pop_back();
}


// does the queue contain queue_element.
template<class T, typename COMP>
bool PriorityQueue<T, COMP>::contains(const T& queue_element) const
{
   return find(_v.begin(), _v.end(), queue_element) != _v.end();
}


// insert queue_element into queue
template<class T, typename COMP>
void PriorityQueue<T, COMP>::insert(const T& queue_element)
{
   _v.push_back(queue_element);
   push_heap(_v.begin(), _v.end(), _cmp);
}


// returns the top element of the queue.
template<class T, typename COMP>
const T& PriorityQueue<T, COMP>::top() const
{
   return _v.front();
}


// return the number of queue_elements.
template<class T, typename COMP>
int PriorityQueue<T, COMP>::size() const
{
   return static_cast<int>(_v.size());
}

由于感触颇深，所以作为一个c++外行，简单写写
1.谓词的问题
c++据我所知应该是没有匿名函数支持的，这简直不可思议
看看objective-c里的block、python里的lambda、ruby里的proc
这些都是好用得不得了的例子。
但c++里的谓词，我怎么用都觉得难用……
自定义函数类与继承结合要写在template里，我不知道这是不是标准用法，不过反正可行

template<class T, class COMP=greater<T>>
class PriorityQueue {
protected:
   vector<T> _v;    // use <vector> and <algorithm>'s heap
                // function to build PriorityQueue
   COMP _cmp; // compare function

bind2nd实在是个好用的函数，可以把一个二元函数绑定成一元。
有了它，那些stl里参数为的一元谓词的函数才变得好用。
比如any_of与find_if，网上找来找去都是这样的例子

bool isOdd(int i){
return i%2!=0
}
...
any_of(_v.begin(), _v.end(), isOdd);
...

有个毛用啊！！
但有了bind2nd之后，就可以这样写了

any_of(_v.begin(), _v.end(), bind2nd(_cmp, queue_element));

这是我昨天发现的最好用的c++函数

2.字符串转换的问题
一个简单到极点的int转sring的问题，在网上一搜，居然还有一大堆啰嗦的实现
有用sprintf的，有用stringstream的，还有用itoa的，我就想哭了……
难道中国程序员的c++水平还在98年么？
从C++11开始，用std::to_string(int)才是正常做法

3.random问题
这个不想细说了，还用%那真是上个世纪的写法。

#include<random>
#include<chrono>
...
unsigned int                      seed = static_cast<unsigned int>(std::chrono::system_clock::now().time_since_epoch().count());
default_random_engine             generator(seed);
uniform_real_distribution<double> real_distribution(1.0, 10.0);
uniform_int_distribution<double> int_distribution(1, 10);

...
int a = int_distribution(generator);
double b = real_distribution(generator);
...

4.异常问题
还是贴代码

#include<stdexcept>
...
if (V < 0)
    throw runtime_error("Number of vertices must be nonnegative");

5.模板的问题
这个是重点啊，来个三小点
1)模板与迭代器
我实在想不通 vector<T>::iterator iter这样定义一个迭代器有什么错。
查了很久才发现，要写typename vector<T>::iterator iter

2)模板与分离编译
模板类如果分开写在.h与.cpp里，连接器会报错。这与C++标准有关，因为只有调用才会实例化函数体。
在C++98的标准中，有export关键字，也就是在.cpp文件里这样写

export template<class T, typename V>
PriorityQueue<T, V>::PriorityQueue()
{
   make_heap(_v.begin(), _v.end(), _cmp);
}

但是呢，主流编译器都不支持它，包括VS、g++以及xcode，因为这标准已经过期了
据说intel的compiler可以支持，反正我没用过。
目前解决方式是直接include .cpp文件，虽然这很不美╮(╯_╰)╭

模板与友元函数(坑爹的重重点)

template <class T>
class PriorityQueue{
    friend ostream & operator<< (ostream & o, PriorityQueue &pq);
};

template <typename T>
ostream & operator<<(ostream& o, PriorityQueue<T> &pq)
{
    ...
    return o;
}

这是错的！！声明的友元的函数是一个一般函数，不是下面定义的那个。

template <class T>
class PriorityQueue{
    friend ostream & operator<< (ostream & o, PriorityQueue<T> &pq);
};

template <typename T>
ostream & operator<<(ostream& o, PriorityQueue<T> &pq)
{
    ...
    return o;
}

这也是错的！！因为参数里的T和实例化PriorityQueue用的T被认为不一样。

template <class T>
class PriorityQueue{
    friend ostream & operator<< <T> (ostream & o, PriorityQueue &pq);
};

template <typename T>
ostream & operator<<(ostream& o, PriorityQueue<T> &pq)
{
    ...
    return o;
}

这是模板函数的标准写法了，可还是错的。

template <class T> class PriorityQueue;

template <typename T>
ostream & operator<<(ostream& o, PriorityQueue<T> &pq)
{
    ...
    return o;
}

template <class T>
class PriorityQueue{
    friend ostream & operator<< <T> (ostream & o, PriorityQueue &pq);
};

真正的正确写法是前置声明，我对这个问题彻底无语。