CODEWITHSUNDEEP
c++
haohaolee
haohaolee

Reputation: 707

Replace swap implementation for built-in types in C++

I want to change the behavior of std::swap for char type. According to what I have learned, the only a way to do this is to add a template specialization for std::swap, isn't it?

Since char is a built-in type, we have no chance to use ADL.

Please give your advice for such cases.

Edit: Here is the original problem I needed to solve. Random shuffle a string except that non-alpha characters should keep their positions unchanged.

The first thing I want to do is to leverage the std::random_shuffle.

Upvotes: 0

Views: 388

Answers (1)

CygnusX1
CygnusX1

Reputation: 21778

First: Don't do that. You may inadvertently break a different part of code that was previously working.

What you could try is to create your own class, make it hold only a single char element in it and then add any fancy functionality to it that you like. This way you would have your own swap behavior without breaking somebody elses code.

However, if you still want to do that, try the following (running) example:

#include <algorithm>
#include <iostream>

namespace std {
template <>
void swap<char>(char& a, char& b) {
  std::cerr << "Swapped " << a << " with " << b << "\n";
  char t=a;
  a=b;
  b=t;
}
}

int main() {
  char arr[] = {'a', 'z', 'b', 'y'};
  std::reverse(arr, arr+4);
  return 0;
}

Do note that some stl algorithms may be specialized for basic types and not use std::swap at all.

Ad. Edited question:

Fair shuffling algorithm is fairly simple:

for (i = 0 .. n-2) {
  j = random (i .. n-1);  //and NOT random (0 .. n-1)
  swap(array[i], array[j]);
}

however, if you modify swap to prevent the operation when either of the arguments is not alphanumeric (I presume that's what you wanted to change swap into?), the remaining permutation is not going to be fair. With the increasing number of non-alhanumeric characters, the chance that given character won't move - increases. In worst-case scenario, imagine a long string with only two alphanumeric characters - the chance of them getting swapped will be near 0.

If you want to have fair permutation on only non-alpha characters you can do:

a) Pretty straightforward way - extract the alphanumeric characters to separate array, shuffle, and then put them back.

Simple, no performance hit, but needs more memory.

b) If the number of nonalphanumeric characters is relatively low, you can repeat the dice roll:

for (i = 0 .. n-2) {
  if (!alphanumeric(array[i]) continue;
  do {
    j = random (i .. n-1);
  while (!alphanumeric(array[j]));
  swap(array[i], array[j]);
}

This shuffling will be still fair, but will take a lot of time when you have a lot of nonalphanumeric characters.

Upvotes: 2

Related Questions