std::sort and binary '=' operator issue with a C++ struct

Question

Ok... I have this struct and comparison function-

struct Edge
{
          char point1;  
          char point2;  
          int weight;   

          bool operator<( const Edge& rhs ) const
          {
              return( weight < rhs.weight );
          }
}; //end Edge

bool compareEdge( const Edge& lhs, const Edge& rhs )
{
      return( lhs.weight < rhs.weight );
}

I have a vector declared as...

vector<Edge> edges;

Finally, I try to sort using the < operator...

sort( edges.begin(), edges.end() );

and I get the following error in Visual Studio 2005...

------ Build started: Project: RadakovichLab6, Configuration: Debug Win32 ------ Compiling... graph.cpp c:\program files\microsoft visual studio 8\vc\include\algorithm(2981) : error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const Edge' (or there is no acceptable conversion)
c:\documents and settings\jake\my documents\visual studio 2005\projects\radakovichlab6\graph.h(25): could be 'Edge &Edge::operator =(const Edge &)'
while trying to match the argument list '(const Edge, Edge)'
c:\program files\microsoft visual studio 8\vc\include\algorithm(2997) : see reference to function template instantiation 'void std::_Insertion_sort1<_BidIt,Edge>(_BidIt,_BidIt,_Ty*)' being compiled
with
[
    _BidIt=std::_Vector_const_iterator<Edge,std::allocator<Edge>>,
    _Ty=Edge
]
c:\program files\microsoft visual studio 8\vc\include\algorithm(3105) : see reference to function template instantiation 'void std::_Insertion_sort<_RanIt>(_BidIt,_BidIt)' being compiled
with
[
    _RanIt=std::_Vector_const_iterator<Edge,std::allocator<Edge>>,
    _BidIt=std::_Vector_const_iterator<Edge,std::allocator<Edge>>
]
c:\program files\microsoft visual studio 8\vc\include\algorithm(3112) : see reference to function template instantiation 'void std::_Sort<std::_Vector_const_iterator<_Ty,_Alloc>,__w64 int>(_RanIt,_RanIt,_Diff)' being compiled
with
[
    _Ty=Edge,
    _Alloc=std::allocator<Edge>,
    _RanIt=std::_Vector_const_iterator<Edge,std::allocator<Edge>>,
    _Diff=__w64 int
]
c:\documents and settings\jake\my documents\visual studio 2005\projects\radakovichlab6\graph.cpp(107) : see reference to function template instantiation 'void std::sort<std::_Vector_const_iterator<_Ty,_Alloc>>(_RanIt,_RanIt)' being compiled
with
[
    _Ty=Edge,
    _Alloc=std::allocator<Edge>,
    _RanIt=std::_Vector_const_iterator<Edge,std::allocator<Edge>>
] c:\program files\microsoft visual studio 8\vc\include\algorithm(2988) : error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const Edge' (or there is no acceptable conversion)
c:\documents and settings\jake\my documents\visual studio 2005\projects\radakovichlab6\graph.h(25): could be 'Edge &Edge::operator =(const Edge &)'
while trying to match the argument list '(const Edge, const Edge)' c:\program files\microsoft visual studio 8\vc\include\algorithm(2989) : error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const Edge' (or there is no acceptable conversion)
c:\documents and settings\jake\my documents\visual studio 2005\projects\radakovichlab6\graph.h(25): could be 'Edge &Edge::operator =(const Edge &)'
while trying to match the argument list '(const Edge, Edge)' Generating Code... Compiling... main.cpp Generating Code... Build log was saved at "file://c:\Documents and Settings\Jake\My Documents\Visual Studio 2005\Projects\RadakovichLab6\Debug\BuildLog.htm" RadakovichLab6 - 3 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

The question is in the first line of the error. I get this error whether I use the overloaded < operator, or pass the comparison function to the std::sort function. The Edge structure's default assignment operator should suffice, I would think, because there is no dynamically allocated memory. If anyone has any insight I would be grateful.

full code...

        #include <list>
        #include <map>
        #include <queue>
        #include <vector>
        #include <algorithm>
        #include <iostream>

        using namespace std;

        //the Edge and aGraph together represent the adjacency list
        //representation of a graph.
        struct Edge
        {
            char point1;  //this represents the endpoint of an edge
            char point2;  
            int weight;   //this is the weight of the edge

            bool operator<( const Edge& rhs ) const
            {
                return( weight < rhs.weight );
            }
        }; //end Edge

        class Graph
        {
        public:
            //Default constructor
            Graph();

            //This method inputs an edge into a graph.
            void inputEdge( char pointA, char pointB, int wt )
            {
                //used to input the edges of the graph
            Edge anEdge;

            //prepare for insertion into list
            anEdge.point1 = pointA;
            anEdge.point2 = pointB;
            anEdge.weight = wt;

            edges.push_back( anEdge );

            //insert edge into the adjacency list.
            aGraph[pointA].push_front( pointB );

            //insert the opposite direction into the
            //adjacency list.
            aGraph[pointB].push_front( pointA )
             }

             //This...
             void bfs();

            //This prints a graph and is used only for debugging purposes.
            void printGraph() const
            {

             list<char>::const_iterator listIter;
             map<char, list<char>>::const_iterator mapIter;

             for( mapIter = aGraph.begin(); 
              mapIter != aGraph.end();
              mapIter++ )
             {
                for( listIter = mapIter->second.begin();
                         listIter != mapIter->second.end();
                         listIter++ )
               {
                     cout << mapIter->first << " " << *listIter << endl;
               } //end for
             } //end for


             sort( edges.begin(), edges.end() );

             vector<Edge>::const_iterator vectIt;

             for( vectIt = edges.begin();
                  vectIt != edges.end();
                  vectIt++ )
             {
                cout << vectIt->point1 << " " << vectIt->point2 << " " << vectIt->weight << endl;
              } //end for
         } //end printGraph


        private:
            //This is the adjacency list
            map<char, list<char>> aGraph;

            //This is a list of edges and their weights.
            vector<Edge> edges;
        };  //end Graph

int main()
{

    Graph myGraph;

    myGraph.inputEdge( 'O', 'A', 2 );
    myGraph.inputEdge( 'O', 'B', 5 );
    myGraph.inputEdge( 'O', 'C', 4 );
    myGraph.inputEdge( 'A', 'B', 2 );
    myGraph.inputEdge( 'A', 'D', 7 );
    myGraph.inputEdge( 'B', 'D', 4 );
    myGraph.inputEdge( 'B', 'E', 3 );
    myGraph.inputEdge( 'C', 'B', 1 );
    myGraph.inputEdge( 'C', 'E', 4 );
    myGraph.inputEdge( 'E', 'D', 1 );
    myGraph.inputEdge( 'D', 'T', 5 );
    myGraph.inputEdge( 'E', 'T', 7 );
    myGraph.inputEdge( 'G', 'Z', 8 );

    myGraph.printGraph();

    cout << endl << endl;

    system("PAUSE");
    return 0;
} //end main

Here is the code...

Answer 1

You're working with a const vector, which cannot be sorted. (Or changed).

This is because your function is const:

void printGraph() const

Remove the const so members of your class can be modified (and therefore sorted).

Answer 2

The following code compiles under g++ 4.4.0:

#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    char point1;  
    char point2;  
    int weight;   

    bool operator<( const Edge& rhs ) const {
        return( weight < rhs.weight );
    }
}; 

bool compareEdge( const Edge& lhs, const Edge& rhs ) {
      return( lhs.weight < rhs.weight );
}

int main() {
    vector <Edge> edges;
    sort( edges.begin(), edges.end() );
}

Please test it with your compiler. In general, it would be helpful if you and others posted small complete programs like this which can be easily tested, and which illustrate the problem (or lack of them, in this case).

Answer 3

The code above compiles fine, it looks like you have an assignment problem when trying to assign something to a const Edge.

You don't need to define an assignment operator but you can't assign something to a const Edge.

Answer 4

It looks to me like you're calling std::sort with a std::vector<Edge>::const_iterator instead of a std::vector<Edge>::iterator, probably in graph.cpp line 107.

After seeing the code: The iterators are indeed constant. edges is a member variable of Graph and printGraph is a const method. Therefore edges can't be modified inside of printGraph because the Graph object can't be modified by a const method. Sorting edges would modify it, so it leads to a compiler error.

Answer 5

The printGraph function is declared as a const member function of Graph but you're trying to modify a member variable (the edges vector). Remove the const from the printGraph declaration and the code will compile.

Alternatively make a local copy of the edges vector and sort that before printing it out, since the comments state this function is only for debugging performance shouldn't be a major concern. It's a little misleading for a function called printGraph to be modifying the edges vector anyway.