#dequeue in c using arrays | Explore Tumblr posts and blogs

sanesquaregg · 3 years ago

Text

The Collection Framework in Java

What is a Collection in Java?

Java collection is a single unit of objects. Before the Collections Framework, it had been hard for programmers to write down algorithms that worked for different collections. Java came with many Collection classes and Interfaces, like Vector, Stack, Hashtable, and Array.

In JDK 1.2, Java developers introduced theCollections Framework, an essential framework to help you achieve your data operations.

Why Do We Need Them?

Reduces programming effort & effort to study and use new APIs

Increases program speed and quality

Allows interoperability among unrelated APIs

Reduces effort to design new APIs

Fosters software reuse

Methods Present in the Collection Interface

NoMethodDescription1Public boolean add(E e)To insert an object in this collection.2Public boolean remove(Object element)To delete an element from the collection.3Default boolean removeIf(Predicate filter)For deleting all the elements of the collection that satisfy the specified predicate.4Public boolean retainAll(Collection c)For deleting all the elements of invoking collection except the specified collection.5Public int size()This return the total number of elements.6Publicvoid clear()This removes the total number of elements.7Publicboolean contains(Object element)It is used to search an element.8PublicIterator iterator()It returns an iterator.9PublicObject[] toArray()It converts collection into array.

Collection Framework Hierarchy

List Interface

This is the child interface of the collectioninterface. It is purely for lists of data, so we can store the ordered lists of the objects. It also allows duplicates to be stored. Many classes implement this list interface, including ArrayList, Vector, Stack, and others.

Array List

It is a class present in java. util package.

It uses a dynamic array for storing the element.

It is an array that has no size limit.

We can add or remove elements easily.

Linked List

The LinkedList class uses a doubly LinkedList to store elements. i.e., the user can add data at the initial position as well as the last position.

It allows Null insertion.

If we’d wish to perform an Insertion /Deletion operation LinkedList is preferred.

Used to implement Stacks and Queues.

Vector

Every method is synchronized.

The vector object is Thread safe.

At a time, one thread can operate on the Vector object.

Performance is low because Threads need to wait.

Stack

It is the child class of Vector.

It is based on LIFO (Last In First Out) i.e., the Element inserted in last will come first.

Queue

A queue interface, as its name suggests, upholds the FIFO (First In First Out) order much like a conventional queue line. All of the elements where the order of the elements matters will be stored in this interface. For instance, the tickets are always offered on a first-come, first-serve basis whenever we attempt to book one. As a result, the ticket is awarded to the requester who enters the queue first. There are many classes, including ArrayDeque, PriorityQueue, and others. Any of these subclasses can be used to create a queue object because they all implement the queue.

Dequeue

The queue data structure has only a very tiny modification in this case. The data structure deque, commonly referred to as a double-ended queue, allows us to add and delete pieces from both ends of the queue. ArrayDeque, which implements this interface. We can create a deque object using this class because it implements the Deque interface.

Set Interface

A set is an unordered collection of objects where it is impossible to hold duplicate values. When we want to keep unique objects and prevent object duplication, we utilize this collection. Numerous classes, including HashSet, TreeSet, LinkedHashSet, etc. implement this set interface. We can instantiate a set object with any of these subclasses because they all implement the set.

LinkedHashSet

The LinkedHashSet class extends the HashSet class.

Insertion order is preserved.

Duplicates aren’t allowed.

LinkedHashSet is non synchronized.

LinkedHashSet is the same as the HashSet except the above two differences are present.

HashSet

HashSet stores the elements by using the mechanism of Hashing.

It contains unique elements only.

This HashSet allows null values.

It doesn’t maintain insertion order. It inserted elements according to their hashcode.

It is the best approach for the search operation.

Sorted Set

The set interface and this interface are extremely similar. The only distinction is that this interface provides additional methods for maintaining the elements' order. The interface for handling data that needs to be sorted, which extends the set interface, is called the sorted set interface. TreeSet is the class that complies with this interface. This class can be used to create a SortedSet object because it implements the SortedSet interface.

TreeSet

Java TreeSet class implements the Set interface it uses a tree structure to store elements.

It contains Unique Elements.

TreeSet class access and retrieval time are quick.

It doesn’t allow null elements.

It maintains Ascending Order.

Map Interface

It is a part of the collection framework but does not implement a collection interface. A map stores the values based on the key and value Pair. Because one key cannot have numerous mappings, this interface does not support duplicate keys. In short, The key must be unique while duplicated values are allowed. The map interface is implemented by using HashMap, LinkedHashMap, and HashTable.

HashMap

Map Interface is implemented by HashMap.

HashMap stores the elements using a mechanism called Hashing.

It contains the values based on the key-value pair.

It has a unique key.

It can store a Null key and Multiple null values.

Insertion order isn’t maintained and it is based on the hash code of the keys.

HashMap is Non-Synchronized.

How to create HashMap.

LinkedHashMap

The basic data structure of LinkedHashMap is a combination of LinkedList and Hashtable.

LinkedHashMap is the same as HashMap except above difference.

HashTable

A Hashtable is an array of lists. Each list is familiar as a bucket.

A hashtable contains values based on key-value pairs.

It contains unique elements only.

The hashtable class doesn’t allow a null key as well as a value otherwise it will throw NullPointerException.

Every method is synchronized. i.e At a time one thread is allowed and the other threads are on a wait.

Performance is poor as compared to HashMap.

This blog illustrates the interfaces and classes of the java collection framework. Which is useful for java developers while writing efficient codes. This blog is intended to help you understand the concept better.

At Sanesquare Technologies, we provide end-to-end solutions for Development Services. If you have any doubts regarding java concepts and other technical topics, feel free to contact us.

0 notes

jaq-h · 5 years ago

Text

While studying computer science at University of Colorado Boulder, my data structures final project was to investigate different priority queue implementations to store the same data and compare their runtime when enqueuing and dequeuing elements. The data in this project was a list of hospital patients with a name, priority, and operation time. The priority of the patient represents the time until the patient goes into labor. The patients were ordered to have lowest priority first, and then ordered by least operation time if the patients had the same priority. The three implementations were a binary heap, linked list, and the c++ standard template library priority queue.

The binary heap priority queue uses an array to store the data while ordering the data in minimum heap property; every parent node is smaller than its child node. The binary heap insert function uses a swap helper function to keep swapping the inserted value with its greater child until the inserted value satisfies the min heap property. The dequeue function removes the root element because it is always the minimum and replaces it with the last element in the heap to keep the tree complete. The heap is then “heapified” or reordered to ensure the root is still the minimum value and the heap follows the min heap property.

The linked list priority queue uses a patient node structure that contains the address to the next priority element. The insert function traverses the list linearly until the inserted element is correctly ordered by its priority. The delete minimum function is very simple because the minimum is always stored at the head of the list so the function reassigns the head of the list to the second element and deletes the first element.

The standard template priority queue was implemented by creating a comparator struct and vector of the elements being prioritized. We do not necessarily know how the queue works because its source code is not available, but we can compare its runtime to the other implementations of the priority queue.

To test each implantation, the data was read into a array for quick access. A random section of the data with a specific size (100, 200… 800) was then copied into a new array. The different sized and random arrays were then enqueued and dequeued with the three priority queues. To calculate the runtime for enqueuing and dequeuing, the time in milliseconds was recorded before and after the loop with the function call and then stored in a matrix. The mean and standard deviations were then calculated for each queue and respective functions.

The code along with the data, charts and graphs for the mean enqueue and dequeue (writeup.pdf) can be found here on my github: https://github.com/jaq-h/priorityQueue

0 notes

huydx · 5 years ago

Text

Understand about how to implement (fast) queue (#1)

Background

(I tried to write this blog post in Vietnamese, but after write half of the blog, I realized that half of written text is in english (ﾉﾟ0ﾟ)ﾉ~ ..)

Recently I wanted to understand better about queue, and how to make a better "unbounded, thread safe queue". If you don't know about queue, you could understand queue as a main data structure to share "work load" or "task" (in another word, producer consumer problem).

My system is written mostly in go. As a go user, the very obvious way to implement unbounded, thread safe is to use go channel

Go channel will serve us very well in most cases and workload, it's not very fast. The problem of slow throughput is pretty obvious since go channel using many centralize lock object, which cause much contention to happen. There is one way to resolve the problem (we're using this method), is to batch the workload into bigger one, to reduce queue contention.

However, since we're still happy with batched workload and go channel, the problem here is very interesting, so I'm realize that thread safe, bounded queue implementation is indeed very interesting topic because it touches many interesting fields in computer science. So that is, that's why I tried to write this blog series.

Implement a queue, why it's hard?

Some simple googling how to implement high performance queue bring me to go github discussion of whether to add decent implementation of unbounded queue to std (container/queue) or not.

The discussion could be summarized into few ideas of why making a queue is hard?:

Variation of situation we would want to use the queue (MPMC, SPMC, MPSC, SPSC)

Variation of features we would the queue to support (push-front or not (dequeue vs queue)? lock-free or not? performance requirement?)

Since we don't want a slow queue, let's presume we want to make it as fast as possible. There are multiple ways to implement a queue:

Linked list

Flat slice or Ring buffer (both could be implemented using array)

Linked-list implementation bring some advantages:

Better lock contention (since the lock contention is only high on tail or head (not both)

Dynamic resizing (since add / remove node require alloc/dealloc a single node only)

However it come in disadvantages:

Memory usage (need 64 bit pointer memory for singly linked-list and 128 bit pointer for doubly linked list per node)

Memory fragment (since alloc happen in realtime, the memory of nodes will not be continuous obviously)

GC pressure (since we will have a lot of pointers to manage, more pointers, more pressure for GC language (java/go))

In opposite, array-backed implementation has totally opposite advantage / disadvantage

Bad: Harder lock method (since we may need to lock the whole array for each enqueue / dequeue ))

Bad: Resizing cost. Most decent resizing method is to double array every time we short of memory, but that will cause high memcopy cost (which is linear to element count).

Good: Contiguous array make a very well performance tradeoff utilizing CPU cache line characteristic. And using array reduce GC pressure a lot, since we only have to manage single pointer of array head.

Grasp some ideas from the giants

Find the optimized implementation that could minimize above disadvantages is hard. Let's see how de-facto implementations of few major languages are doing it. TL;DR most of standard libs don't fancy trick, they just try to do very decent implementation that is bug free and fast enough for most of the cases.

Java's LinkedBlockingQueue

In my daily job, the most queue implementation i've been using is java std LinkedBlockingQueue.

As explained in source code, the queue implementation based on a technique called "two lock queue" with LinkedList backed queue.

https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java#L83-L93

A variant of the "two lock queue" algorithm. The putLock gates entry to put (and offer), and has an associated condition for waiting puts. Similarly for the takeLock.

The comment explain it all, we use 2 lock to control the the queue. putlock used to control write (enqueue) path, and takeLock used to control read (dequeue) path. The origin paper is here: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms .

public boolean offer(E e) { ..... putLock.lock(); try { if (count.get() < capacity) { enqueue(node); .... } } finally { putLock.unlock(); } } public E take() throws InterruptedException { takeLock.lockInterruptibly(); try { x = dequeue(); ... } finally { takeLock.unlock(); } return x; }

The good thing of queue (compare to stack) is that the concern for read and write is separated, we have 2 different object head and last to control read and write path, we could just easily separate lock for those.

Beside the two-lock technique, the implementation also has some fine-grain control method to reduce lock time. One of the method is to control number of remain items so when producer side call offer (or put), it could signal on-waiting take (or poll) right away. The idea is written in source code as below:

to minimize need for puts to get takeLock and vice-versa, cascading notifies are used. When a put notices that it has enabled at least one take, it signals taker. That taker in turn signals others if more items have been entered since the signal. And symmetrically for takes signalling puts.

private final Condition notEmpty = takeLock.newCondition(); public boolean offer(E e) { ..... if (c == 0) notEmpty.signal(); ..... } public E take() throws InterruptedException { ..... try { while (count.get() == 0) { notEmpty.await(); } x = dequeue(); .... } .... }

So that is, LinkedBlockingQueue idea is so simple. To use the queue as MPMC task queue, LinkedBlockingQueue is definitely better than other implementation like ArrayBlockingQueue, since ArrayBlockingQueue try to lock the whole queue for every single put or take.

LinkedBlockingQueue serves us very well for years, even for now. LinkedBlockingQueue is also very convenient in term of specification, since it block consumer or producer when the queue is empty or full, which reduce cost for us to implement to spin wait ourself. However the question still remain, do we have better idea or implementation, which will be talked at next part of this serie, so stay tune :).

1 note · View note

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

You have been hired by a major supermarket chain to model the operation of a proposed supermarket by using a Discrete Event Simulation. The shop has several servers (or checkouts), each of which has a different level of efficiency due to the experience of the server operator. It also takes longer to serve credit card customers. The service time of each customer is calculated as follows: service_time = (tally_time x efficiency) + payment_time where: tally_time: time it takes to tally up the customer's goods efficiency: the efficiency of the server payment_time: 0.3 for cash or 0.7 for credit card The input file “ass2.txt” contains the records of each customer entering the shop and consist of: arrival time (at the server queue), tally time (time it takes to scan the customer's items and add up the cost) payment method (cash or card). Your program should: Open the text file “ass2.txt” (Note: “ass2.txt” should be a hardcoded as a constant.) 2. Read the efficiencies of each server. Read and process the customer arrival and service time data. Print service statistics on the screen. Note: This shop has a single queue of customers waiting to be served. The servers are initially all idle. If more than one idle server is available, the next customer is served by the server with the best efficiency (i.e. the smallest efficiency value). Customers must be served or queued in the order in which they arrive. You should not attempt to read in all the arrival data at the start of the simulation. At the end of the simulation, after the last customer in the file has been served, your program should print out the following information: The number of customers served. The time that it took to serve all the customers. The greatest length reached by the customer queue. The average length of the customer queue. The average time spent by a customer in the customer queue. (If a customer is served immediately, their queue time is 0.0). The percentage of customers who’s waiting time in the customer queue was 0 (zero). For each server: The number of customers they served The time they spent idle. You must choose appropriate data structures and algorithms to accomplish this task quickly. You will lose marks if you use STL, or equivalent libraries, to implement data structures or algorithms. Note: A larger input data file may be used for the final assessment of your program.

Step-1 (Week-7 demo, 2 marks)

For step 1 you are to implement the simulator’s customer queue and event queue. Implement the customer queue (FIFO queue). It should have a maximum size of 500 records. Each record in the customer queue should contain two doubles and a boolean (i.e. arrival time, tally time and payment method). Your customer queue should have functions for adding an item (enqueue), removing an item (dequeue), and for testing if the queue is empty. (Note: C++ and Java coders should also add a constructor for initialsing the queue.) FIFO Queue

Test your customer queue by declaring an instance of it in the main(). Use a for loop to add 10 records to the queue. Set the arrival time for each record between 1 and 100 using rand() or random(). The other fields can be set to 0 or false. Also, print the arrival times on the screen as you add them. Now use a while loop to remove all the records from the customer queue and print the arrival times on the screen. Is the output correct? Now implement the simulator's event queue (i.e. a priority queue). The event queue’s records should contain an event type (int or enum), event time & tally time (doubles), and payment method (boolean). You can assume the maximum number of events in the event queue is 100. The record with the minimum event time has the highest priority.

Test the event queue by declaring an instance of it in the main(). Use the while loop (implemented previously) to remove records from the customer queue and add them to the event queue. Set the event time with the customer's arrival time. Set the other fields to zero. Then implement a while loop in the main() to remove (dequeue) each record from the event queue and print the event time on the screen. Is the output correct? Note: For step-1 (to get the 2 demo marks) you can implement the customer and event queues using any method you like. However, for the final submission, to get full marks, you should ensure all data structures and algorithms are optimised for speed.

Step-2 (Server array implementation)

The server array should have a maximum of 20 servers. Each server should have a busy flag (boolean), an efficiency factor (double) and other data members for calculating the stats. C++ and Java coders should implement the server array with a class, preferably, and provide public functions for adding, and removing customers to/from the servers, finding the fasted idle server, etc. according to the specs on page 1.

Step-3 (Processing in the data)

When you have the customer queue, event queue and server array correctly completed, delete the main() test code from step 1 and replace it with code for reading the input data file “ass2.txt” and processing the data, as explained on page 1. The following algorithm shows how a typical discrete time simulator can be implemented: main() Declare variables and instances and do initialisations Open the input data file; if not found print error and exit Read first CustomerArrival event from file and add it to the event queue While the event queue is not empty . . . Get the next event from the event queue and set CrntTime to the event time If the event type = CustomerArrival event . . . if an idle server is available . . . Find fastest idle serve set the server’s idle flag to busy calculate the server’s finish time from event's customer data add ServerFinish event to the event queue Else Add event's customer to the customer queue End if If not EOF . . . Read next customer arrival from file add CustomerArrival event to the event queue End if Else // event type must be a ServerFinish event . . . Get server no. from event, set server to idle and do server's stats If customer queue is not empty . . . Get next customer from the customer queue Find fastest idle serve set the server’s idle flag to busy. calculate the server’s finish time add ServerFinish event to the event queue End if End if End while Print stats End main()

Step-4 (Optimisation and stats)

When you have the discrete time simulation working correctly, add the necessary data members and variables needed for calculating all the required stats, as explained on page 1, and optimise your simulator for speed.

Step-5 (Specifications)

In a comment block at the bottom of your program (no more than 20 lines of text) list all the data structures and algorithms used by your program to process the input data. Include any enhancements you did to speed up your program (if any). For this step, marks will be awarded based on how accurately and clearly you describe your program.

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

Marks will be awarded for the appropriate use of data structures and the efficiency of the program at processing the input and producing the correct output. Marks may be deducted for untidy or poorly designed code. Appropriate comments should be provided where needed. There will be a deduction of up to 4 marks for using STL, or equivalent libraries, rather than coding the data structures and algorithms yourself. You may use string or String type for storing words or text, if you wish. All coding and comments must be your own work. Submission: Assignments should be typed into a single text file named "ass2.ext" where "ext" is the appropriate file extension for the chosen language. You should run your program and copy and paste the output into a text file named: "output.txt" Submit your files via the submit program on banshee: submit -u user -c csci203 -a 2 ass1.ext output.txt - where user is your unix userid and ext is the extn of your code file. Late assignment submissions without granted extension will be marked but the points awarded will be reduced by 1 mark for each day late. Assignments will not be accepted if more than five days late. An extension of time for the assignment submission may be granted in certain circumstances. Any request for an extension of the submission deadline must be made via SOLS before the submission deadline. Supporting documentation should accompany the request for any extension. Read the full article

0 notes

programmingsolver · 5 years ago

Text

Computing Machinery I Assignment 05 Solution

Part A: Global Variables and Separate Compilation

A FIFO queue data structure can be implemented using an array, as shown in the following C program:

#include <stdio.h>

#include <stdlib.h>

#define QUEUESIZE

#define MODMASK

0x7

#define

FALSE

#define

TRUE

/* Function Prototypes */

void enqueue(int value);

int dequeue();

int queueFull();

int queueEmpty();

v…

View On WordPress

0 notes

myprogrammingsolver · 5 years ago

Text

Computing Machinery I Assignment 05 Solution

Part A: Global Variables and Separate Compilation

A FIFO queue data structure can be implemented using an array, as shown in the following C program:

#include <stdio.h>

#include <stdlib.h>

#define QUEUESIZE

#define MODMASK

0x7

#define

FALSE

#define

TRUE

/* Function Prototypes */

void enqueue(int value);

int dequeue();

int queueFull();

int queueEmpty();

v…

View On WordPress

0 notes

iyarpage · 7 years ago

Text

Data Structures & Algorithms in Swift Full Release Now Available!

Hey, Swifties! The full release of our Data Structures & Algorithms in Swift book is now available!

The early access release of this book — complete with the theory of data structures and algorithms in Swift — debuted at our conference RWDevCon 2018. Since then, the team has been hard at work creating a robust catalogue of challenges — 18 chapters in all — to test what you’ve learned and grow your expertise. The book is structured with the theory chapters alternating with the challenge chapters to keep you on track to nail down the fundamental and more advanced concepts.

Why Do You Need This Book?

Understanding how data structures and algorithms work in code is crucial for creating efficient and scalable apps. Swift’s Standard Library has a small set of general purpose collection types, yet they don’t give you what you need for every case.

Moreover, you’ll find these concepts helpful for your professional and personal development as a developer.

When you interview for a software engineering position, chances are that you’ll be tested on data structures and algorithms. Having a strong foundation in data structures and algorithms is the “bar” for many companies with software engineering positions.

Knowing the strategies used by algorithms to solve tricky problems gives you ideas for improvements you can make to your own code. Knowing more data structures than just the standard array and dictionary also gives you a bigger collection of tools that you can use to build your own apps.

Here’s what’s contained in the full release of the book:

Section I: Introduction

Chapter 1: Why Learn Data Structures & Algorithms?: Data structures are a well-studied area, and the concepts are language agnostic; a data structure from C is functionally and conceptually identical to the same data structure in any other language, such as Swift. At the same time, the high-level expressiveness of Swift make it an ideal choice for learning these core concepts without sacrificing too much performance.

Chapter 2: Swift Standard Library: Before you dive into the rest of this book, you’ll first look at a few data structures that are baked into the Swift language. The Swift standard library refers to the framework that defines the core components of the Swift language. Inside, you’ll find a variety of tools and types to help build your Swift apps.

Section II: Elementary Data Structures

Chapter 3: Linked List: A linked list is a collection of values arranged in a linear unidirectional sequence. A linked list has several theoretical advantages over contiguous storage options such as the Swift Array, including constant time insertion and removal from the front of the list, and other reliable performance characteristics.

Chapter 5: Stacked Data Structure: The stack data structure is identical in concept to a physical stack of objects. When you add an item to a stack, you place it on top of the stack. When you remove an item from a stack, you always remove the topmost item. Stacks are useful, and also exceedingly simple. The main goal of building a stack is to enforce how you access your data.

Chapter 7: Queues: Lines are everywhere, whether you are lining up to buy tickets to your favorite movie, or waiting for a printer machine to print out your documents. These real-life scenarios mimic the queue data structure. Queues use first-in-first-out ordering, meaning the first element that was enqueued will be the first to get dequeued. Queues are handy when you need to maintain the order of your elements to process later.

Easy-to-understand examples show key concepts, such as trees!

Section III: Trees

Chapter 9: Trees: The tree is a data structure of profound importance. It is used to tackle many recurring challenges in software development, such as representing hierarchical relationships, managing sorted data, and facilitating fast lookup operations. There are many types of trees, and they come in various shapes and sizes.

Chapter 11: Binary Trees: In the previous chapter, you looked at a basic tree where each node can have many children. A binary tree is a tree where each node has at most two children, often referred to as the left and right children. Binary trees serve as the basis for many tree structures and algorithms. In this chapter, you’ll build a binary tree and learn about the three most important tree traversal algorithms.

Chapter 13: Binary Search Trees: A binary search tree facilitates fast lookup, addition, and removal operations. Each operation has an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.

Chapter 15: AVL Trees: In the previous chapter, you learned about the O(log n) performance characteristics of the binary search tree. However, you also learned that unbalanced trees can deteriorate the performance of the tree, all the way down to O(n). In 1962, Georgy Adelson-Velsky and Evgenii Landis came up with the first self-balancing binary search tree: the AVL Tree.

Helpful visuals demonstrate how to organize and sort data!

Chapter 17: Tries: The trie (pronounced as “try”) is a tree that specializes in storing data that can be represented as a collection, such as English words. The benefits of a trie are best illustrated by looking at it in the context of prefix matching, which is what you’ll do in this chapter.

Chapter 19: Binary Search: Binary search is one of the most efficient searching algorithms with a time complexity of O(log n). This is comparable with searching for an element inside a balanced binary search tree. To perform a binary search, the collection must be able to perform index manipulation in constant time, and must be sorted.

Chapter 21: The Heap Data Structure: A heap is a complete binary tree, also known as a binary heap, that can be constructed using an array. Heaps come in two flavors: Max heaps and Min heaps. Have you seen the movie Toy Story, with the claw machine and the squeaky little green aliens? Imagine that the claw machine is operating on your heap structure, and will always pick the minimum or maximum value, depending on the flavor of heap.

Chapter 23: Priority Queue: Queues are simply lists that maintain the order of elements using first-in-first-out (FIFO) ordering. A priority queue is another version of a queue that, instead of using FIFO ordering, dequeues elements in priority order. A priority queue is especially useful when you need to identify the maximum or minimum value given a list of elements.

Section IV: Sorting Algorithms

Chapter 25: O(n²) Sorting Algorithms: O(n²) time complexity is not great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. These algorithms are space efficient; they only require constant O(1) additional memory space. In this chapter, you’ll be looking at the bubble sort, selection sort, and insertion sort algorithms.us shapes and sizes.

Chapter 27: Merge Sort: In this chapter, you’ll look at a completely different model of sorting. So far, you’ve been relying on comparisons to determine the sorting order. Radix sort is a non-comparative algorithm for sorting integers in linear time. There are multiple implementations of radix sort that focus on different problems. To keep things simple, in this chapter you’ll focus on sorting base 10 integers while investigating the least significant digit (LSD) variant of radix sort.

Chapter 29: Radix Sort: A binary search tree facilitates fast lookup, addition, and removal operations. Each operation has an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.

Chapter 31: Heapsort: Heapsort is another comparison-based algorithm that sorts an array in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 21, “The Heap Data Structure.” Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree.

Chapter 33: Quicksort: Quicksort is another divide and conquer technique that introduces the concept of partitions and a pivot to implement high performance sorting. You‘ll see that while it is extremely fast for some datasets, for others it can be a bit slow.

Real-world examples help you apply the book’s concepts in a concrete and relevant way!

Section V: Graphs

Chapter 35: Graphs: What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs! A graph is a data structure that captures relationships between objects. It is made up of vertices connected by edges. In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. This lets you choose the cheapest or shortest path between two vertices.

Chapter 37: Breadth-First Search: In the previous chapter, you explored how graphs can be used to capture relationships between objects. Several algorithms exist to traverse or search through a graph’s vertices. One such algorithm is the breadth-first search algorithm, which can be used to solve a wide variety of problems, including generating a minimum spanning tree, finding potential paths between vertices, and finding the shortest path between two vertices.

Chapter 39: Depth-First Search: In the previous chapter, you looked at breadth-first search where you had to explore every neighbor of a vertex before going to the next level. In this chapter, you will look at depth-first search, which has applications for topological sorting, detecting cycles, path finding in maze puzzles, and finding connected components in a sparse graph.

Chapter 41: Dijkstra’s Algorithm: Have you ever used the Google or Apple Maps app to find the shortest or fastest from one place to another? Dijkstra’s algorithm is particularly useful in GPS networks to help find the shortest path between two places. Dijkstra’s algorithm is a greedy algorithm, which constructs a solution step-by-step, and picks the most optimal path at every step.

Chapter 43: Prim’s Algorithm: In previous chapters, you’ve looked at depth-first and breadth-first search algorithms. These algorithms form spanning trees. In this chapter, you will look at Prim’s algorithm, a greedy algorithm used to construct a minimum spanning tree. A minimum spanning tree is a spanning tree with weighted edges where the total weight of all edges is minimized. You’ll learn how to implement a greedy algorithm to construct a solution step-by-step, and pick the most optimal path at every step.

The book moves beyond fundamentals to more advanced concepts, such as Dijkstra’s Algorithm!

Data Structures and Algorithms in Swift will teach you how to implement the most popular and useful data structures, and when and why you should use one particular data structure or algorithm over another.

This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs. And the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

Get your own copy:

If you’ve pre-ordered Data Structures & Algorithms in Swift, you can log in to the store and download the final version here.

If you haven’t already bought this must-have addition to your development library, head over to our store page to grab your copy today!

Questions about the book? Ask them in the comments below!

The post Data Structures & Algorithms in Swift Full Release Now Available! appeared first on Ray Wenderlich.

Data Structures & Algorithms in Swift Full Release Now Available! published first on https://medium.com/@koresol

0 notes

mlbors · 7 years ago

Text

Discovering C#

Through this article, we are going to take a look at the programming language named C#. Let's get into it!

Introduction

First of all, we are not going to look at C# in every single detail because it is not the purpose of this article and it would probably take a whole book. Our goal here is to simply get familiar with this very common language. We are going to have a look at the very basics of this language and go a little further after that. This article is some kind of introduction to this language.

What is C#?

C#, or C Sharp, is a programming language developed by Microsoft. We usually say that it is an object-oriented programming language, but in fact, it is a multi-paradigm programming language. It was designed to be used with the .NET Framework. It is derived from C and C++ and it is really similar to Java.

C# programs run on the .NET Framework through a virtual execution system called the Common Language Runtime (CLR). When we compile a program written in C#, it is transformed to an Intermediate Language (IL). That last code and all the resources a stored in an executable file called Assembly. When the program is executed, the Assembly is loaded into the CLR that will perform the Just-in-Time compilation (JIT) that will convert the Intermediate Language code to native machine instructions. In a very few words, we can say that the CLR is to .NET the same thing as the JVM is to Java.

Generalities and syntax

A source code written in C# is placed in a file that has ".cs" as extension. Lines written in this file have to be read from left to right, from top to bottom. Every instruction should be ended with a semicolon (;).

C# is case-sensitive.

We can add comments to our code using "//" for a single line, or "/" and "/" for multiple lines.

Variables

A variable is like a box where we store a value. It is a name given to a data value. The content of a variable can vary at any time. In C#, a variable has to be defined with a data type. A variable can be declared and initialized later or it can be declared and initialized at the same time.

// Declaring a variable string message; // Assigning a value the previously declared variable message = "Hello World!!"; // Declaring and initializing a variable string message = "Hello World!!";

Data Types

Because C# is a strongly typed language, we are required to inform the compiler about which data type we want to use with every variable we declare. A data type specifies the type of data that a variable can store.

The information stored in a type can include the following:

The storage space that a variable of the type requires

The maximum and minimum values that it can represent

The members (methods, fields, events, and so on) that it contains

The base type it inherits from

The location where the memory for variables will be allocated at run time

The kinds of operations that are permitted

The compiler uses type information to make sure that all operations that are performed in our code are type safe.

// Declaring a string string stringVar = "Hello World!!"; // Declaring a integer int intVar = 100; // Declaring a float float floatVar = 10.2f; // Declaring a character char charVar = 'A'; // Declaring a boolean bool boolVar = true;

Value Type and Reference Type

In C#, data types are categorized based on how they store their value in the memory. They could be a value type or a reference type.

Value Type

A data type is a value type if it holds a data value within its own memory space. It means variables of these data types directly contain their values.

The following data types are all of value type:

bool

byte

char

decimal

double

enum

float

int

long

sbyte

short

struct

uint

ulong

ushort

When we pass a value type from one method to another, the system creates a separate copy of that variable in the other method. So if the value is changed in one method, the value in the other method won't be affected.

Reference Type

A data type is a reference type if it stores the memory address where the value is being stored. In other words, a reference type contains a pointer to another memory location that holds the data.

The following data types are of reference type:

String

All arrays, even if their elements are value types

Class

Delegates

When we pass a reference type from one method to another, the system passes the address of the variable. It means that if the value is changed in one method, the value in the other method will also be affected.

Operators

An operator is a symbol that is used to perform operations. Some operators have different meanings based on the data type of the operand.

Condition

In C# programming, there are various types of decision-making statements:

if statement

if-else statement

Nested if statement

if-else-if statement

switch statement

If statements

The if statement contains a boolean expression inside brackets followed by a single or multi-line code block. At runtime, if a boolean expression is evaluated to true, then the code block will be executed.

// if statement if (a > b) { Console.WriteLine("a is greater than b"); } // if-else statement if (a > b) { Console.WriteLine("a is greater than b"); } else { Console.WriteLine("a is either equal to or less than b"); } // if-else-if statement if (a > b) { Console.WriteLine("a is greater than b"); } else if (a < b) { Console.WriteLine("a is less than b"); } else { Console.WriteLine("a is equal ton b"); } // Nested if statement if (a > 0) { if (a <= 100) { Console.WriteLine("a is positive number less than 100"); } else { Console.WriteLine("a is positive number greater than 100"); } }

Switch

The switch statement executes a code block depending upon the resulted value of an expression. It is like the if-else-if statement.

switch (a) { case 10: Console.WriteLine("It is 10"); break; case 20: Console.WriteLine("It is 20"); break; case 30: Console.WriteLine("It is 30"); break; default: Console.WriteLine("Not 10, 20 or 30"); break; }

Loops

A loop gives us the ability to repeat a block of code. In C#, there are four ways to achieve a loop.

While loop

A While loop is used to iterate a part of the program while a condition is true.

int i = 0; while (i < 10) { Console.WriteLine("Value of i: {0}", i); i++; }

Do-While loop

A Do-While loop is like a While loop, except that the block of code will be executed at least once because the loop executes the block of code first and then checks the condition.

int i = 0; do { Console.WriteLine("Value of i: {0}", i); i++; } while (i < 10);

For loop

A For loop executes a block of statements repeatedly until the specified condition returns false.

for (int i = 0; i < 10; i++) { Console.WriteLine("Value of i: {0}", i); }

Foreach loop

A Foreach statement provides a way to iterate through the elements of an array or any enumerable collection.

int[] numbers = { 4, 5, 6, 1, 2, 3, -2, -1, 0 }; foreach (int i in numbers) { System.Console.Write("{0} ", i); }

Arrays

In C#, an array is a group of similar types of elements that have contiguous memory location. An array is a special type of data type which can store a fixed number of values sequentially using special syntax. Array index starts from 0.

Like a variable, an array can be declared and initialized later or it can be declared and initialized at the same time.

// Declaring an array that contains strings string[] names; // Instantiating the array and defining its size string[] names = new string[2]; // Storing a value at index 0 names[0] = "John Doe"; // Displaying the value stored at index 0 Console.WriteLine(intArray[0]);

Collections

In C#, a collection represents a group of objects. Unlike an array, a collection doesn't have a fixed size. There are several types of collections.

ArrayList

An ArrayList stores objects of any type like an array.

// Declaring ArrayList ArrayList arrayList = new ArrayList(); // Adding elements arrayList.Add(1); arrayList.Add("Two"); // Add an element at a specific index arrayList.Insert(1, "Second Item"); // Removing element at a specific index arrayList.RemoveAt(1);

SortedList

A SortedList stores key and value pairs. It automatically arranges elements in ascending order of key by default.

// Declaring SortedList SortedList sortedList = new SortedList(); // Adding elements sortedList.Add(3, "Three"); sortedList.Add(4, "Four"); sortedList.Add(1, "One"); sortedList.Add(5, "Five"); sortedList.Add(2, "Two");

Stack

A Stack stores the values in LIFO style (Last In First Out). It provides a Push() method to add a value and Pop() and Peek() methods to retrieve values.

// Declaring Stack Stack stack = new Stack(); // Adding elements stack.Push("John Doe"); stack.Push(1); stack.Push(2); stack.Push(null); stack.Push(3); // Displaying the top item from the stack Console.WriteLine(stack.Peek()); // Removing and returning the item from the top of the Stack stack.Pop()

Queue

A Queue stores the values in FIFO style (First In First Out). It keeps the order in which the values were added. It provides an Enqueue() method to add values and a Dequeue() method to retrieve values from the collection.

// Declaring Queue Queue queue = new Queue(); // Adding elements queue.Enqueue(3); queue.Enqueue(2); queue.Enqueue(1); // Displaying the first item of the Queue Console.WriteLine(queue.Peek()); // Removing and returning the item from the beginning of the queue queue.Dequeue();

HashTable

A HashTable stores key and value pairs. It retrieves the values by comparing the hash value of the keys.

// Declaring Hashtable Hashtable hashtable = new Hashtable(); // Adding elements hashtable.Add(1, "One"); hashtable.Add(2, "Two"); hashtable.Add(3, "Three"); hashtable.Add("Fr", "Four"); // Accessing element string str = (string)hashtable[2]; // Removing element hashtable.Remove(3);

Tuples

A tuple is an ordered immutable sequence, fixed-size of heterogeneous objects. Tuples allow to return multiple values from a method.

// Declaring a tuple var numbers = ("One", "Two", "Three", "Four", "Five"); // Declaring another tuple (string, string, int) person = ("John", "Doe", 30); // Declaring another tuple and accessing values. var person = (firstName: "John", lastName: "Doe", Age: 30); person.firstName; We can also use a tuple as a return type. (int Val1, int Val2) Values() { int val1 = 1; int val2 = 2; return (val1, val2); } var values = GetValues();

Classes

A class is like a blueprint. It is a template from which objects are created. In an object-oriented programming language like C#, an object is like in the real world: it has properties and functionalities. So, a class defines the kinds of data and the functionalities that an object will have.

Access modifiers

Access modifiers are applied to the declaration of the class, methods, properties, fields and other members. They define the accessibility of the class and its members. There are four access modifiers:

public - allows a class to expose its member variables and member functions to other functions and objects

private - allows a class to hide its member variables and member functions from other functions and objects

protected - allows a child class to access the member variables and member functions of its base class

internal - allows a class to expose its member variables and member functions to other functions and objects in the current assembly

Fields

A field is a class level variable that can hold a value.

Properties

A property allows us to control the accessibility of a class variable. It encapsulates a private field and provides a level of abstraction allowing us to change a field while not affecting the external way they are accessed by the things that use our class.

Constructor

A class constructor is a special member function that is executed whenever a new object of that class is created. A constructor has exactly the same name as the class and it does not have any return type.

Methods

A method is a group of statements that perform a task. A method is basically written like so:

<Access Modifier <Return Type> <Method Name>(Parameter List) { Method Body }

Namespaces

A namespace is a container for a set of related classes. A class name declared in one namespace does not conflict with the same class name declared in another.

Example

Let's put what we saw together to create a simple class:

// Namespace namespace MyNamespace { // Declaring the class - access modifier, class keyword, class name public class MyClass { // Fields - access modifier, type, field name public string field = string.Empty; // Property private int propertyVar; // Property accessors public int Property { get { return propertyVar; } set { propertyVar = value; } } // Constructor public MyClass() { } // Method - acces modifier, return type, method name, parameters public void MyMethod(int parameter1, string parameter2) { Console.WriteLine("First Parameter {0}, second parameter {1}", parameter1, parameter2); } // Method - acces modifier, return type, method name, parameters public int MyMethod(int parameter1, int parameter2) { return parameter1 + parameter2; } } }

Interfaces

An interface is like a contract. Every class that inherits from a specific interface has to implement what is defined in the interface. An interface only contains the declaration of the methods and the properties that a class has to implement.

// Declaring the interface interface MyInterface { void MyMethod(string message); } // Implementing the interface class MyClass : MyInterface { public void MyMethod(string message) { Console.WriteLine(message); } }

An interface can also contain properties.

interface MyInterface { string Property { get; set; } void MyMethod(string message); } class MyClass : MyInterface { private string property; public string Property { get { return name; } set { name = value; } } public void MyMethod(string message) { Console.WriteLine(message); } }

Structs

A struct is mostly like a class, but while a class is a reference type, a struct is a value type data type. Unlike a class, it does not support inheritance and can't have a default constructor.

We can consider defining a struct instead of a class if instances of the type are small and commonly short-lived or are commonly embedded in other objects. The general rule to follow is that structs should be small, simple collections of related properties, that are immutable once created.

struct Point { private int x, y; public int XPoint { get { return x; } set { x = value; } } public int YPoint { get { return y; } set { y = value; } } public Point(int p1, int p2) { x = p1; y = p2; } }

Enums

An enum is a value type data type. It is used to declare a list of named integral constants that may be assigned to a variable. An enum is used to give a name to each constant so that the constant integer can be referred using its name.

enum Days { Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday } Console.WriteLine(Days.Tuesday); Console.WriteLine((int)Days.Friday);

Delegates

In C#, a delegate is like a pointer to a function. It is a reference type data type and it holds the reference to a method. When we instantiate a delegate, we can associate its instance with any method with a compatible signature and return type. Delegates are used for implementing events and callback methods.

// Declaring the delegate delegate int Calculator(int n); class Program { static int number = 1; public static int add(int n) { number = number + n; return number; } public static int mul(int n) { number = number * n; return number; } public static int getNumber() { return number; } public static void Main(string[] args) { // Instantiating the delegate Calculator c1 = new Calculator(add); // Instantiating the delegate Calculator c2 = new Calculator(mul); // Calling method using delegate c1(20); // Calling method using delegate c2(3); } }

Anonymous functions and Lambdas

An anonymous function is a type of function that doesn't have a name.

In C#, there are two types of anonymous functions:

Lambda expressions

Anonymous methods

Lambdas Expressions

A lambda expression is an anonymous function that we can use to create delegates. We can use a lambda expression to create a local function that can be passed as an argument.

class Program { delegate int Square(int num); static void Main(string[] args) { Square getSquare = x => x * x; int a = getSquare(5); Console.WriteLine(a); } }

Anonymous Methods

An anonymous method is quite like a lambda expression but allows us to omit the parameter list.

class Program { public delegate void AnonymousFunction(); static void Main(string[] args) { AnonymousFunction myFunction = delegate() { Console.WriteLine("This is an anonymous function"); }; myFunction(); } }

Generics

Generics allow us to define a class with placeholders for the type of its fields, methods or parameters. The compiler will replace these placeholders with the specified type at compile time. Generics increase code reusability.

// Declaring a generic class class GenericClass<T> { // Declaring a generic field private T genericField; // Declaring a generifc property public T genericProperty { get; set; } // Constructor public GenericClass(T value) { genericField = value; } // Declaring a generic method public T genericMethod(T genericParameter) { Console.WriteLine("Parameter type: {0}, value: {1}", typeof(T).ToString(),genericParameter); Console.WriteLine("Return type: {0}, value: {1}", typeof(T).ToString(), genericField); return genericField; } } class Program { static void Main(string[] args) { // Using the generic class GenericClass<int> genericClass = new GenericClass<int>(10); } }

We can use constraints to specify which type of placeholder is allowed with a generic class.

// Declaring a generic class specifying that T must be a reference type. class GenericClass<T> where T: class { ... }

Generic collections

We mentioned collections before. In C#, we can also have generic collections.

List - contains elements of specified type

Dictionary - contains key-value pairs

SortedList - stores key and value pairs in an ordered manner

Hashset - contains non-duplicate elements

Queue - a Queue containing elements of specified type

Stack - a Stack containing elements of specified type

Polymorphism

In C#, polymorphism can be used in different manners. There are two types of polymorphism in C#: compile time polymorphism and runtime polymorphism. Compile time polymorphism, also known as static binding or early binding, is achieved by method overloading and operator overloading. Runtime polymorphism, also known as dynamic binding or late binding, is achieved by method overriding.

Method overloading

It allows us to have the same method multiple times but with different parameters or return type.

public class Program { public int add(int a, int b) { return a + b; } public int add(int a, int b, int c) { return a + b + c; } public float add(float a, float b) { return a + b; } }

Method overriding

It allows a class to override a method that is inherited from a base class. We need to use the keyword "virtual" in front of the method in the base class to allow a derived class to override it.

public class Animal { public virtual void play() { Console.WriteLine("Playing"); } } public class Cat : Animal { public override void play() { Console.WriteLine("Playing like a cat"); } }

Abstract classes

An abstract class is a class that cannot be instantiated. It can contain concrete or abstract methods. An abstract method is a method that has no body and it must be implemented by the derived class.

public abstract class AbstractClass { public abstract void AbstractMethod(); public void Method() { Console.WriteLine("This is a method"); } } public class ConreteClass : AbstractClass { public override void AbstractMethod() { Console.WriteLine("Abstract method implementation"); } }

Attributes

An attribute is a declarative tag that is used to send information to runtime about the behavior of various elements like classes, methods, structures, enumerators or assemblies. Attributes are used to add metadata, such as compiler instruction or other information to a program.

Attributes are generally applied physically in front of type and type member declarations. They're declared with square brackets, "[" and "]", surrounding the attribute. In the following example, we use the "Obsolete" attribute which is a pre-defined attribute in the .NET Framework.

class Program { static void Main() { Test(); } [Obsolete("Test method is obsolete.", true)] static void Test() { } }

When we try to compile the program, the compiler generates an error.

Conclusion

Through this article we had an overview of the C# programming language and how we can use it. It was more like a theoretical article more than a practical article. Nevertheless, we now have the tools to dig a little deeper and to use C#.

One last word

If you like this article, you can consider supporting and helping me on Patreon! It would be awesome! Otherwise, you can find my other posts on Medium and Tumblr. You will also know more about myself on my personal website. Until next time, happy headache!

#programming #development #c #coding #code

0 notes

just4programmers · 8 years ago

Text

C++ STL Algorithm Library

In this article you will learn about stl algorithm library in c++.

Are you a competitive programmer or very passionate programmer then you must know about STL algorithm library. It contains very rich set of algorithms. If you practice this well you can nail any programming interview. All inbuilt algorithms implemented in this library were implemented in the best complexity way. So using those is better than writing own code. It also saves time and code readability.

C++ STL Algorithm Library

There are many of those algorithms. We will see some of them which mostly used.

To work with these we first need to include algorithm library. That is #include<algorithm>

In all previous articles we learned about containers, now we can apply these algorithms on those containers.

Since main intention of algorithm is to retrieve information or to know some of properties, these will not do any modifications on container sizes or container storage. They just use iterators to apply on containers.

min (a, b): This gives minimum value of a and b. Here conditions are both a and b must be same data type. In case if a and b are equal it gives same value.

max (a,b) : This gives maximum value of a and b. Both a and b should be same data type.

sort (first_iterator , last_iterator): Sorts the elements of a container between given vectors.

Above sort sorting function used to sort containers only. Because they only have iterators. But for normal arrays. We have to use sort (array_begin, array_end):

Example program to show above algorithms:

//Standard library algorithms #include <iostream> #include <algorithm> #include <vector> #include <ctime> #include <cstdlib> using namespace std; int main(){ cout << "min(10,3) gives " << min(10,3) << "\n"; cout << "min(5,5) gives " << min(5,5) << "\n"; cout << "min ('A', 'B') gives" << min ('A' , 'B') << "\n"; cout << endl << "max(10,3) gives " << max(10,3) << "\n"; cout << "max(5,5) gives " << max(5,5) << "\n"; cout << "max ('A', 'B') gives" << max ('A' , 'B') << "\n"; vector <int> v; vector <int> :: iterator it; for(int i=0; i<5;i++) v.push_back(10-i); cout << endl << "Elements of vector before sort " << endl; for(it= v.begin(); it!=v.end();it++) cout << *it << " "; cout << endl; cout << "Performing sort(v.begin(), v.end()) " << endl; sort(v.begin(), v.end()); cout << "After above function vector elements are " << endl; for(it= v.begin(); it!=v.end(); it++) cout << *it << " " ; cout << endl; int ar[5]; for(int i=0; i<5 ;i++) ar[i]= 15-i; cout << endl << "Array elements are " << endl; for(int i=0; i<5; i++) cout << ar[i] << " " ; cout << endl; cout << "Performing sort(ar+0, ar+5) " << endl; sort(ar+0, ar+5); cout << "After above operation array elements are " << endl; for(int i=0;i<5; i++) cout << ar[i] << " "; cout << endl; return 0; }

Output

min(10,3) gives 3 min(5,5) gives 5 min (‘A’, ‘B’) givesA

max(10,3) gives 10 max(5,5) gives 5 max (‘A’, ‘B’) givesB

Elements of vector before sort 10 9 8 7 6 Performing sort(v.begin(), v.end()) After above function vector elements are 6 7 8 9 10

Array elements are 15 14 13 12 11 Performing sort(ar+0, ar+5) After above operation array elements are 11 12 13 14 15

find(): This will find given element present in container or not. Input parameters for this are range and element. Range contains two values, beginning of the range and ending of the range.

find() on arrays will be find(ar_base_address, ar_end, element);

Similarly find() on other stl containers will be find(iterator_to_1st, iterator_to_last, element);

One more thing we need to know about this find() is, if given element is present it points that element position, else it points to end of the container. This we can use for checking purpose.

count (): This is same way of find() algorithm. But this returns number of times given element present in the given range of elements.

Same like find(), for arrays we need to give base address as range and for other STL containers like vector, dequeue, list, etc. give iterator positions as range.

equal(): This is used to compare range of sequences. We will give some range as parameter to compare other range. It gives true if all elements equal in the range else returns false.

For example if give a vector and an array ranges, equal gives true if and only if ith element of vector and array are same. Where i is between given range.

Example program to show above algorithms:

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int ar[5]; for(int i=0;i<5; i++) ar[i]= i*i; cout << "Array contains 0, 1, 4, 9, 16" << endl; cout << "Performing find(ar+0, ar+5, 44) " << endl; int *position= find(ar+0, ar+5, 44); if(position == ar+5){ cout << "Element not found in the array " << endl; } else{ cout << "Element found in the array " << endl; } vector <int> vec; vector <int> :: iterator it; for(int i=0; i<5; i++) vec.push_back(i*i); cout << endl << "Vector contains elements 0, 1, 4, 9, 16" << endl; cout << "Performing find (vec.begin(), vec.end(), 4) " << endl; it = find (vec.begin(), vec.end(), 4); if(it == vec.end()){ cout << "Element not found in the vector " << endl; } else{ cout << "Element found in the vector " << endl; } ar[0]= vec[0]= 2; ar[1]= vec[1]= 3; ar[2]= vec[2]= 2; ar[3]= vec[3]= 2; ar[4]= vec[4]= 5; cout << endl << "Array and vector contains elements 2, 3, 2, 2, 3" << endl; cout << "Performing count (ar+0, ar+5, 2) on array " << endl; int cnt= count(ar+0, ar+5, 2); cout << "2 present " << cnt << " times in the array" << endl; cout << "Performing count (vec.begin(), vec.end(), 3) on vector " << endl; cnt= count(vec.begin(), vec.end(), 3); cout << "3 present " << cnt << " times in the vector " << endl; cout << endl << "elements of array are " << endl; for(int i=0; i<5; i++) cout << ar[i] << " " ; cout << endl; cout << "elements in the vector are " << endl; for(it=vec.begin(); it!=vec.end(); it++) cout << *it << " "; cout << endl; cout << "Now performing equal(vec.begin(), vec.end(), ar) " << endl; bool chk = equal(vec.begin(), vec.end(), ar); if(chk) cout << "Both sequences are equal "<< endl; else cout << "Givens sequences are not equal " << endl; return 0; }

Output

Array contains 0, 1, 4, 9, 16 Performing find(ar+0, ar+5, 44) Element not found in the array

Vector contains elements 0, 1, 4, 9, 16 Performing find (vec.begin(), vec.end(), 4) Element found in the vector

Array and vector contains elements 2, 3, 2, 2, 3 Performing count (ar+0, ar+5, 2) on array 2 present 3 times in the array Performing count (vec.begin(), vec.end(), 3) on vector 3 present 1 times in the vector

elements of array are 2 3 2 2 5 elements in the vector are 2 3 2 2 5 Now performing equal(vec.begin(), vec.end(), ar) Both sequences are equal

reverse(start_, end_): This algorithm reverse the elements in given range.

accumulate(start_, end_, initial_sum ): Accumulate is used to sum the all elements in the give range. It adds elements to initial sum which also we specify as a parameter to this accumulate function.

To use this accumulate function we should include numeric library. i.e #include <numeric>

distance( start_, position): This function used to find the how much distance from the given iterator position to given position. Position might be anything specified by user. For example position may be minimum element, of maximum element of the vector/container.

Example program to show above functions:

#include <iostream> #include <algorithm> #include <vector> #include <numeric> // This is for accumulate function using namespace std; int main(){ vector <int> vec; vector <int> :: iterator it; for(int i=0; i<5; i++) vec.push_back(i+5); cout << "Vector contains elements " ; for(it=vec.begin(); it!= vec.end(); it++) cout << *it << " "; cout << endl; cout << "Performing reverse(vec.begin(), vec.end()) " << endl; reverse(vec.begin(), vec.end()); cout << "Now vector elements are " ; for(it=vec.begin(); it!= vec.end(); it++) cout << *it << " "; cout << endl; cout << endl << "Performing accumulate (vec.begin(), vec.end(), 0) " << endl; int total= accumulate(vec.begin(), vec.end(), 0); cout << "Total of vector elements using accumulate function is " << total << endl; cout << endl << "Finding distance from starting of vector to maximum element of the vector " << endl; cout << "For that performing distance(vec.begin(), max(vec.begin(), vec.end()) " << endl; int dist= distance (vec.begin(), max(vec.begin(), vec.end() )); cout << "The distance to maximum element from starting of the iterator is " << dist << endl; return 0; }

Output

Vector contains elements 5 6 7 8 9 Performing reverse(vec.begin(), vec.end()) Now vector elements are 9 8 7 6 5

Performing accumulate (vec.begin(), vec.end(), 0) Total of vector elements using accumulate function is 35

Finding distance from starting of vector to maximum element of the vector For that performing distance(vec.begin(), max(vec.begin(), vec.end()) The distance to maximum element from starting of the iterator is 5

next_permuatation(start_ , end_ ): As I said starting of this article, STL is a friend to competitive programmer, generating permutations is one of the main task in some questions. By using this we can generate next permutation of given sequence between the elements given specified range.

prev_permutation (start_, end_ ): This gives previous permutation of the sequence.

Example program to show above functions:

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ vector <int> vec; vector <int> :: iterator it; for(int i=1; i<=5; i++) vec.push_back(i); cout << "Elements in the vector are " ; for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " "; cout << endl; cout << "next_permutation (vec.begin(), vec.end()) gives " << endl; next_permutation(vec.begin(), vec.end()); for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " "; cout << endl; cout << "prev_permutation (vec.begin(), vec.end()) gives " << endl; prev_permutation(vec.begin(), vec.end()); for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " "; cout << endl; return 0; }

Output

Elements in the vector are 1 2 3 4 5 next_permutation (vec.begin(), vec.end()) gives 1 2 3 5 4 prev_permutation (vec.begin(), vec.end()) gives 1 2 3 4 5

lower_bound(start_, end_ , ele ): Returns an iterator pointing to the first element in the range which has element not less than ele.

upper_bound(start_, end_ ,ele ): Returns an iterator pointing to the first element in the given range which has element greater than ele.

These two functions used in performing binary search operation:

Example program to show above functions:

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int ar[5]= {10, 20, 30, 40, 50}; vector <int> vec (ar, ar+5) ; vector <int> :: iterator it; sort(vec.begin(), vec.end()); // Sorting must need for lower_bound, upper_bound and binary search cout << "Elements in the vector are " ; for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " "; cout << endl; it = lower_bound(vec.begin(), vec.end(), 25); cout << "Lower bound for 25 is at position " << it- vec.begin() << endl; it = upper_bound(vec.begin(), vec.end(), 35); cout << "upper bound for 35 is at position " << it- vec.begin() << endl; return 0; }

Output

Elements in the vector are 10 20 30 40 50 Lower bound for 25 is at position 2 upper bound for 35 is at position 3

Comment below if you have any queries related to above C++ stl algorithm library.

The post C++ STL Algorithm Library appeared first on The Crazy Programmer.

#The Crazy Programmer

0 notes

myquestionbank · 8 years ago

Text

C++ programming questions and answers

Vector vs. deques. Vectors are used to store contiguous elements like an array. However, unlike arrays, vectors can be resized Dequeues, are double ended queues that store elements in a linear order. They allow elements to be accessed at any position. Vector vs. deques. – Vector supports dynamically expandable array. – Deque is double ended queue. Deque elements can be accessed from both the ends…

View On WordPress

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

When you have the customer queue, event queue and server array correctly completed, delete the main() test code from step 1 and replace it with code for reading the input data file “ass2.txt” and processing the data, as explained on page 1. The following algorithm shows how a typical discrete time simulator can be implemented: main() Declare variables and instances and do initialisations Open the input data file; if not found print error and exit Read first CustomerArrival event from file and add it to the event queue While the event queue is not empty . . . Get the next event from the event queue and set CrntTime to the event time If the event type = CustomerArrival event . . . if an idle server is available . . . Find fastest idle serve set the server’s idle flag to busy calculate the server’s finish time from event's customer data add ServerFinish event to the event queue Else Add event's customer to the customer queue End if If not EOF . . . Read next customer arrival from file add CustomerArrival event to the event queue End if Else // event type must be a ServerFinish event . . . Get server no. from event, set server to idle and do server's stats If customer queue is not empty . . . �� Get next customer from the customer queue Find fastest idle serve set the server’s idle flag to busy. calculate the server’s finish time add ServerFinish event to the event queue End if End if End while Print stats End main()

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes