I am looking for a review on one of my homework assignments for this semester. This homework has already been submitted and graded and my final has already been submitted so there is no cheating or conflict of interest in my review request! I would love some advice on how to better manage my class interactions and how to better encapsulate data. The specific area I struggle with is when using parent classes and giving access to only protected assets from child classes. My professor has mentioned on several occasions that it would be much better to keep data private and give access through functions, but how would I initialize those member variables when instantiating an instance of a child class that has private members in the parent class? I understand the idea of encapsulation is to protect data that shouldn't be manipulated by outside programmers or irrelevant classes. I was the sole developer on this project so I understand in this specific example encapsulation may not be paramount, but on a larger project with multiple engineers it would certainly be relevant. Includes ``` #include "stdafx.h" #include #include #include using namespace std; ``` ** Note the coordinates struct just contains an integer xCoordinate and an integer yCoordinate main ``` int main() { //Create environment object containing environment antDoodlebugSimulation; antDoodlebugSimulation.InitializeSimulation(); return 0; } ``` Environment ``` class environment { //friends of environment friend class organism; friend class doodlebug; friend class ant; private: organism * environmentBoard[20][20]; void CreateStartPopulation(); int GenerateRandomStartingLocations(int min, int max); void OutputCurrentEnvironment(); void DoodlebugsAct(); void AntsAct(); void ResetCritterTimeStep(); public: //constructor environment(); //deconstructor ~environment(); //public member functions void Initializ

The following C++ code implements the "Genuine Sieve of Eratosthenes" algorithm as described in Melissa O'Neill's classic paper. On my MacBook it computes the first 1,000,000 primes in about 11 seconds. ``` $ ./a.out | head -1000000 | tail -1 15485863 $ ``` Just looking for general code review comments here. At least two parts of `sieverator` smell really bad to me, but I'm not sure of the proper way to fix them while still preserving the general "STLishness" of this code. For example, I really want to keep using the ranged for-loop in `main`. ``` #include #include #include #include #include #include template class iotarator { Int value = 0; Int step = 1; public: explicit iotarator() = default; explicit iotarator(Int v) : value(v) {} explicit iotarator(Int v, Int s) : value(v), step(s) {} Int operator*() const { return value; } iotarator& operator++() { value += step; return *this; } iotarator operator++(int) { auto ret = *this; ++*this; return ret; } bool operator==(const iotarator& rhs) const { return value == rhs.value && step == rhs.step; } bool operator!=(const iotarator& rhs) const { return !(*this == rhs); } }; template class sieverator { struct erased_iterator { virtual Int dereference() = 0; virtual void increment() = 0; }; template class derived_iterator : public erased_iterator { It it; public: derived_iterator(It it) : it(std::move(it)) {} Int dereference() override { return *it; } void increment() override { ++it; } }; Int m_current; std::unique_ptr m_ptr; explicit sieverator() {} // used by .end() public: template explicit sieverator(It it) : m_current(*it), m_ptr(std::make_unique>(std::move(it))) {} sieverator begin() { return std::move(*this); } sieverator end() const { return sieverator{}; } bool operator==(const sieverator&) const { return false; } bool op

Based on Concurrent FIFO in C++11 and my review I implemented a queue and its concurrent pendant. Is there anything left to improve regarding clarity, usability, code-style, lock-times or general efficiency? ``` #ifndef FIFO_H #define FIFO_H #include #include #include #include #include template class ST_FIFO { static_assert(CAPACITY, "Needs to have non-zero capacity"); T data[CAPACITY + 1]; std::size_t input_index = 0; std::size_t output_index = 0; inline static constexpr std::size_t wrap_index(std::size_t index) noexcept { return index > CAPACITY ? index - CAPACITY - 1 : index; } public: static constexpr std::size_t capacity() noexcept { return CAPACITY; } bool empty() const noexcept { return input_index == output_index; } std::size_t size() const noexcept { return input_index >= output_index ? input_index - output_index : input_index + CAPACITY + 1 - output_index; } template auto push(X&& x) noexcept(noexcept(pop(*data), *data = std::forward(x))) -> decltype(*data = std::forward(x), true) { if(size() == CAPACITY) pop(data[input_index]); data[input_index] = std::forward(x); input_index = wrap_index(input_index + 1); return true; } template auto try_push(X&& x) noexcept(noexcept(*data = std::forward(x))) -> decltype(*data = std::forward(x), true) { if(size() == CAPACITY) return false; data[input_index] = std::forward(x); input_index = wrap_index(input_index + 1); return true; } std::size_t multi_push(const T ts[], size_t count) noexcept(noexcept(push(*ts))) { for (size_t i = 0; i = size()) return false; t = data[wrap_index(output_index + ind)]; return true; } }; template class MT_FIFO : ST_FIFO { std::atomic_bool wait_flag = true; mutable std::mutex mutex; mutable std::condition_variabl

After reading Ulrich Drepper's "Futexes are Tricky", I have written the following "dumbest mutex" in C++14 using the Linux `futex` primitives. This mutex is simpler than Drepper's; I believe it to be correct. The reason it gets to be so simple is the same as the reason I'm calling it the "dumbest mutex": it makes a system call on every `unlock`, even if the mutex is not being contended and nobody's waiting for the lock. Therefore this is not a good mutex if you care about performance. My question is: Leaving aside the performance issue, is this a correct mutex? Or does it, like most hand-written concurrency code, have some subtle bug? Stylistic comments are also welcome. ``` #include #include #include #include inline int futex_wait(void *addr, int block_if_value_is) { return syscall(SYS_futex, addr, block_if_value_is, nullptr, nullptr, 0); } inline int futex_wake_one(void *addr) { return syscall(SYS_futex, addr, FUTEX_WAKE, 1, nullptr, nullptr, 0); } class mutex { std::atomic m_state; static constexpr int UNLOCKED = 0; static constexpr int LOCKED = 1; public: constexpr mutex() noexcept : m_state(UNLOCKED) {} bool try_lock() { return m_state.exchange(LOCKED) == UNLOCKED; } void lock() { while (m_state.exchange(LOCKED) != UNLOCKED) { futex_wait(&m_state, LOCKED); } } void unlock() { m_state = UNLOCKED; futex_wake_one(&m_state); } }; ```

This is my implementation of a red-black tree that I'm planning to use in a little personal project. It works fine, however I'm not sure that the code is very good as I'm only a beginner, and insertions are 4x slower than in a broken implementation I found here (it stops working after a few insertions). I was wondering if I did something unnecessary that slows down the algorithm or is it just because my nodes also have keys instead of just data. I'd greatly appreciate any suggestions and corrections. ``` enum Color { Red = 0, Black }; template class RBTree { public: RBTree(); ~RBTree(); void Insert(TKey Key, TData Data); void Delete(TKey Key); TData * Find(TKey Key); private: struct Node { Node(const TKey & Key, const TData & Data, Node * Parent); ~Node(); Color _Color; Node * _Link[2]; Node * _Parent; TKey _Key; TData _Data; }; Node * _Root; }; template inline RBTree::RBTree() : _Root(nullptr) { } template inline RBTree::~RBTree() { delete _Root; } template inline void RBTree::Insert(TKey Key, TData Data) { Node * pNode = nullptr; Node * pParent = nullptr; Node * pUncle = nullptr; Node * pGrandparent = nullptr; Node * T = nullptr; int Dir; int PDir; if (!_Root) { _Root = new Node(Key, Data, nullptr); _Root->_Color = Black; } else { pNode = _Root; while (pNode) { pParent = pNode; Dir = Key > pNode->_Key; pNode = pNode->_Link[Dir]; } pParent->_Link[Dir] = new Node(Key, Data, pParent); pNode = pParent->_Link[Dir]; TKey k; TData d; Node * n; while (pNode->_Parent && pNode->_Parent != _Root && pParent->_Color == Red) { pGrandparent = pParent->_Parent; PDir = pParent->_Data > pGrandparent->_Data; pUncle = pGrandparent->_Link[!PDir];

I'm learning C++ and whilst trying to write in modern C++, I've made an attempt to rewrite a trie implementation written in C found here: http://www.geeksforgeeks.org/trie-insert-and-search/ It uses arrays to hold the branches in each node and because it's C it was done using malloc() and no freeing of memory was done in the example. Is this an efficient approach of representing a trie in C++11? what other ways can I store children in trie nodes? ``` #include #include #include #include class Trie { struct Node; typedef std::unique_ptr spNode; struct Node { std::map children; bool isLeaf; Node() : isLeaf{false} {} }; spNode root; public: Trie(); void insert(const std::string& str); bool search(const std::string& str); }; Trie::Trie():root{nullptr}{} void Trie::insert(const std::string& str) { if (root == nullptr) { std::unique_ptr node(new Node()); root = std::move(node); } Node *temp = root.get(); for (const char& c : str) { if (temp->children.find(c) == temp->children.end()) {//if char not in map std::unique_ptr node(new Node()); temp->children[c] = std::move(node); } temp = temp->children[c].get(); } temp->isLeaf = true; } bool Trie::search(const std::string &str) { if (root == nullptr) return false; Node *temp = root.get(); for (const char& c : str) { if (temp->children.find(c) == temp->children.end()) return false; temp = temp->children[c].get(); } return (temp->isLeaf); } int main (void) { std::string words[] = { "Hello", "hi", "hey", "howdy", "ho"}; Trie test; for (const auto& str : words) { test.insert(str); } if (test.search("Hello")) std::cout << " 'Hello' is found in the trie\n"; else std::cout <<" 'Hello' is not found in the trie\n"; if (test.search("yo")) std::cout << " 'yo' is found in the t

I have made two quite basic algorithms used for lossless data compression. This is my RLE: ``` #include std::string rle(const std::string& input) // encode (aaaaeecd -> 4a2e1c1d) { std::string output; int n = input.size(); int i = 0; while(i aaaaeecd) { std::string output; for(int i = 0; i < input.size(); i += 2) { int nb = (int)(unsigned char)input[i]; // range between 0 and 255 for(int k = 0; k < nb; k++) output += input[i+1]; } return output; } ``` and here goes my MTF: ``` #include #include #include #include /* if alphabet A = {'a', 'b', 'c'} then string "accbc" is encoded 02021 (a is at index 0, alphabet remains {'a', 'b', 'c'}, outputs 0 ; c is at index 2, alphabet becomes {'c', 'a', 'b'}, outputs 2 ; c is at index 0, alphabet remains {'c', 'a', 'b'}, outputs 0 ; b is at index 2, alphabet becomes {'b', 'c', 'a'}, outputs 2 ; a is at index 1, alphabet becomes {'a', 'b', 'c'}, outputs 1) */ std::string mtf(const std::string& input) { std::string output; std::list alphabet; // constant erase/insert for(int i = 0; i alphabet; // constant erase (begin) & operator[] ; insert (middle) is O(n) for(int i = 0; i <= 255; i++) alphabet.push_back((char)i); for(unsigned char n: input) { char temp_c = alphabet[n]; output += temp_c; alphabet.erase(alphabet.begin() + n); alphabet.insert(alphabet.begin(), temp_c); } return output; } ``` I know there are many possible improvments possible, especially for the RLE algorithm. I would just like a review on the C++ syntax I've used, especially on the structures I have chosen.

I attempted to make better Fibonacci sequence calculation algorithm in C++. This was the best I could: ``` constexpr unsigned fibonacci(unsigned n) { unsigned result[2] = {1, 0}; for (unsigned i = 1; i < n; ++i) result[i%2] = result[0] + result[1]; return result[1 - n%2]; } ``` ...which runs at `O(n)` time complexity and `O(1)` space complexity. Is there any better?

I want to change the legacy C-style code by using stl: ``` for (posEmptyItem = startAt; strlen(collection[posEmptyItem]) > 10; posEmptyItem++) {} std::cout << posEmptyItem << std::endl; ``` This code seems a bit hard to read. Anyway to do better? ``` auto it = std::find_if(collection + startAt, collection + COLLECTION_SIZE, [](const char* line) { return strlen(line) <= 10; }); int idx = std::distance(collection, it); ``` Below a complete example: ``` #include #include #include #define COLLECTION_SIZE 250 int main() { const char* collection[COLLECTION_SIZE]{ "time11,time2,time3", "time12,time2,time3", "time13,time2,time3", "time14,time2,time3", "time15,time2,time3", "x\n", "" }; auto startAt = 2; int posEmptyItem; // legacy code for (posEmptyItem = startAt; strlen(collection[posEmptyItem]) > 10; posEmptyItem++) {} std::cout << posEmptyItem << std::endl; // replace the loop to search an index by calling to standard library auto it = std::find_if(collection + startAt, collection + COLLECTION_SIZE, [](const char* line) { return strlen(line) <= 10; }); posEmptyItem = std::distance(collection, it); std::cout << posEmptyItem << std::endl; return 0; } ```

Once again I decided to beat system `memcmp` function. This time I decided to use a template and to "precompile" all cases from 0 to 31 bytes. Result is 400% improvement - from about 1:15 min to 0:25 min. Finally I had rewritten `memcmp_fixed_` with naive looking for statement and I noticed that the compiler can optimize it as well. However I did not tested with random data, so I am not sure what role the cache line and branch predictor plays in the tests. Here is the code: ``` #include #include namespace{ template int memcmp_fixed_(const unsigned char *s1, const unsigned char *s2){ for(size_t i = 0; i int memcmp_fixed_(const unsigned char *s1, const unsigned char *s2){ return *s1 - *s2; } template int memcmp_fixed_(const void *a1, const void *a2){ const unsigned char *s1 = (const unsigned char *) a1; const unsigned char *s2 = (const unsigned char *) a2; return memcmp_fixed_(s1, s2); } } inline int fast_memcmp(const void *a1, const void *a2, size_t const size){ switch(size){ case 0: return 0; case 1: return memcmp_fixed_(a1, a2); case 2: return memcmp_fixed_(a1, a2); case 3: return memcmp_fixed_(a1, a2); case 4: return memcmp_fixed_(a1, a2); case 5: return memcmp_fixed_(a1, a2); case 6: return memcmp_fixed_(a1, a2); case 7: return memcmp_fixed_(a1, a2); case 8: return memcmp_fixed_(a1, a2); case 9: return memcmp_fixed_(a1, a2); case 10: return memcmp_fixed_(a1, a2); case 21: return memcmp_fixed_(a1, a2); case 22: return memcmp_fixed_(a1, a2); case 23: return memcmp_fixed_(a1, a2); case 24: return memcmp_fixed_(a1, a2); case 25: return memcmp_fixed_(a1, a2); case 26: return memcmp_fixed_(a1, a2); case 27: return memcmp_fixed_(a1, a2); case 28: return memcmp_fixed_(a1, a2); case 29: return memcmp_fixed_(a1, a2); case 30: return memcmp_fixed_(a1, a2);