CODEWITHSUNDEEP
c++containersstd
gigi
gigi

Reputation: 9

Is c++ standard library containers have no implementation?

I'm reimplementing c++ std containers.

In "Professional C++ by Marc Gregoire" I read this quote

c++ standard specify the interface but not the implementation, of each container

Implement means just "template class" code in Container?

what is implementation in c++ Standard container library?

Upvotes: 0

Views: 198

Answers (3)

JaMiT
JaMiT

Reputation: 17072

The C++ standard specifies functionality. It does not care how that functionality is achieved. This is similar to a coding homework problem. The teacher specifies the functionality required of the student's code, while the student decides how to achieve that. Typically, there is more than one correct answer.

Let us look at std::vector for an example. The standard says that std::vector::size() must return the number of elements in the container in constant time. This implies that the container is going to store that size somewhere, but it is up to the implementation to decide where to store that size.

One implementation might decide to store that information directly in the vector class, along the lines of the following. (Please accept that I have abridged some details to focus on the relevant parts.)

class vector<T> {
    T * data;
    size_type capacity;
    size_type size;      // <-- directly in the class

  public:
    // Public interface goes here.
    size_type size() const noexcept { return size; }
};

Another implementation might decide to minimize the size of each vector object and instead store the size in dynamically-allocated memory.

struct vector_data<T> {
    size_type capacity;
    size_type size;
    T * data;   // Advanced techniques could avoid this extra layer of indirection
};

class vector<T> {
    std::unique_ptr<vector_data<T>> data;  // <-- Typically, the same size as a raw pointer

  public:
    // Public interface goes here.
    size_type size() const noexcept { return data->size; }
};

Both implementations meet the interface requirements of the standard (well, of the C++ 17 standard, before size() had to be constexpr). The former is optimized for speed, while the latter is optimized for (local) space. As far as the C++ standard is concerned, either approach is acceptable.

Upvotes: 0

Deumaudit
Deumaudit

Reputation: 1016

That quote means that c++ standard specify what should be done, but not how it should be done. For example if standard says "function sum must return result of summing its argument", than compiler can easily implement this behaviour in any available way, so every next implementation is legal, and the choice of which implementation to put in a particular compiler depends only on the compiler developer

template<typename T>
T sum(T a, T b)
{
    return a+b;
}

template<typename T>
T sum(T a, T b)
{
    return -(-a - b);
}

template<typename T>
T sum(T a, T b)
{
    return ("some random string" > 0)*a + b;
}

Upvotes: 2

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 123293

You can find drafts of all C++ standards online. I recommend to take a look at one them. You can find concrete examples there, so I can use some hypothetical

 void foo(int* a,int* b);

Now for example the specification of foo will say something along the line of:

  • Precondition: a and b point to elements in the same array.
  • Postcondition: All elements in the range [a,b) are fooed.
  • Complexity: O(distance(a,b)).

Thats it. Users read the standard and know what it does. Implementers read the standard too and need to implement what is written there. For example, the standard guarantees that foo has linear complexity. How this is achieved is up to the implementer of foo.

Upvotes: 0

Related Questions