#include <iostream> #include <stdexcept> #include <vector> #include <algorithm> #include <memory> #include <map>
namespace{ enum:int{ MAXVALUE = 9999 }; } template<typename T> class Node{ private: T key_; public: template<typename Ty> Node(const Ty& key); template<typename Ty> Node(const Node<Ty>& otherNode_); template<typename Ty> Node(Node<Ty>&& otherNode_); Node() = default; ~Node(); template<typename Ty> friend bool operator==(const Node<Ty>& first_, const Node<Ty>& second_); template<typename Ty> friend bool operator<(const Node<Ty>& first_, const Node<Ty>& second_); const Node<T>& operator=(const Node<T>& otherNode_);//必须这么写 不然编译器还会合成. template<typename Ty> friend std::ostream& operator<<(std::ostream& os, const Node<Ty>& node_); template<typename Ty> void operator=(Node<Ty>&& otherNode_); }; template<typename T> template<typename Ty> Node<T>::Node(const Ty& key) :key_(key) { //std::cout<<"constructor function."<<std::endl; } template<typename T> template<typename Ty> Node<T>::Node(const Node<Ty>& otherNode_) :key_(otherNode_.key_) { std::cout<<"copy for constructor"<<std::endl; } template<typename T> Node<T>::~Node() { // } template<typename Ty> bool operator==(const Node<Ty>& first_, const Node<Ty>& second_) { return (first_.key_ == second_.key_) ? true : false; } template<typename T> const Node<T>& Node<T>::operator=(const Node<T>& otherNode_) //必须这么写不然编译器自己合成. { this->key_ = otherNode_.key_; std::cout<<"copy function"<<std::endl; } template<typename Ty> bool operator<(const Node<Ty>& first_, const Node<Ty>& second_) { std::cout<<"<"<<std::endl; return (first_.key_ < second_.key_) ? true : false; } template<typename Ty> std::ostream& operator<<(std::ostream& os, const Node<Ty>& node_) { os<<node_.key_<<std::endl; return os; } template<typename T> template<typename Ty> void Node<T>::operator=(Node<Ty>&& otherNode_) { std::cout<<"operator move"<<std::endl; this->key_ = otherNode_.key_; } template<typename T> class Map{ private: class Compare{ public: template<typename Ty> bool operator()(const Node<Ty>& first_, const Node<Ty>& second_); }; //template<typename Ty> //typedef Graph std::map<Node<Ty>, std::map<Node<Ty>, int>>; //不能用typedef只能用using. class Container{ public: template<typename Ty> bool operator()(typename Map<Ty>::cv_iter currentIter_, std::shared_ptr<Node<Ty>> currentNode_); }; std::map<Node<T>, std::map<Node<T>, int>> graph_; //该边的加权值可以为负 std::map<Node<T>, std::vector<Node<T>>> adjList_; std::map<Node<T>, std::map<Node<T>, int>> temp_graph_; unsigned int nodeNumber_; template<typename Ty> typename Map<Ty>::Graph extend_shortest_paths(std::shared_ptr< typename Map<Ty>::Graph > g); const int& min(const int& first_, const int& second_); public: template<typename Ty> using Graph = std::map<Node<Ty>, std::map<Node<Ty>, int>>;//类型别名. template<typename Ty> using v_iter = typename std::vector<Node<Ty>>::const_iterator;//类型别名. template<typename Ty> using cv_iter = typename std::map<Node<Ty>, std::vector<Node<Ty>>>::const_iterator; template<typename Ty> using cmm_iter = typename std::map<Node<Ty>, std::map<Node<Ty>, int>>::const_iterator;//类型别名. template<typename Ty, unsigned int N> Map(const Ty (&edge)[N][3]); ~Map(); Map()=default; void slow_all_pairs_shortest_paths(); }; template<typename T> template<typename Ty, unsigned int N> Map<T>::Map(const Ty (&edges)[N][3]) :nodeNumber_(N) { if(N == 0){ throw std::runtime_error(std::string("there is nothing in graph")); } for(int i =0; i<N; ++i){ //存储无向图中的数据以及两个相连接结点之前的加权值。 Node<Ty> first_(edges[i][0]); Node<Ty> second_(edges[i][2]); this->graph_[first_][second_] = edges[i][1]; this->temp_graph_[first_][second_] = ::MAXVALUE; this->adjList_[first_].push_back(second_); //邻接链表：跟结点A相连接的所有结点都被放在一个vector中. } } template<typename T> template<typename Ty> typename Map<Ty>::Graph Map<T>::extend_shortest_paths(std::shared_ptr< typename Map<Ty>::Graph > g) { typename Map<Ty>::Container jundge_; typename Map<Ty>::cv_iter first_ = this->adjList_.cbegin(); typename Map<Ty>::v_iter second_ = this->adjList_[first_->first].cbegin(); typename Map<Ty>::Graph temp_graph_; for(; first_ != this->adjList_.cend(); ++first_){ for(; second_ != this->adjList_[first_->first].cend(); ++second_){ temp_graph_[first_->first][*second_] = ::MAXVALUE; typename Map<Ty>::v_iter third_ = this->adjList_[first_->first].cbegin(); for(; third_ != this->adjList_[first_->first].cend(); ++third_){ bool boolean = jundge(third_, std::make_shared<Node<Ty>> (*second_)); if(boolean == false){ continue; } temp_graph_[first_][second_] = this->min(temp_graph_[first_][second_], (*g)[first_][third_]+this->graph_[third_][second_]); } } } return (*g); } template<typename T> void Map<T>::slow_all_pairs_shortest_paths() { Map<T>::Graph<T> L(this->graph_); for(int i=1; i<this->nodeNumber_; ++i){ L = this->extended_shortest_paths(std::make_shared< Map<T>::Graph<T> > (this->graph_)); } } template<typename T> template<typename Ty> bool Map<T>::Compare::operator()(const Node<Ty>& first_, const Node<Ty>& second_) { return first_ < second_ ? true : false; } template<typename T> const int& Map<T>::min(const int& first_, const int& second_) { return (first_ < second_) ? first_ : second_; } template<typename T> template<typename Ty> bool Map<T>::Container::operator()(typename Map<Ty>::cv_iter currentIter_, std::shared_ptr<Node<Ty>> currentNode_) { if(Map<Ty>::adjList_[*currentNode_].empty()){ return false; }else{ typename Map<Ty>::v_iter first_ = Map<Ty>::adjList_[*currentNode_].cbegin(); typename Map<Ty>::v_iter second_ = Map<Ty>::adjList_[*currentNode_].cend(); typename Map<Ty>::v_iter third_; third_=std::find_if(first_, second_, [currentNode_](const Node<Ty>& temp_)->bool { return (temp_ == *currentNode_) ? true : false; }); if(third_ == second_){ return false; }else{ return true; } } } int main() { Node<int> one_(20); Node<int> two_(30); Node<int> three_; three_ = one_; one_ = two_; std::cout<<one_; three_ = std::move(one_); std::cout<<std::boolalpha<< (one_<two_ )<<std::endl; return 0; }
