estd::ordered_vector

Overview

The estd::ordered_vector is a fixed-capacity associative container that represents a sorted multiset of objects of type Key. Sorting is done using the key comparison function Compare and the default order is ascending order.

Unlike std::multiset, search operations have logarithmic complexity. Removal and insertion operations have linear complexity in the distance to the end of the ordered_vector.

Removal and insertion operations cause a memmove of the elements located behind the target position. This invalidates all the references, pointers, and iterators referring to the moved elements.

Declare namespace allocates memory whereas ::estd::ordered_vector<type> is a handler class. The ordered vector from declare namespace has functionalities to construct, whereas, ordered vector under estd namespace has other functions like insert, find_or_insert, contains, remove, clear, etc.

Usage

The usage guidelines apply for ordered_vector:

Usage guidance

Size of ordered_vector should be checked before accessing the elements. Accessing outside the bounds of ordered_vector using at() and operator[]() function will result in assertion.

Example

The examples for the above functions are given below.

using IntVector10 = ::estd::declare::ordered_vector<int32_t, 10, std::less<int32_t>>;
// declare the ordered vector of size 10
::estd::declare::ordered_vector<int32_t, 10> a;
// inserting elements to the ordered vector created
a.insert(3);
EXPECT_THAT(a, testing::ElementsAre(3));
a.insert(2);
EXPECT_THAT(a, testing::ElementsAre(2, 3));
a.insert(1);
// ordered elements in the vector
EXPECT_THAT(a, testing::ElementsAre(1, 2, 3));
a.resize(2);
// element size reduced to 2
EXPECT_THAT(a, testing::ElementsAre(1, 2));
// makes the vector empty
a.clear();
a.find_or_insert(5);
// Since element 5 is not found, it is inserted otherwise returns position.
EXPECT_THAT(a, testing::ElementsAre(5));
// Check whether the value is in the vector
ASSERT_TRUE(a.contains(5));
// finds and remove particular element
// a.remove_if(comp); removes element based on predicate
a.remove(5);
a.insert(1);
// erase element using iterator
a.erase(a.begin());
a.insert(1);
a.insert(2);
// erase element using range of iterators
a.erase(a.begin(), a.end());
a.insert(5);
IntVector10::const_iterator itr = a.begin();
itr++;
// returns the position of the value mentioned
ASSERT_EQ(*itr, 2);