Implement Transposition cipher in c++

Question

I try to implement the encryption by Columnar transposition.

Input: key_secret and Text_to_encrypt, both of them are in lower.

Output: encrypted_text.

The code works fine but I have some questions:

• it warns: "Function 'begin' could not be resolved", Function 'end' could not be resolved, Function 'copy_if' could not be resolved. How can I get rid of it?
• it creates mapOriginAlphabet slowly. How can I improve it?

I use gcc 5.3.0

Here the code: .h file

#ifndef TRANSPOSITIONCIPHER_H_
#define TRANSPOSITIONCIPHER_H_

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>

#define log(s) std::cout << s << std::endl

class transpositioncipher {
private:
    std::map<char,bool> mapOriginAlphabet;
    std::map<char,char> mapAlphabet;
    std::vector<int> vecOrder;
    std::string mKeySecret;

    std::string removeDuplicates(const std::string strOrigin);
    void createOrder();
    void createSubstitution();

public:
    transpositioncipher(std::string KeySecret);
    virtual ~transpositioncipher();

    std::string encrypt(const std::string strOrigin);
    std::string decrypt(const std::string strOrigin);
    void print();
};

#endif /* TRANSPOSITIONCIPHER_H_ */

.cpp file

#include "transpositioncipher.h"

transpositioncipher::transpositioncipher(std::string KeySecret) {

    mKeySecret = removeDuplicates(KeySecret);
    createOrder();
    for (int i = 97; i < 123; ++i) {
        char c = (char) i;
        std::size_t found = mKeySecret.find(c);
        if (found != std::string::npos) {
            mapOriginAlphabet[c] = false;
        } else {
            mapOriginAlphabet[c] = true;
        }
    }
     createSubstitution();
}

transpositioncipher::~transpositioncipher() {
}

std::string transpositioncipher::removeDuplicates(const std::string strOrigin) {

    std::set<char> moved;
    std::string result;
    result.reserve(strOrigin.size());

    //Only copy one character of each type to the new string
    std::copy_if(std::begin(strOrigin), std::end(strOrigin),
        std::back_inserter(result),
        [&moved](const auto& value) {return moved.insert(value).second;});

     return result;
}

void transpositioncipher::createOrder() {

    std::set<char> chars { mKeySecret.begin(), mKeySecret.end() };

    std::string strTemp = std::string(chars.begin(), chars.end());

    for (auto& x : strTemp) {
        std::size_t found = mKeySecret.find(x);

        vecOrder.push_back(found);
    }

}


void transpositioncipher::createSubstitution() {

    int iCols = mKeySecret.length();
    int iRows = 26 / iCols + 1;

    std::vector<std::vector<char>> vecTemp;

    std::vector<char> vecFirstRow;
    for (auto& x : mKeySecret) {
        vecFirstRow.push_back(x);
    }
    vecTemp.push_back(vecFirstRow);

    int index = 97;
    int iNumRow = 0;

    while (iNumRow < iRows) {
        std::vector<char> row;
        int iNumCol = 0;
        while (iNumCol < iCols) {
            if (mapOriginAlphabet[(char) index]) {
                row.push_back((char) index);
                iNumCol++;
            }
            index++;
            if (index > 123) {
                break;
            }
        }
        vecTemp.push_back(row);
        iNumRow++;
    }

    index = 97;
    for (auto& indexCol: vecOrder) {
        for (auto& vec: vecTemp) {
            if (indexCol >= vec.size())
                continue;
            else {
                mapAlphabet[(char)index] = vec.at(indexCol);
                index ++;
            }
        }
    }
}

std::string transpositioncipher::encrypt(const std::string strOrigin) {
    std::string ret;
    for (auto& x: strOrigin) {
        ret += mapAlphabet[x];
    }

    return ret;
}

Answer 1

I see a number of things that may help you improve your code.

Fix the formatting

The code has an inconsistent format, with varying indentation and brace placement. To make your code easier to read, you should choose a style and apply it consistently.

Avoid confusing branching constructs

The code currently contains this:

for (auto& vec: vecTemp) {
    if (indexCol >= vec.size())
        continue;
    else {
        mapAlphabet[(char)index] = vec.at(indexCol);
        index++;
    }
}

(with the formatting fixed). There are several problems with this. The first is that the control flow is confusing. It can be made much simpler:

for (auto& vec: vecTemp) {
    if (indexCol < vec.size()) {
        mapAlphabet[(char)index] = vec.at(indexCol);
        index ++;
    }
}

Use appropriate types for variables

The next problem with that code is that it uses an old C-style cast to turn index into a char. In fact, it's cast to a char just about every time it's used. Why not just declare it as a char in the first place and remove the casts?

Eliminate "magic numbers"

Instead of using numbers such as 97 and 123 as with this code:

for (int i = 97; i < 123; ++i) {
    char c = (char) i;
    std::size_t found = mKeySecret.find(c);

it would make the code a lot easier to understand if we used the appropriate type of variable and used character constants like this:

for (char c = 'a'; c <= 'z'; ++c) {
    std::size_t found = mKeySecret.find(c);

Use boolean results directly

Rather than this:

std::size_t found = mKeySecret.find(c);
if (found != std::string::npos) {
    mapOriginAlphabet[c] = false;
} else {
    mapOriginAlphabet[c] = true;
}

The code would be much shorter and clearer written like this:

bool found = mKeySecret.find(c) != std::string::npos;
mapOriginAlphabet[c] = !found;

Or possibly this:

mapOriginAlphabet[c] = mKeySecret.find(c) == std::string::npos;

Understand standard template library containers

The code for encrypt contains these lines:

for (auto& x: strOrigin) {
    ret += mapAlphabet[x];
}

This seems to do the right thing, but in fact, it inserts non alphabetic characters into the mapAlphabet which is not the desired behavior here. Instead, you should use mapAlphabet.at(x) like this:

for (const auto& x: strOrigin) {
    try {
        ret += mapAlphabet.at(x);
    } catch (std::exception &e) {
        // ignore out of range inputs
    }
}

Use const where practical

Performing an encryption or decryption with a given keyword should not alter the underlying transpositioncipher object, so those should be made const.

Prefer const & as function arguments

Several of the functions take a std::string as an argument, but should probably be const std::string & instead to avoid the pointless duplication of a string. The constructor and removeDuplicates are two such places, as are encrypt and decrypt.

Re-examine your algorithm

What you have implemented is not a transposition cipher, but a substitution cipher in which the ciphertext alphabet is derived by a transposition. Encryption and decryption could be done with an inverse pair of std::unordered_map objects which may give slightly better performance.

Don't keep variables that are not needed

The vecOrder and mapOriginAlphabet variables are only need during object construction, so they should not be permanent data members of the object. They could be created and destroyed as the map is being constructed. Better yet, don't use them at all, as shown in the next suggestion.

Rethink your algorithm

Ultimately, the goal of the constructor is to create a substitution map based on the keyword. The procedure is to eliminate duplicate letters in the keyword and then to create a table that includes all of the letters, rearranged according to the keyword. For example, the keyword "bongo" would be reduced to "bngo" and then your vecTemp would look like this:

'b', 'o', 'n', 'g', 
'a', 'c', 'd', 'e', 
'f', 'h', 'i', 'j', 
'k', 'l', 'm', 'p', 
'q', 'r', 's', 't', 
'u', 'v', 'w', 'x', 
'y', 'z', 

We then read down the columns according to the alphabetic order of the letter at the top of each column and create the substitution map:

a = b
b = a
c = f
d = k
e = q
f = u
g = y
h = g
i = e
j = j
k = p
l = t
m = x
n = n
o = d
p = i
q = m
r = s
s = w
t = o
u = c
v = h
w = l
x = r
y = v
z = z

I think that if you ponder it a while longer, there is perhaps a more direct way to derive the map. Instead, you could start with something like this:

std::string &delete_duplicates(std::string &str, size_t len) {
    for (size_t i=0; i < len; ++i) {
        str.erase(std::remove(str.begin()+i+1, str.end(), str[i]),
            str.end());
    }
    return str;
}

Then in the constructor, you could have this:

delete_duplicates(keyword, keyword.size());
std::string alphabet{keyword + "abcdefghijklmnopqrstuvwxyz"};
delete_duplicates(alphabet, keyword.size());

That gives the linear string that represents the two dimensional array shown above. Remap them into vector of strings and sort:

std::vector<std::string> columns(keyword.size());
for (size_t i=0, col=0; i < alphabet.size(); ++i) {
    columns[col++] += alphabet[i];
    if (col >= columns.size()) {
        col = 0;
    }
}
std::sort(columns.begin(), columns.end());
// now replace the alphabet
alphabet.clear();
for (auto &word : columns) {
    alphabet += word;
}

Now you can construct an encryption map (and a decryption map, if you like) by simply linearly assigning each letter of the "new" alphabet.

Answer 2

Choose appropriate data structures

Essentially anywhere a map<T, bool> (for some arbitrary type T) can be used, a set<T> will probably do the job, unless you really need to differentiate between three states: not present, present but false, and and present and true. I don't think that's the case here though, so mapOriginalAlphabet can probably become a set (or unordered_set).

A set, however, is basically just a way of creating a sparse matrix of bool. That is, it stores the values for which the bool should be true. If the set of values is dense (that is, the number used is fairly large in proportion to the range of possible values) it can make more sense to just store a vector<bool> (or, due to the odd specialization on that type, possibly a deque<bool> or vector<char>, where chars are used to store only two values meaning true and false).

In a typical case, this is a trade-off between memory usage and speed. If we store the values densely, we save storage at the expense of extra CPU time. If we store the whole sparse matrix, access is faster but we use extra memory.

In this case, however, the range of values is only the 26 lower-case letters. It's trivial to store the whole sparse matrix in only 26 bytes--less than a sparse matrix is likely to use--so just using an array gives us fast access and fairly minimal memory usage (though if we really cared, we could compress it down to one bit per bool, and store all the values in a 32-bit integer).

Include the headers needed for what you use

You haven't included either <vector> or <iterator> (but you use things that are declared in them).

Consider using a namespace

It seems to me that if you're using such things, it would make sense to have a cipher namespace, with members like transposition, substitution, and so on.

namespace cipher { 
    class Substitution {
        // ...
    };
}

Note: quite a few people do not indent members of namespaces. I did here, but it's not really mandatory like other indentation is (nudge, nudge).

Naming

The Hungarian Notation-like warts on variable names strike me as ugly, and if they're at all useful it's a strong indication of other problems with the code.

Use Meaningful Initialization

When at all reasonable, try to initialize things to the value they'll contain, rather than (for example) using default initialization and then putting the required values into them. For example:

std::vector<char> vecFirstRow;
for (auto& x : mKeySecret) {
    vecFirstRow.push_back(x);
}

...can be written something like:

std:vector<char> vecFirstRow{mKeySecret.begin(), mKeySecret.end()};

or:

std:vector<char> vecFirstRow{ std::begin(mKeySecret), std::end(mKeySecret)};

The latter (std::begin and std::end) is particularly useful for generic code that might receive an array rather than a container that defines begin and end members.

Appropriate Algorithms

This is probably at least part of what you were really asking about.

void transpositioncipher::createOrder() {   
    std::set<char> chars{ mKeySecret.begin(), mKeySecret.end() };
    std::string strTemp = std::string(chars.begin(), chars.end());

    for (auto& x : strTemp) {
        std::size_t found = mKeySecret.find(x);    
        vecOrder.push_back(found);
    }
}

Despite use of a map, this is an \$O(N^2)\$ algorithm. You're creating a collection of the unique characters in the input string, but then doing a linear search in the original string to find the position of each to put into the result.

Instead, I'd build a map of the unique characters and their positions in the string, then use that to create the result:

void transpositioncipher::createOrder() {
    using T = std::string::size_type;
    std::map<char, T> positions;

    // Note that insert will fail if a character is already present, so this records the
    // position of the first occurrence of each character.
    for (T i = 0; i < mKeySecret.size(); i++)
        positions.insert(std::make_pair(mKeySecret[i], i));

    // Now walk through the characters in alphabetical order and copy their positions
    // To the output.   
    for (auto pos : positions)
        vecOrder.push_back(pos->second);
}

Here we depend on the order of a map to create the output in the correct order, so we can't use unordered_map instead.

There are also a few cases where it might be appropriate to consider using a standard algorithm instead of an explicit loop. For one obvious example:

std::string ret;
for (auto& x : strOrigin) {
    ret += mapAlphabet[x];
}

Could be done as something like:

std::transform(strOrigin.begin(), strOrigin.end(), 
               std::back_inserter(ret),
               [&](char c) { return mapAlphabet[c]; });

This one is open to a lot of argument though--unless you're quite accustomed to using standard algorithms, it may not be an improvement.

Answer 3

I'd like to thank you for my learning experience in answering this question. It required me to do some new research on the internet.

Inappropriate for Code Review Questions
It would be better not to include any debugging code in the question, especially macros in C++11 or C++14. The header file contains the following code that is not used by the program:

#define log(s) std::cout << s << std::endl

Including debugging code indicates there are errors in the code. The rules on code review are that only working code can be included so debugging code might get the question put on hold.

Indenting Code
This may be a by product of how the code was entered but the code is almost unreadable due to the inconsistent nature of indenting.

MAGIC_NUMBERS
Raw numeric constants in code are sometimes called Magic Numbers (additional reference here).

This term was coined because anyone reading the code or maintaining the code has no clue what the number represents. The code is more readable and maintainable if the numbers are replaced by symbolic constants.

The code becomes much more maintainable with symbolic names not only because it is more readable, but if the number has to change it can be changed in only one place rather than in multiple places in the code.

Examples of Magic Numbers in the code are:
97 (occurs 3 times in the code, no clue what it means) 123 (occurs 2 times in the code, no clue what it means) 26 (occurs once in the code, could mean the number of letters in the alpahbet).

Examples of Symbolic Names for Numeric Constants:

constexpr int ALPHABET_SIZE = 26;    // [defines ALPHABET_SIZE at compile time][4]
const int ALPHABET_SIZE = 26;        // defines ALPHABET_SIZE at run time.

Default Destructors
In the header file the code contains

    virtual ~transpositioncipher();

and in the CPP file the code contains

transpositioncipher::~transpositioncipher() {
}

Since C++11 this can be replaced by a default constructor in the header file

    virtual ~transpositioncipher() = default;

The compiler will generate any necessary code for the destructor when the default destructor is used.

Casting in C++
Static, Dynamic and reinterpret_cast casts are preferred over old style C Casting. Old style C Casting is not type safe, static and dynamic casts are type safe. Type checking is performed at compile time for static casts and at run time for dynamic casts.

Use

    for (int i = 97; i < 123; ++i) {
        char c = static_cast<char>(i);

instead of

    for (int i = 97; i < 123; ++i) {
        char c = (char) i;    // Old style C Cast

Use the KISS Programming Principle
As a suggestion always treat compiler warning messages as compiler errors. A compiler warning message is suggesting that even though the code compiles it may not run properly.

The KISS principle is that code should be kept as simple as possible and not over engineered.

The function below removeDuplicates() is overly complicated. std::string transpositioncipher::removeDuplicates(const std::string strOrigin) {

    std::set<char> moved;
    std::string result;
    result.reserve(strOrigin.size());

    //Only copy one character of each type to the new string
    std::copy_if(std::begin(strOrigin), std::end(strOrigin),
            std::back_inserter(result),
            [&moved](const auto& value) {return moved.insert(value).second;});

    return result;
}

The std::set moved isn't needed, the condition for the copy_if() can and should be defined in terms of the result string. result.find(value) will provide the necessary condition.

I believe (sorry, not sure) that part of the warning message is because the code is ignoring the return value from the copy_if(). Rather than doing

    result.reserve(strOrigin.size());

You can use the return value of copy_if() to resize the string after the algorithm is done. This has the benefit of reducing the size of the result to only the contents transferred.

Untested alternate removeDuplicates():

std::string transpositioncipher::removeDuplicates(const std::string strOrigin) {
    std::string result;

    //Only copy one character of each type to the new string
    auto it = std::copy_if(std::begin(strOrigin), std::end(strOrigin),
            result.begin(),
            [&result](char value) { return (std::string::npos == result.find(value)); };
    result.resize(std::distance(result.begin(), it);

    return result;
}

Why is My Code Slow
The number of loops in the following code, and the functions it calls in all probability contribute to the performance or lack thereof. Keep in mind that find(), find_if(), initialization using CONTAINER.begin(), CONTAINER.end() all use loops at some level in their implementation.

transpositioncipher::transpositioncipher(std::string KeySecret) {

    mKeySecret = removeDuplicates(KeySecret);
    createOrder();
    for (int i = 97; i < 123; ++i) {
        char c = (char) i;
        std::size_t found = mKeySecret.find(c);
        if (found != std::string::npos) {
            mapOriginAlphabet[c] = false;
        } else {
            mapOriginAlphabet[c] = true;
        }
    }
    createSubstitution();
}