On Thu, Jun 26, 2008 at 10:51 AM, David Abrahams <dave@boostpro.com> wrote:
But the efficiency is a different issue. It's like the same reason we don't provide random access for list iterators: operator++ on an iterator is supposed to be fundamentally O(1) (notwithstanding filter_iterator -- how do you measure /that/?!)
I am inclined to agree that a fast swap for array is useful and thus should be provided, but I still have a nagging doubt about whether it's "the right thing to do." Maybe I've been brainwashed by a certain disciple of Alex Stepanov's, because nobody else seems to share that doubt... so feel free to ignore me if you're unconvinced.
I think the problem here is that you are talking about a swap operation being a strictly O(1) operation and therefore there shouldn't be an array swap because it would have to be O(n), but the actual underlying problem is that in the context of a generic swap, at least in the sense of std::swap, there simply _is_no_ "n" to even be talking about in a meaningful sense. When working with the STL, we get into the habit of assuming that "n" is always the size of a range we are dealing with and the reason we can do that is because those algorithms are required to be working over a range. In that context, "n" is the size of the range. Again, we are able to do this because being passed a range is a requirement of these algorithms and a range must always have a size. However, in the context of std::swap, this is not the case. std::swap has no requirement that what you pass is some type of container or range. As Neils pointed out earlier: "For a particular template instantiation of boost::swap, for a particular type of arrays, the number of element swaps would be constant. Doesn't that make it O(1)?" What he is saying is perfectly fine because "n" was never appropriately defined before it was decided that swap must be an O(1) operation as opposed to an O(n) operation. So in the general sense, how do you define "n" here? Remember that std::swap may be used with types other than containers (ints, floats, pods, etc.). If you want to state the complexity of a general algorithm, then any variables you refer to (i.e. "n") have to be expressible in terms of the concept requirements of that algorithm. In the context of most STL algorithms we use "n" to mean the size of the range we are operating over, but we can only do that because it is required that a range is passed to those algorithms. With respect to the general concept of a swap, there is no such requirement and so it doesn't make sense to define "n" in that manner. A quick example -- what is the complexity of the swap operation here: _________________________________________________ struct complex_type { /**/ }; struct a { complex_type b, c, d; } left, right; swap( left, right ); _________________________________________________ You would probably say O(1), but then what is the complexity of the same swap done here (assume the above definition of a): _________________________________________________ BOOST_FUSION_ADAPT_STRUCT( a, (complex_type,b)(complex_type,c)(complex_type,d) ) swap( left, right ); _________________________________________________ Did the complexity of the general swap operation now change to O(n) simply because we adapted the struct to be a fusion sequence of size n? No. The fact that it is a sequence is meaningless with respect to the general idea of the swap operation. It's true that because we are using a fusion sequence we can now say "the swap operation in this context is O(n) where n is equal to the size of the fusion sequence being passed," but that doesn't mean that it's an O(n) swap in the general sense of the swap operation because "n" simply has no meaning in the general sense of std::swap. Because of this, I see absolutely no reason why std::swap should not be defined for arrays and boost::array, at least with respect to complexity. -- -Matt Calabrese