- #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;
- }
来源: http://www.phpxs.com/code/1009859/