- Space efficiency when using vectors. - 7 Updates
| Paul <pepstein5@gmail.com>: Dec 05 12:14PM -0800 The quote below is from a book about algorithms in C++, and is discussing representations of graphs. I don't understand what he means by initializing a vector with small capacity. The nearest thing that I'm aware of is the reserve() method. However, that only works to request more capacity, not to limit capacity. I'd be grateful for any explanations. The ways that I'm aware of, for initializing a vector, don't involve the capacity. Thanks, Paul BEGIN QUOTE There are several alternatives for maintaining the adjacency lists. First, observe that the lists themselves can be maintained in either vectors or lists. However, for sparse graphs, when using vectors, the programmer may need to initialize each vector with a smaller capacity than the default; otherwise, there could be significant wasted space. END QUOTE |
| Nobody <nobody@nowhere.invalid>: Dec 05 08:36PM On Sat, 05 Dec 2015 12:14:38 -0800, Paul wrote: Nothing in the standard allows you to initialise a vector with a specific capacity. The closest is to initialise it with a given number of elements, call shrink_to_fit() on it, then clear(). shrink_to_fit() requires C++11, and is a non-binding request to reduce the capacity to match the size. It's possible that on some implementations, creating a vector with an initial set of elements results in the capacity matching the size, even if the default capacity is larger. But that's just an implementation detail. |
| Melzzzzz <mel@zzzzz.com>: Dec 05 09:44PM +0100 On Sat, 5 Dec 2015 12:14:38 -0800 (PST) > programmer may need to initialize each vector with a smaller capacity > than the default; otherwise, there could be significant wasted space. > END QUOTE Well, on systems that overcommit memory, like Linux, this is of no concern, since what is reserved and not touched is never actually allocated. But then again, if memory is of concern one will use more compact data structure. |
| Paul <pepstein5@gmail.com>: Dec 05 12:50PM -0800 On Saturday, December 5, 2015 at 8:44:33 PM UTC, Melzzzzz wrote: > concern, since what is reserved and not touched is never actually > allocated. But then again, if memory is of concern one will use more > compact data structure. Would a list instead of a vector be an example of a "more compact data structure"? Paul |
| "Öö Tiib" <ootiib@hot.ee>: Dec 05 01:28PM -0800 On Saturday, 5 December 2015 22:15:04 UTC+2, Paul wrote: > The quote below is from a book about algorithms in C++, and is discussing representations of graphs. I don't understand what he means by initializing a vector with small capacity. The nearest thing that I'm aware of is the reserve() method. However, that only works to request more capacity, not to limit capacity. I'd be grateful for any explanations. The ways that I'm aware of, for initializing a vector, don't involve the capacity. C++ standard does not specify default capacity for vectors. Most implementations seem to use 0 as default capacity. That makes sense (as cheapest). Not sure what your author means by it. > BEGIN QUOTE > There are several alternatives for maintaining the adjacency lists. First, observe that the lists themselves can be maintained in either vectors or lists. However, for sparse graphs, when using vectors, the programmer may need to initialize each vector with a smaller capacity than the default; otherwise, there could be significant wasted space. > END QUOTE Google indicates that the author of it "Mark Allen Weiss" has published at least two quite identical books: "Data Structures and Algorithm Analysis in Java" and "Data Structures and Algorithm Analysis in C++". That makes it likely that both books are crap. |
| Ian Collins <ian-news@hotmail.com>: Dec 06 10:52AM +1300 Paul wrote: >> allocated. But then again, if memory is of concern one will use more >> compact data structure. > Would a list instead of a vector be an example of a "more compact data structure"? Please try and wrap your lines! The answer to your question is the usual one when discussing data structures: it depends! If the data is sparse, there will be a point where a list is more appropriate. What determines that point depends on the data and the machine the code is running on. A sparse vector may work well with the processor cache where an equivalent list may not. You really need to measure with real data on the intended target to be sure. -- Ian Collins |
| Norman Peelman <npeelman@cfl.rr.com>: Dec 05 06:00PM -0500 On 12/05/2015 04:52 PM, Ian Collins wrote: > machine the code is running on. A sparse vector may work well with the > processor cache where an equivalent list may not. You really need to > measure with real data on the intended target to be sure. Although, Thunderbird has wrapped appropriately above... your lines came across just as long as his did. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment