RE: [Boost-users] Library array
Dave
I do have one question about the array library. In the documentation, the statement is made that the advantage array has over vector is the fact that since vectors provide the semantics of dynamic arrays, "This results in some overhead in case only arrays with static sizes are needed.". When discussing this with my peers, I'd like to present something a little more concrete to them.
If I have a number of elements that is known at compile time, why, *specifically*, should I prefer boost::array to std::vector?
The array is stored inside the class instance rather than separately allocated from the heap. There is no need for additional pointer and size member data. This saves time and memory. Many member functions are trivial because of the fixed size. This also saves time. The array size is exactly what you specify, whereas std::vector may round up the size of its internal array to allow for some growth. This saves memory. There may also be a reduction in mental overhead because you will never have to think about the possibility of the array size changing. One disadvantage is that you can catch a failed heap allocation whereas a failed automatic allocation is normally fatal. Allocating large arrays in automatic storage remains a bad idea. Ben.
I have a proble with bfs example of graph library. first I write this code typedef adjacency_list < vecS, vecS, bidirectionalS > graph_t; // Set up the vertex IDs and names enum { r, s, t, u, v , N}; const char *name = "rstuv"; // Specify the edges in the graph typedef std::pair < int, int >E; E edge_array[] = { E(0, 2), E(0,3) , E(3, 1), E(2, 3), E(3, 4)}; // Create the graph object and the result (order of visit ) was 0 -> 2-> 3 ->1 ->4 which true. Second I only modified the rank of an edge E edge_array[] = { E(0,3) ,E(0, 2), E(3, 1), E(2, 3), E(3, 4)}; and I got a wrong order 0->3 ->2->1->4 Normally , the edge rank don't have any influence on the result?????????????????????? Cheers
Hi Adel, On Tue, 11 Nov 2003, adel essafi wrote: adel.e> I have a proble with bfs example of graph library. adel.e> first I write this code adel.e> typedef adjacency_list < vecS, vecS, bidirectionalS > graph_t; adel.e> // Set up the vertex IDs and names adel.e> enum { r, s, t, u, v , N}; adel.e> adel.e> const char *name = "rstuv"; adel.e> // Specify the edges in the graph adel.e> typedef std::pair < int, int >E; adel.e> E edge_array[] = { E(0, 2), E(0,3) , E(3, 1), E(2, 3), E(3, 4)}; adel.e> // Create the graph object adel.e> and the result (order of visit ) was 0 -> 2-> 3 ->1 ->4 which true. adel.e> adel.e> Second I only modified the rank of an edge adel.e> E edge_array[] = { E(0,3) ,E(0, 2), E(3, 1), E(2, 3), E(3, 4)}; adel.e> adel.e> and I got a wrong order 0->3 ->2->1->4 adel.e> Normally , the edge rank don't have any influence on the adel.e> result?????????????????????? I'm not sure what you mean by "edge rank"... the change above just reorders the edges. Also, what you mean by "wrong order". What is wrong about that order? To me it looks like a void breadth-first traversal. To quote the docs on the definition of breadth-first: A breadth-first traversal visits vertices that are closer to the source before visiting vertices that are further away. In this context ``distance'' is defined as the number of edges in the shortest path from the source vertex. There are many possible valid BFS traversals of a given graph. The order for visiting adjacent vertices is not specified. So from 0, either 2 or 3 is a fine choice for the next visit. The BGL implementation arbitrarily chooses a particular order, which has to do with the order provided by the out_edge_iterator implementation for the particular graph type. Hope that helps, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
On Tue, 11 Nov 2003, Jeremy Siek wrote: jsiek> jsiek> I'm not sure what you mean by "edge rank"... the change above just jsiek> reorders the edges. jsiek> jsiek> Also, what you mean by "wrong order". What is wrong about that order? To jsiek> me it looks like a void breadth-first traversal. To quote the docs on ^^^^ should be "valid" jsiek> the definition of breadth-first: jsiek> jsiek> A breadth-first traversal visits vertices that are closer to the source jsiek> before visiting vertices that are further away. In this context jsiek> ``distance'' is defined as the number of edges in the shortest path from jsiek> the source vertex. jsiek> jsiek> There are many possible valid BFS traversals of a given graph. The order jsiek> for visiting adjacent vertices is not specified. So from 0, either 2 or 3 jsiek> is a fine choice for the next visit. The BGL implementation arbitrarily jsiek> chooses a particular order, which has to do with the order provided by the jsiek> out_edge_iterator implementation for the particular graph type. ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
this is my graph 0 / \ 3 <---- 2 \ 1 | 4 what is the algorithme that allow me to visit vertices 0 -> 2 -> 3 -> 1 -> 4. A virtice is not visited if all vis patent are visited. I forgot his name. Cheers.
Sorry, I do not know of such an algorithm. On Tue, 11 Nov 2003, adel essafi wrote: adel.e> this is my graph adel.e> 0 adel.e> / \ adel.e> 3 <---- 2 adel.e> \ adel.e> 1 adel.e> | adel.e> 4 adel.e> what is the algorithme that allow me to visit vertices 0 -> 2 -> 3 -> 1 -> adel.e> 4. A virtice is not visited if all vis patent are visited. adel.e> I forgot his name. adel.e> Cheers. ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
participants (3)
-
adel essafi -
Ben Hutchings -
Jeremy Siek