Unordered (unsorted) array

Array:
-  is a collection of data items (its elements) of the same type arranged contiguously in memory
- can be sorted or unsorted
- can accept or not duplicate values

Array is created with predefined size =>
   - if there are less elements than the array size is => memory waste
   - if there are more elements that the array size is => program fails

Implementations:
- C-style array
- std::vector

Unordered arrays with no duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position); it must be checked whether item already exists in the array - a search is performed
- Complexity: O(N) (because of the search)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Unordered arrays with duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position)
- Complexity: O(1)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Write a function which reverses words in a sentence

Algorithm: reverse all characters in the entire sentence and then reverse characters in each word.

Write a function which reverses a string

Algorithm: maintain two pointers - one that goes from the beginning towards the end of the string and another which is going the other way round; each time they move, swap characters at their positions; stop when pointers try to swap their sides;

We can use helper pointer:



Alternatively, we can use just index:

main.cpp:


Output:

Before reversing: ""
After reversing: ""
Before reversing: "a"
After reversing: "a"
Before reversing: "ab"
After reversing: "ba"
Before reversing: "abc"
After reversing: "cba"
Before reversing: "abcdefg"
After reversing: "gfedcba"

Reversing a string can be achieved by using a helper data structure - stack. Algorithm pushes all characters to the stack and then pops them into the new string which has all characters from an original string reversed.

Write a function which returns a length of a given string

Algorithm: find the last character and return the distance between it and the first one.

We can use helper pointer:



Alternatively, we can use just index:

main.cpp:


Output:

String: ""
Length: 0
String: "a"
Length: 1
String: "ab"
Length: 2
String: "abc"
Length: 3
String: "abcdefg"
Length: 7

Parse the following declaration:char (*(*a[4])())[5]

what does this mean char (*(*a[4])())[5]?

The Clockwise/Spiral Rule

cdecl.org

Is there anything you can do in C++ that you cannot do in C?

No.

What is the difference between new/delete and malloc/free?

What is “name mangling”. Differences between C and C++ compilers in terms of it.

What is the difference between external and internal linkage?

What is external linkage and internal linkage in C++? (SO)

Internal linkage: symbol is visible only within compilation unit where it is defined
External linkage: symbols is visible across multiple compilation units

C specific:
- non-static variables and functions have external linkage by default
- static variables and functions have external linkage

C++ specific:
- global variable, function, class, enumeration, namespace have external linkage by default

What does extern "C" int func(int *, Foo) accomplish?

Assuming this is a declaration of function written in C++ code:
It will turn off "name mangling" for this function so that one can link to code compiled by C compiler. (this C++ function can be used in C code)

Assuming func is a function written in C, this is how it should be declared (prototyped) in C++ code so C++ code can invoke this C function.

How do you link a C++ program to C functions?

Compare and contrast C and C++. What are the major differences between C and C++?